| Date | Topics Covered | Reading |
| 9/25 | Course intro and info; Three problems; Automata | 0 |
| 9/28 | Solving problems with Finite Automata; Example FAs; Alphabets/strings/languages | 1.1 |
| 9/30 | DFA Defn; Delta hat; Proof of Simple property of delta hat (induction) | Lecture notes |
| 10/2 | Proving DFA minimality (pigeon-hole); Properties of Regular Languages | Lect. notes, 1.1 |
| 10/5 | Closures: union, complement, intersection (cross product construction); Nondeterminism | 1.2 |
| 10/7 | Solving problems with NFAs; Defn of NFA | 1.2 |
| 10/9 | NFA Computation; Closure properties of NFAs | 1.2 |
| 10/12 | DFA-NFA equivalence (subset construction) | 1.3 |
| 10/14 | Regular Expressions; NFA-DFA-regexp connection; Decision Procedures | 1.4, Lect. Notes |
| 10/16 | Properties of Regular Languages: Pumping | 1.4 |
| 10/19 | Pumping Lemma and Nonregular Languages | 1.4 |
| 10/21 | PL examples; CFG definitions and examples; | 2.1 |
| 10/23 | Computation with CFGs; CFG design; Parse Trees and Ambiguous Grammars | 2.1 |
| 10/26 | MIDTERM Exam | All the above |
| 10/28 | Parse Trees and Ambiguous Grammars | 2.1, Lect. Notes |
| 10/30 | Properties of CFLs: Closures, Chomsky Normal Form | 2.1, Lect. Notes |
| 11/2 | Decision Procedures; Push Down Automata: Defns and Examples;Computation with PDAs | 2.2, Lect. Notes |
| 11/4 | Equivalence of PDAs and CFGs; Closure of the Regular Languages intersection with CFLs | 2.2 (skip pages 115 - 122) |
| 11/6 | Pumping Lemma for CFLs | 2.3 |
| 11/9 | Turing Machines: Motivation and Design; Definitions | 3.1 |
| 11/11 | Veteran's Day, No Class | |
| 11/13 | Definition of Computation; Turing Acceptable vs Turing Decidable Languages | 3.2 |
| 11/16 | TM variants: multitape TMs; Non-deterministic TMs | 3.2 |
| 11/18 | NTMs; Enumerators; Dove-tailing; Church-Turing Thesis | 3.3 |
| 11/20 | Decidability; Languages vs Problems; Halting Problem | 4.1 |
| 11/23 | Universal Turing Machines, The Matrix |
4.2, Lect. Notes |
| 11/25 | Undecidable Problems; Reductions; Atm, HALTtm Language Hierarchy Revisited | 5.1 (skip pages 193 - 206) |
| 11/27 | Thankgsgiving, No Class | |
| 11/30 | Mapping Reductions; Computable Functions; | 5.3 |
| 12/2 | Finish Reductions; Time Complexity of Algorithms;The classes P and NP | 5.3, Ch. 7, Lect. Notes |
| 12/4 | NP problems; Evaluating your instructor and TAs | Ch. 7, Lect. Notes |
| 12/10 | FINAL Exam, 3:30-5:30pm | 10/28 and after |