| 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 | |
| Mon | Oct 12 | No class: Thanksgiving Day | |
| 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.
|
|