| Class # | Date | Lecture Topic | Materials | Assignments |
| Week 1 | ||||
| 1 | 1/18 | Motivation, mathematical preliminaries | Sipser, Ch 0 | |
| 2 | 1/20 | More preliminaries | Sipser, Sec 1.1 | HW 0 assigned |
| Week 2 | ||||
| 3 | 1/25 | DFAs | Sipser, Sec 1.1 | |
| 4 | 1/27 | Closure theorems, NFAs | Sipser, Sec 1.2 | HW 0 due / HW1 assigned |
| Week 3 | ||||
| 5 | 2/1 | NFA-DFA equivalence; proving closure thms | Sipser, Sec 1.2 | |
| 6 | 2/3 | Regular expressions | Sipser, Sec 1.3 | |
| Week 4 | ||||
| 7 | 2/8 | Reg. expr., GNFAs, equivalence | Sipser, Sec 1.3 | |
| 8 | 2/10 | Nonregular languages, pumping lemma | Sipser, Sec 1.4 | Hw 1 due / HW2 assigned |
| Week 5 | ||||
| 9 | 2/15 | Using the pumping lemma | Sipser, Sec 1.4 | |
| 10 | 2/17 | Substitution, homomorphism, equivalence classes | handout | |
| Week 6 | ||||
| 11 | 2/22 | equivalence classes; DFA minization | handout | |
| 12 | 2/24 | Myhill-Nerode Theorem | handout | HW 2 due |
| Week 7 | ||||
| 13 | 3/1 | Context free grammars and languages | Sipser 2.1 | |
| 3/2 | MIDTERM 1 7:00PM | |||
| 14 | 3/3 | Chomsky normal form | Sipser 2.1 | HW 3 assigned |
| Week 8 | ||||
| 15 | 3/8 | Pushdown automata (PDAs) | Sipser 2.2 | |
| 16 | 3/10 | PDA-CFL equivalence | Sipser 2.2 | |
| Week 9 | ||||
| 17 | 3/15 | Pumping lemma for CFLs; non-CFLs | Sipser 2.3 | |
| 18 | 3/17 | CFL closure properties | handout | HW3 due / HW4 assigned |
| Spring Break | ||||
| Week 10 | ||||
| 19 | 3/29 | CYK algorithm, context-sensitive grammars | handout | |
| 20 | 3/31 | Chomsky hierarchy, Turing machines | Sipser 3.1 | |
| Week 11 | ||||
| 21 | 4/5 | recognizable, decidable langs, TM examples | Sipser 3.1 | |
| 22 | 4/7 | TM variants, Church-Turing thesis | Sipser 3.2 | HW4 due |
| Week 12 | ||||
| 23 | 4/12 | enumerators, Church-Turing thesis | Sipser 3.3 | |
| 4/13 | MIDTERM 2 7:00PM | |||
| 24 | 4/14 | Decidability, halting problem | Sipser 4.1,4,2 | |
| Week 13 | ||||
| 25 | 4/19 | reducibility | Sipser 5.1 | HW5 assigned |
| 26 | 4/21 | Post's correspondence problem, mapping reducibility | Sipser 5.2,5.3 | |
| Week 14 | ||||
| 27 | 4/26 | Complexity theory, P, NP | Sipser 7.1-7.3 | |
| 28 | 4/28 | NP-completeness | Sipser 7.4 | |
| Week 15 | ||||
| 29 | 5/3 | Mystery topic | ??? | HW5 due |
Note: The recursive automata notes above were written by Madhusudan Parthasarathy and Sariel Har-Peled.