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