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: 1/18/26
Changelog:
| Date | Topics | Readings | Assignment Timeline |
|---|---|---|---|
| January 20 (Tuesday) | Overview and Math Review | First class to-do list | |
| January 22 (Thursday) | Mathematical Literacy | Sipser 0.1-0.4 | Problem Set 0 released (not graded) |
| January 25 (Sunday) | Due: Labs from 1/20 and 1/22 | ||
| January 27 (Tuesday) | Deterministic Finite Automata | Sipser 1.1 | |
| January 29 (Thursday) | Nondeterminism | Sipser 1.2 | Problem Set 1 released |
| Add/drop deadline, January 30 (Friday) | |||
| February 1 (Sunday) | Due: Labs from 1/27 and 1/29 | ||
| February 3 (Tuesday) | Regular Expressions | Sipser 1.3 | |
| February 5 (Thursday) | Nonregularity | Sipser 1.4, Handout | Due: Problem Set 1 Problem Set 2 released |
| February 8 (Sunday) | Due: Labs from 2/3 and 2/5 | ||
| February 10 (Tuesday) | Decision Procedures for Regular Models | Handout (pdf) | |
| February 12 (Thursday) | Turing Machines | Sipser 3.1 | Due: Problem Set 2 Problem Set 3 released |
| February 15 (Sunday) | Due: Labs from 2/10 and 2/12 | ||
| February 17 (Tuesday) | Variants of Turing Machines | Sipser 3.2, 3.3 | |
| February 19 (Thursday) | Decidability | Sipser 4.1 | Due: Problem Set 3 |
| February 22 (Sunday) | Due: Labs from 2/17 and 2/19 | ||
| February 24 (Tuesday) | Exam 1 | ||
| February 26 (Thursday) | Undecidability | Sipser 4.2 | Problem Set 4 released |
| March 1 (Sunday) | Due: Labs from 2/26 | ||
| March 3 (Tuesday) | Undecidable Problems | Sipser 5.1, skim 5.2 | |
| March 5 (Thursday) | Reducibility | Sipser 5.3, Handout | Due: Problem Set 4 Problem Set 5 released |
| Spring break, March 9-20 | |||
| March 22 (Sunday) | Due: Labs from 3/3 and 3/5 | ||
| March 24 (Tuesday) | Rice's Theorem | Handout (pdf) | |
| March 26 (Thursday) | Kolmogorov Complexity | Sipser 6.4 | Due: Problem Set 5 |
| March 29 (Sunday) | Due: Labs from 3/24 and 3/26 | ||
| March 31 (Tuesday) | Exam 2 | ||
| April 2 (Thursday) | Time Complexity | Sipser 7.1, 7.2 | Problem Set 6 released |
| Withdraw deadline, April 3 (Friday) | |||
| April 5 (Sunday) | Due: Labs from 3/31 and 4/1 | ||
| April 7 (Tuesday) | NP-Completeness | Sipser 7.3, 7.4 (only up to Cook-Levin pp. 304) | |
| April 9 (Thursday) | More NP-Completeness | Sipser 7.5 | Due: Problem Set 6 Problem Set 7 released |
| April 12 (Sunday) | Due: Labs from 4/9 | ||
| April 14 (Tuesday) | Cook-Levin Theorem | Finish Sipser 7.4 | |
| April 16 (Thursday) | Savitch's Theorem | Sipser 8.1 | Due: Problem Set 7 Problem Set 8 released |
| April 19 (Sunday) | Due: Labs from 4/14 and 4/16 | ||
| April 21 (Tuesday) | PSPACE-Completeness | Sipser 8.2, 8.3 | |
| April 23 (Thursday) | L and NL | Sipser 8.4-8.6 | Due: Problem Set 8 Problem Set 9 released |
| April 26 (Sunday) | Due: Labs from 4/21 and 4/23 | ||
| April 28 (Tuesday) | Hierarchy Theorems | Sipser 9.1 (only up to EXPSPACE-complete, pp. 372) | |
| April 30 (Thursday) | Intractability | Sipser 10.1, 10.2 | Due: Problem Set 9 Problem Set 10 released |
| May 3 (Sunday) | Due: Labs from 4/28 and 4/30 | ||
| May 5 (Tuesday) | Special Topics in Theory | TBD | |
| May 7 (Thursday) | Course wrap-up | TBD | Due: Problem Set 10 |
| May 9 (Sunday) | Due: Labs from 12/9 and 12/11 | ||
| May 12 (Tuesday) | Final exam (section -02 only) | ||
| May 14 (Thursday) | Final exam (section -01 only) | ||
| May 15 (Friday) | All work due 5pm (including revisions) | ||