| September 6: | Course Overview | notes | slides |
| September 8: | Induction and Strings | notes | slides |
| September 11: | A Proof for Sept. 8 | notes | no slides |
| September 13: | Regular Languages | notes | slides |
| September 15: | Nondeterminism | notes | slides |
| September 18: | NFAs | notes | slides |
| September 20: | Equivalence of NFAs and DFAs | slides | |
| September 22: | Regular Expressions | slides | |
| September 25: | Equivalance of REs and NFAs/DFAs | slides | printer-friendly slides |
| September 27: | The Pumping Lemma | slides | printer-friendly slides |
| September 29: | Wrapping-Up Regular Languages | slides | printer-friendly slides |
| September 29: | Wrapping-Up Regular Languages | slides | printer-friendly slides |
| October 2: | Context-Free Languages | slides | |
| October 4: | Context-Free Languages (cont.) | slides | |
| October 6: | Applications of Context-Free Languages | slides | |
| October 9: | Thanksgiving: no lecture | ||
| October 11: | Midterm 1 | questions | solution |
| October 13: | Chomsky Normal Form | slides | |
| October 16: | Pushdown Automata | slides | |
| October 18: | PDAs and CFLs | slides | |
| October 20: | The Pumping Lemma for CFLs | slides | |
| October 23: | The Halting Problem | slides | printer-friendly slides |
| October 25: | Turing Machines | slides | |
| October 27: | Programming Turing Machines | No slides or notes | |
| October 30: | The Church-Turing Thesis | slides | |
| November 1: | Decidable Problems | slides | printer-friendly slides |
| November 3: | Universal Turing Machines and Diagonalization | slides | printer-friendly slides |
| November 6: | The Halting Problem for Turing Machines | slides | |
| November 8: | Reductions | slides | |
| November 10: | Reductions and Computational Histories | slides | |
| November 17: | Computational Histories and Post's Correspondence Problem | slides | |
| November 22: | Proofs | slides | |
| November 29: | The GHz Race Is Over | slides | printer-friendly slides |