| 1 | Introduction, Finite Automata, Regular Expressions | |
| 2 | Nondeterminism, Closure Properties, Regular Expressions ↔ FA | |
| 3 | Regular Pumping Lemma, Context Free Languages | |
| 4 | Pushdown Automata, CFG ↔ PDA | |
| 5 | CF Pumping Lemma, Turing Machines | Homework 1 due |
| 6 | TM Variants, Church-Turing Thesis | |
| 7 | Decision Problems for Automata and Grammars | |
| 8 | Undecidability | |
| 9 | Reducibility | Homework 2 due |
| 10 | Linearly Bounded Automata, PCP | |
| 11 | Recursion Theorem and Logic | |
| 12 | Time Complexity | Homework 3 due |
| 13 | Midterm Exam | |
| 14 | P and NP, SAT, Poly-time Reducibility | |
| 15 | NP-Completeness | |
| 16 | Cook-Levin Theorem | Homework 4 due |
| 17 | Space Complexity | |
| 18 | PSPACE, TQBF, Savitch's Theorem | |
| 19 | Games, Generalized Geography | |
| 20 | L and NL, NL= coNL | Homework 5 due |
| 21 | Hierarchy Theorems | |
| 22 | Provably Intractable Problems, Oracles | |
| 23 | Probabilistic Computation, BPP | |
| 24 | Probabilistic Computation (cont.) | |
| 25 | Interactive Proof Systems, IP | Homework 6 due |
| 26 | Topic | |
| 27 | Final Exam | |