| Week | Day | Topics | Readings |
|---|---|---|---|
| Nov 28 - Dec 2 | 1 | Introduction to course, Skills review | 0.4 |
| 2 | The basic Turing Machine | 3.1 | |
| 3 | Modifications of Turing Machines | 3.2 | |
| 4 | I am out of town. Use this time to work on the homework assignment. | ||
| Dec 5 - 9 | 5 | Turing machines, The Church Turing thesis | 3.3 |
| 6 | The Halting problem | 4.2 | |
| 7 | The Halting problem revisited | 4.2 | |
| 8 | Finite automata | 1.1 | |
| Dec 12 - 16 | 9 | Finite automata, Nondeterminism | 1.1 cont'd, 1.2 |
| 10 | Nondeterminism | 1.2 cont'd | |
| 11 | Regular expressions | 1.3 | |
| 12 | Nonregular languages | 1.4 | |
| Dec 19 - 20 | 13 | Context-free grammars | 2.1 |
| 14 | No class, to compensate for evening exam. | ||
| Jan 5 - 6 | 15 | Chomsky Normal Form | 2.1 |
| 16 | Pushdown automata | 2.2 | |
| Jan 9 - 13 | 17 | Pushdown automata | 2.2 cont'd |
| 18 | Pushdown automata | 2.2 cont'd | |
| 19 | Non-context-free languages | 2.3 | |
| 20 | Review of pumping lemma for CFL
Review of equivalence of PDAs and CFG | ||
| Jan 16 - 20 | 21 | Review of Turing Machines | 3.1 - 3.3 |
| 22 | Decidability | 4.1 | |
| 23 | Decidability | 4.1 cont'd | |
| 24 | Undecidability of Halting problem | 4.2 cont'd | |
| Jan 23 - 27 | 25 | Turing-unrecognizable language | 4.2 cont'd |
| 26 | Reducibility | 5.1 | |
| 27 | Reducibility | 5.1 cont'd | |
| 28 | No class, to compensate for take-home exam | ||
| Jan 30 - Feb 3 | 29 | Rice's Theorem | |
| 30 | Post correspondence problem | 5.2 | |
| 31 | Goedel's incompleteness proof | ||
| 32 | A decidable theory | 6.2 cont'd | |
| Feb 6 - 10 | 33 | Time complexity | 7.1 |
| 34 | The class P | 7.2 | |
| 35 | The class NP, P vs NP | 7.3 | |
| 36 | NP-completeness | 7.4 | |
| Feb 13 - 17 | 37 | NP-completeness | 7.4, cont'd |
| 38 | Space complexity | 8.1 | |
| 39 | The class PSPACE | 8.2 | |
| 40 | Review, Time for course evaluations. |