Our course schedule is outlined below. This is subject to change depending on the particular needs and pacing of this iteration of the course; I will note specific updates as they arise. In each row, the Reading and any associated activities should be completed before class begins on the specified Date. Note that dates use the American convention: Month/Day/Year.
Last updated: 8/22/2025
| Date | Topics | Readings | Assignment Timeline |
|---|---|---|---|
| August 28 (Thursday) | Overview and Math Review | First class to-do list | |
| August 31 (Sunday) | Due: Labs from 8/28 | ||
| September 2 (Tuesday) | Mathematical Literacy | Sipser 0.1-0.4 | |
| September 4 (Thursday) | Deterministic Finite Automata | Sipser 1.1 | Homework 1 released |
| September 7 (Sunday) | Due: Labs from 9/2 and 9/4 | ||
| September 9 (Tuesday) | Nondeterminism | Sipser 1.2 | |
| September 11 (Thursday) | Regular Models (Closure and Minimization) | Handout (pdf) | Due: Homework 1 Homework 2 released |
| Add/drop deadline, September 12 (Friday) | |||
| September 14 (Sunday) | Due: Labs from 9/9 and 9/11 | ||
| September 16 (Tuesday) | Regular Expressions | Sipser 1.3 | |
| September 18 (Thursday) | Irregularity | Sipser 1.4, Handout | Due: Homework 2 Homework 3 released |
| September 21 (Sunday) | Due: Labs from 9/16 and 9/18 | ||
| September 23 (Tuesday) | Context-Free Grammars | Sipser 2.1 | |
| September 25 (Thursday) | Turing Machines | Sipser 3.1 | Due: Homework 3 |
| September 28 (Sunday) | Due: Labs from 9/23 and 9/25 | ||
| September 30 (Tuesday) | Exam 1 | ||
| October 2 (Thursday) | Variants of Turing Machines | Sipser 3.2 | Homework 4 released |
| October 5 (Sunday) | Due: Labs from 9/30 and 10/2 | ||
| October 7 (Tuesday) | Decidability | Sipser 4.1 | |
| October 9 (Thursday) | Undecidability | Sipser 4.2 | Due: Homework 4 Homework 5 released |
| October 12 (Sunday) | Due: Labs from 10/9 | ||
| October 14 (Tuesday) | Undecidable Problems | Sipser 5.1, skim 5.2 | |
| October 16 (Thursday) | Reducibility | Sipser 5.3 | Due: Homework 5 Homework 6 released |
| October 19 (Sunday) | Due: Labs from 10/14 and 10/16 | ||
| Fall break, October 20-24 | |||
| October 28 (Tuesday) | Rice's Theorem | Handout | |
| October 30 (Thursday) | Time Complexity | Sipser 7.1, 7.2 | Due: Homework 6 |
| November 2 (Sunday) | Due: Labs from 10/28 and 10/30 | ||
| November 4 (Tuesday) | Exam 2 | ||
| November 6 (Thursday) | NP-Completeness | Sipser 7.3, 7.4 (only up to Cook-Levin pp. 304) | Homework 7 released |
| Withdraw deadline, November 7 (Friday) | |||
| November 9 (Sunday) | Due: Labs from 11/4 and 11/6 | ||
| November 11 (Tuesday) | More NP-Completeness | Sipser 7.5 | |
| November 13 (Thursday) | Cook-Levin Theorem | Finish Sipser 7.4 | Due: Homework 7 Homework 8 released |
| November 16 (Sunday) | Due: Labs from 11/13 | ||
| November 18 (Tuesday) | Savitch's Theorem | Sipser 8.1 | |
| November 20 (Thursday) | PSPACE-Completeness | Sipser 8.2, 8.3 | Due: Homework 8 Homework 9 released |
| November 23 (Sunday) | Due: Labs from 11/18 and 11/20 | ||
| November 25 (Tuesday) | L and NL | Sipser 8.4-8.6 | |
| Thanksgiving break, November 27-28 | |||
| November 30 (Sunday) | Due: Labs from 11/25 | ||
| December 2 (Tuesday) | Hierarchy Theorems | Sipser 9.1 | |
| December 4 (Thursday) | Approximation Algorithms | Sipser 9.2 | Due: Homework 9 Released: Homework 10 |
| December 7 (Sunday) | Due: Labs from 12/2 and 12/4 | ||
| December 9 (Tuesday) | Special Topics in Theory (TBD) | READING | |
| December 11 (Thursday) | Wrap-up | Due: Homework 10 | |
| December 14 (Sunday) | Due: Labs from 12/9 and 12/11 | ||
| December 17 (Wednesday) | Final exam (section -01 only) | ||
| December 19 (Friday) | Final exam (section -02 only) | All work due (including revisions) | |