This page will be updated frequently with current and upcoming topics.
Any content that's colored light gray is tentative and subject to change.
Homework sets will be available on this course's Canvas page (under Files). Please read the policies section of the course website for submission instructions, the lateness policy (which is absolutely strict), grading standards, and the academic honor principle.
Lectures, Quizzes, and Submissions Due
In the table below, all references are to the required textbook (Sipser). Notation like "p34" refers to a particular page number; notation like "2.1" refers to a section number; notation like "Ch 3" refers to an entire chapter.
| # | Date | Class Topics / Other Events | References |
|---|---|---|---|
| 1 |
Thu Jan 05 | Administrivia, overview; Math background; Strings and languages | Slides; 0.1, 0.2, 0.3, 0.4 |
| S |
Mon Jan 09 | No homework due yet | |
| 2 |
Tue Jan 10 | Finite automata (DFA); examples; formalization | 1.1 |
| X |
Wed Jan 11 | x-hour not used | |
| 3 |
Thu Jan 12 | Nondeterminism; NFA; Regular expressions (teaser) | 1.2; 1.3 up to p66 (whiteboard) |
| S |
Mon Jan 16 | Homework 1 due by 22:00:00 | |
| 4 |
Tue Jan 17 | Kleene's Theorem I and II: RegExp → NFA → DFA | 1.3 up to p69 (whiteboard) |
| X |
Wed Jan 18 | converted to an office hour | |
| 5 |
Thu Jan 19 | Kleene's Theorem III: DFA → RegExp; Pumping lemma | Notes; 1.3 (whiteboard) |
| S |
Mon Jan 23 | Homework 2 due by 22:00:00 | |
| 6 |
Tue Jan 24 | Proving non-regularity via pumpling lemma and/or closure properties | 1.4 |
| X |
Wed Jan 25 | Discussion of HW2; Improving mathematical presentation and formalism | |
| 7 |
Thu Jan 26 | Pushdown automata (PDA); examples; formalization | 2.2 up to p116 |
| S |
Mon Jan 30 | Homework 3 due by 22:00:00 | |
| 8 |
Tue Jan 31 | Context-free grammars (CFG); Ambiguity; conversion CFG → PDA | 2.1; 2.2 (whiteboard) |
| Q |
Wed Feb 01 | Quiz 1: closed notes, in class | |
| 9 |
Thu Feb 02 | Formal proofs with CFLs; conversion PDA → CFG | Notes; 2.2 (whiteboard) |
| S |
Mon Feb 06 | Homework 4 due by 22:00:00 | |
| 10 |
Tue Feb 07 | Closure properties; pumping lemma for CFLs; non context-freedom | 2.3 (whiteboard) |
| X |
Wed Feb 08 | x-hour not used | |
| 11 |
Thu Feb 09 | Turing Machines; variants (multi-tape and nondeterministic) | Simulators [1], [2], [3]; Slides; 3.1, 3.2, 3.3 |
| S |
Mon Feb 13 | Midterm exam due by 22:00:00 | |
| 12 |
Tue Feb 14 | NDTM → TM; RAM model; Church-Turing thesis; Enumerators | Slides; 3.2, 4.1 (whiteboard) |
| X |
Wed Feb 15 | x-hour not used | |
| 13 |
Thu Feb 16 | Universal TM; Decision problems ACFG, ETM, etc.; Undecidability | 4.2; 5.1 up to p220 (whiteboard) |
| S |
Mon Feb 20 | Homework 5 due by 22:00:00 | |
| 14 |
Tue Feb 21 | Reductions and mapping reductions; more undecidable and unrecognizable languages | 5.1 up to p220; 5.3 (whiteboard) |
| Q |
Wed Feb 22 | Quiz 2: closed notes, in class | |
| 15 |
Thu Feb 23 | Time complexity; P and NP; Reductions and NP-completeness | Slides; 7.1, 7.2, 7.3 |
| S |
Mon Feb 27 | Homework 6 due by 22:00:00 | |
| 16 |
Tue Feb 28 | More reductions; growing the web of NP-complete problems | 7.4; 7.5 to p318 (whiteboard) |
| X |
Wed Mar 01 | Open discussion; AMA | |
| 17 |
Thu Mar 02 | The problems INTCFG and ALLCFG; the Cook-Levin theorem | 7.5; 5.1 |
| S |
Mon Mar 06 | Homework 7 due by 22:00:00 | |
| 18 |
Tue Mar 07 | Looking beyond: modern topics in computaional complexity theory |
The precise plan for the X-hours is not yet set, but please be available during every X-hour.
Reading Homework
There is reading homework associated with every class, which consists of reading the related sections of the textbook, plus any slides or notes linked from the table above. On rare occasions, the reading will cover a theorem or a small topic that was not discussed in detail in class. In any case, this reading homework is always due before the next class. There is nothing to submit and no grade for this homework, but I assume that you will nevertheless do the homework on time, every time.
Be warned that not doing this reading homework will make it very hard to follow along during the next class.