Prof. Tom Hayes | University at Buffalo | Fall 2026
Welcome to Fall 2026! Classes begin on Monday, August 24. Please make sure you join our Piazza space and review the Syllabus & Policies page before our first session.
The schedule below outlines our topical progression, homework releases, and assessment milestones. Lecture notes and homework handouts will be linked here as we progress.
| Week | Dates | Core Topics | Milestones & Deliverables |
|---|---|---|---|
| Week 1 | Aug 24 – Aug 28 | Course Intro, Mathematical Preliminaries, DFAs (5-tuples) | HW 1 Released (Fri) |
| Week 2 | Aug 31 – Sep 4 | NFAs & Subset Construction (Labor Day Mon) | Monday Tutorial: Problem Workshop |
| Week 3 | Sep 7 – Sep 11 | Regular Expressions & Kleene's Theorem | Assessment 1 & HW 2 Released (Fri) |
| Week 4 | Sep 14 – Sep 18 | DFA Minimization & Myhill-Nerode Theorem | Monday Tutorial: Problem Workshop |
| Week 5 | Sep 21 – Sep 25 | Pumping Lemma for Regular Languages | Assessment 2 & HW 3 Released (Fri) |
| Week 6 | Sep 28 – Oct 2 | Context-Free Grammars (CFGs) & Parse Trees | Midterm 1 (Friday) |
| Week 7 | Oct 5 – Oct 9 | Ambiguity & Pushdown Automata (PDAs) | Monday Tutorial: Problem Workshop |
| Week 8 | Oct 12 – Oct 16 | Chomsky Normal Form & CFL Properties (Fall Break) | Assessment 3 & HW 4 Released (Fri) |
| Week 9 | Oct 19 – Oct 23 | Turing Machines (Formal Definition & Variants) | Monday Tutorial: Problem Workshop |
| Week 10 | Oct 26 – Oct 30 | Decidability & Turing-Recognizability | Assessment 4 & HW 5 Released (Fri) |
| Week 11 | Nov 2 – Nov 6 | Undecidability: Diagonalization & Halting Problem | Midterm 2 (Friday) |
| Week 12 | Nov 9 – Nov 13 | Mapping Reductions | Monday Tutorial: Problem Workshop |
| Week 13 | Nov 16 – Nov 20 | Advanced Reductions & Cook-Levin Overview | Assessment 5 & HW 6 Released (Fri) |
| Week 14 | Nov 23 – Nov 27 | Time Complexity & P vs. NP (Thanksgiving Wed-Fri) | Monday Tutorial: Problem Workshop |
| Week 15 | Nov 30 – Dec 4 | NP-Completeness & Course Wrap-Up | Assessment 6 (Friday) |
| Finals Week | Dec 7 – Dec 11 | Cumulative Review & Final Exam Block | Final Exam |