| 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 | 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.
|
|