| Date | Topic | Notes/References | |
|---|---|---|---|
| Wed | Sept 9 | intro to TCS | Post, P-vs-NP, lec 1 |
| Wed | Sept 9 | Homework 1 released (due Sept 21): Latex (set1.tex) | |
| Fri | Sept 11 | intro to TCS | sensitivity, entropy, lec 2 |
| Mon | Sept 14 | intro to TCS | coding, Freivalds, gems, lec 3 |
| Wed | Sept 16 | intro to TCS; strings and languages | CHSH, Nobel '22, lec 4 |
| Fri | Sept 18 | decision problems, DFAs | lec 5, [S, Sec. 1.1] |
| Mon | Sept 21 | DFAs, concatenation | lec 6, [S, Sec. 1.1] |
| Mon | Sept 21 | add/drop deadline | |
| Wed | Sept 23 | NFAs (informal) | lec 7, [S, Sec. 1.2] |
| Fri | Sept 25 | NFAs (formal) | lec 8, [S, Sec. 1.2] |
| Fri | Sept 25 | Homework 2 released (due Oct 9): Latex (set2.tex) | |
| Mon | Sept 28 | simulating NFA by DFA | lec 9, [S, Sec. 1.2] |
| Wed | Sept 30 | No class: National Day for Truth and Reconciliation | |
| Fri | Oct 2 | regular expression, pumping lemma | lec 10, [S, Sec. 1.3-1.4] |
| Mon | Oct 5 | pumping lemma | lec 11, [S, Sec. 1.4] |
| Wed | Oct 7 | OpenAI release, Turing machine | lec 12, blog post, [S, Sec. 3.1] |
| Fri | Oct 9 | Turing machine | lec 13, [S, Sec. 3.1] |
| Mon | Oct 12 | No class: Thanksgiving Day | |
| Wed | Oct 14 | Turing machine | lec 14, [S, Sec. 3.1-3.2] |
| Fri | Oct 16 | multitape and nondeterministic TMs | lec 15, [S, Sec. 3.2] |
| Mon | Oct 19 | midterm exam | |
| Mon | Oct 19 | Homework 3 released (due Nov 13): Latex (set3.tex) | |
| Wed | Oct 21 | intro to computability; countability | lec 16, [S, Sec. 3.3, 4.2] |
| Fri | Oct 23 | (un)countability, A_TM | lec 17, [S, Sec. 3.3, 4.2] |
| Mon | Oct 26 | A_TM, Halting problem, reductions | lec 18, [S, Sec. 4.2, 5.1] |
| Wed | Oct 28 | more reductions, PCP | lec 19, [S, Sec. 5.1, 5.2] |
| Fri | Oct 30 | undecidability of PCP | lec 20, [S, Sec. 5.2] |
| Mon | Nov 2 | intro to time complexity | lec 21, [S, Sec. 7.1] |
| Wed | Nov 4 | multitape-TM complexity, P | lec 22, [S, Sec. 7.1, 7.2] |
| Fri | Nov 6 | PATH in P, NTM complexity, NP | lec 23, [S, Sec. 7.2, 7.3] |
| Mon | Nov 9 | No class: midterm break/Remembrance Day | |
| Wed | Nov 11 | No class: midterm break | |
This is an undergraduate introductory course to the theory of computation. For the first three items below, we will closely follow Introduction to the Theory of Computation (3rd edition) by Sipser [S].
Tentative list of topics:
The formal prerequisites include CPSC 221 and 320. In particular, you should be familiar with [S, Section 0], Big-O and little-o notation, and basic algorithms and discrete math. Some basic knowledge of probability is useful for the topics part of the course but I plan to review it.
GenAI policy: any use of GenAI is prohibited for homeworks; answers suspected of being from GenAI (for example, by Pangram) will receive zero credit unless you can demonstrate understanding upon appeal.
|
|