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 |
Wed Jan 05 | Welcome, administrivia, overview; Math background | Slides; 0.1, 0.2, 0.3, 0.4 |
| 2 |
Thu Jan 06 | More on proofs; Strings and languages | Slides; 0.4 |
| 3 |
Fri Jan 07 | Finite automata (DFA); examples; formalization as (Q,Σ,δ,q0,F) | 1.1 (whiteboard) |
| 4 |
Mon Jan 10 | More DFA examples; Nondeterminism and NFA (teaser) | 1.2 (whiteboard) |
| S |
Tue Jan 11 | Homework 1 due by 22:00:00 | |
| 5 |
Wed Jan 12 | More on NFAs; Union and concatenation; Regular expressions | 1.3 up to p69 (whiteboard) |
| 6 |
Thu Jan 13 | Regular languages; Kleene's Theorem and proof outline | 1.3 up to p69 (whiteboard) |
| 7 |
Fri Jan 14 | Kleene's Theorem I and II: RegExp → NFA → DFA | Notes; 1.3 (whiteboard) |
| H |
Mon Jan 17 | MLK day | |
| S |
Tue Jan 18 | Homework 2 due by 22:00:00 | |
| 8 |
Wed Jan 19 | Kleene's Theorem III: DFA to RegExp | Notes; 1.3 (whiteboard) |
| 9 |
Thu Jan 20 | The pumping lemma; proving non-regulartiy | 1.4 (whiteboard) |
| 10 |
Fri Jan 21 | More non-regularity; Closure properties; Pushdown automata (PDA) | 1.4; 2.2 up to p112 (whiteboard) |
| 11 |
Mon Jan 24 | More PDA examples; Formalization | 2.2 up to p116 (whiteboard) |
| S |
Tue Jan 25 | Homework 3 due by 22:00:00 | |
| Q |
Wed Jan 26 | Quiz 1: closed notes, in class | |
| 12 |
Thu Jan 27 | Context-free grammars (CFG); Formalization; Ambiguity | 2.1 up to p107 (whiteboard) |
| 13 |
Fri Jan 28 | Further formalization with PDAs and CFGs | Notes; 2.1 (whiteboard) |
| 14 |
Mon Jan 31 | Ambiguity and disambiguation; Chomsky Normal Form | 2.1 (whiteboard) |
| S |
Tue Feb 01 | [Extended deadline: now due Feb 2] Homework 4 due by 22:00:00 | |
| 15 |
Wed Feb 02 | Equivalence of CFGs and PDAs, I | Notes; 2.2 up to p120 (whiteboard) |
| 16 |
Thu Feb 03 | Equivalence of CFGs and PDAs, II | 2.2 (whiteboard) |
| 17 |
Fri Feb 04 | Closure properties and pumping lemma for CFLs; applications | 2.3 (whiteboard) |
| 18 |
Mon Feb 07 | Turing Machines; examples; formal definition | 3.1; Simulators [1], [2], [3] (whiteboard) |
| S |
Tue Feb 08 | Midterm exam due by 22:00:00 | |
| 19 |
Wed Feb 09 | Multi-tape TMs; Equivalence with single-tape TMs | Slides; 3.2 up to p178 |
| 20 |
Thu Feb 10 | Nondeterministic TMs; The RAM model; Church-Turing Thesis | Slides; 3.2, 3.3 |
| 21 |
Fri Feb 11 | Enumerator TMs; Connections with deciders/recognizers | 3.2 (whiteboard) |
| 22 |
Mon Feb 14 | Decision problems for major language classes: ADFA, ACFG, ATM; Undecidability | 4.1 (whiteboard) |
| S |
Tue Feb 15 | Homework 5 due by 22:00:00 | |
| 23 |
Wed Feb 16 | More decision problems: EX, ALLX, EQX, INTX; Undecidability and unrecognizability | 4.2 (whiteboard) |
| 24 |
Thu Feb 17 | Reductions, mapping reductions, and their applications | 5.1 up to p220, 5.3 (whiteboard) |
| 25 |
Fri Feb 18 | Time complexity; P and NP | 7.1, 7.2, 7.3 (whiteboard) |
| Q |
Mon Feb 21 | Quiz 2: closed notes, in class | |
| S |
Tue Feb 22 | [Extended deadline: now due Feb 23] Homework 6 due by 22:00:00 | |
| 26 |
Wed Feb 23 | NP-completeness and polynomial time reductions (intro) | Slides; 7.4 to p304, 7.5 to p318 |
| 27 |
Thu Feb 24 | NP-completeness of CLIQUE, UHAMCYCLE, TSP | 7.5 (whiteboard) |
| 28 |
Fri Feb 25 | NP-completeness of 3-COL; Tractability of 2-COL and 2-SAT | 7.5 (whiteboard) |
| 29 |
Mon Feb 28 | Computational tableaux; Undecidability of INTCFG; Unrecognizability of ALLCFG | 5.1 (whiteboard) |
| S |
Tue Mar 01 | Homework 7 due by 22:00:00 | |
| 30 |
Wed Mar 02 | Proof of the Cook-Levin theorem | 7.4 (whiteboard) |
| H |
Thu Mar 03 | x-hour not used | |
| 31 |
Fri Mar 04 | NP and search problems; Space complexity (glimpse) | |
| 32 |
Mon Mar 07 | Looking beyond: modern topics in computaional complexity theory | |
| S |
Tue Mar 08 | Homework 8 due by 22:00:00 |
As you can see, we will be using 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.