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