This course has ended. Links to slides and notes in the table below are no longer functional.
Topics Day-by-Day
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 | Topics | References |
|---|---|---|---|
| 1 | Mon Mar 26 | Welcome, administrivia, overview; Mathematical notation | Slides; 0.1, 0.2, 0.3 |
| 2 | Wed Mar 28 | Types of proof (direct, contradiction, induction) | Slides; 0.4 |
| 3 | Thu Mar 29 | Strings and languages; Finite automata; Basic DFA examples | 1.1 up to p34 |
| 4 | Fri Mar 30 | Further DFA examples; formalization as (Q,Σ,δ,q0,F) | 1.1 |
| 5 | Mon Apr 2 | Closure under union/intersection | 1.2 |
| 6 | Wed Apr 4 | The regular operations; Regular expressions | 1.3 up to p69 |
| 7 | Thu Apr 5 | Kleene's Theorem; Conversion of RegExp to NFA | Notes; 1.3 up to p69 |
| 8 | Fri Apr 6 | Kleene's Theorem II: Conversion of NFA to DFA | 1.3 |
| 9 | Mon Apr 9 | Kleene's Theorem III: of DFA to RegExp | Notes; 1.3 |
| 10 | Wed Apr 11 | The pumping lemma; proving non-regulartiy | 1.4 |
| 11 | Thu Apr 12 | Non-regularity via closure properties | 1.4 |
| 12 | Fri Apr 13 | Pushdown automata; examples | 2.2 up to p116 |
| Q | Mon Apr 16 | Quiz 1: closed notes, in class | |
| 13 | Wed Apr 18 | Formal definitions for PDAs; Closure under union, concatenation, star | 2.2 up to p116 |
| 14 | Thu Apr 19 | Context-free grammars; examples | 2.1 up to p106 |
| 15 | Fri Apr 20 | Formal definitions for CFGs; a sophisticated completeness proof | Notes |
| 16 | Mon Apr 23 | Ambiguity; Chomsky Normal Form | 2.1 |
| 17 | Wed Apr 25 | Equivalence of CFGs and PDAs, I | Notes; 2.2 up to p120 |
| 18 | Thu Apr 26 | Equivalence of CFGs and PDAs, II | 2.2 |
| 19 | Fri Apr 27 | Pumping lemma for CFLs; applications | 2.3 |
| 20 | Mon Apr 30 | Turing Machines; simple examples; formal definition | 3.1; Simulator 1; Simulator 2 |
| 21 | Wed May 2 | Multi-tape TMs; Equivalence with single-tape TMs | Slides; 3.2 up to p178 |
| 22 | Thu May 3 | Nondeterministic TMs; The RAM model; Church-Turing Thesis | Slides; 3.2, 3.3 |
| 23 | Fri May 4 | Enumerator TMs; Connections with deciders/recognizers | 3.2 |
| 24 | Mon May 7 | Decision problems for major language classes: ADFA, ACFG, ATM; EX, ALLX, EQX, INTX | 4.1 |
| 25 | Wed May 9 | Proving undecidability and unrecognizability | 4.2 |
| 26 | Thu May 10 | Catch-up (as needed) | 5.1 up to p220, 5.3 |
| 27 | Fri May 11 | Reductions, mapping reductions, and their applications | 5.3 |
| Q | Mon May 14 | Quiz 2: closed notes, in class | |
| 28 | Wed May 16 | Time complexity; P and NP | 7.1, 7.2, 7.3 |
| 29 | Thu May 17 | NP-completeness and polynomial time reductions (intro) | Slides; 7.4 up to p304, 7.5 up to p318 |
| 30 | Fri May 18 | NP-completeness of SAT (without proof), 3-SAT, IND-SET | 7.5 |
| 31 | Mon May 21 | NP-completeness of CLIQUE, UHAMCYCLE, TSP | 7.5 |
| 32 | Wed May 23 | NP-completeness of 3-COL; Tractability of 2-COL and 2-SAT | 7.5 |
| 33 | Thu May 24 | Computational tableaux | |
| 34 | Fri May 25 | Undecidability of INTCFG; Unrecognizability of ALLCFG | 5.1 |
| H | Mon May 28 | Memorial day | |
| 35 | Wed May 30 | Proof of the Cook-Levin theorem; Wrap up | 7.4 |
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 the homework will make it very hard to follow along during the next class.