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 | Mon Mar 25 | Welcome, administrivia, overview; Mathematical notation | Slides; 0.1, 0.2, 0.3 |
| S | Tue Mar 26 | Nothing to submit | |
| 2 | Wed Mar 27 | Types of proof (direct, contradiction, induction) | Slides; 0.4 |
| 3 | Thu Mar 28 | Strings and languages; Finite automata; Basic DFA examples | 1.1 up to p34 |
| 4 | Fri Mar 29 | Further DFA examples; formalization as (Q,Σ,δ,q0,F) | 1.1 |
| 5 | Mon Apr 01 | NFA; examples and formalization; union and concatenation | 1.2 |
| S | Tue Apr 02 | Homework 1 due by 22:00:00 | |
| 6 | Wed Apr 03 | The regular operations; Regular expressions | 1.3 up to p69 |
| 7 | Thu Apr 04 | Kleene's Theorem; Conversion of RegExp to NFA | Notes; 1.3 up to p69 |
| 8 | Fri Apr 05 | Kleene's Theorem II: Conversion of NFA to DFA | 1.3 |
| 9 | Mon Apr 08 | Kleene's Theorem III: of DFA to RegExp | Notes; 1.3 |
| S | Tue Apr 09 | Homework 2 due by 22:00:00 | |
| 10 | Wed Apr 10 | The pumping lemma; proving non-regulartiy | 1.4 |
| 11 | Thu Apr 11 | Proof of pumping lemma; more non-regularity proofs | 1.4 |
| 12 | Fri Apr 12 | Non-regularity via closure properties; Pushdown automata | 2.2 up to p116 |
| Q | Mon Apr 15 | Quiz 1: closed notes, in class | |
| S | Tue Apr 16 | Homework 3 due by 22:00:00 | |
| 13 | Wed Apr 17 | Several examples of PDAs | 2.2 up to p116 |
| 14 | Thu Apr 18 | Context-free grammars; a sophisticated completeness proof | Notes; ; 2.1 up to p106 |
| 15 | Fri Apr 19 | Formal definition of PDA, CFG; Closure properties | 2.1 up to p106 |
| 16 | Mon Apr 22 | Ambiguity; Chomsky Normal Form | 2.1 |
| S | Tue Apr 23 | Homework 4 due by 22:00:00 | |
| 17 | Wed Apr 24 | Equivalence of CFGs and PDAs, I | Notes; 2.2 up to p120 |
| 18 | Thu Apr 25 | Equivalence of CFGs and PDAs, II | 2.2 |
| 19 | Fri Apr 26 | Pumping lemma for CFLs; applications | 2.3 |
| 20 | Mon Apr 29 | CFL wrap-up; Turing Machines; examples; formal definition | 3.1; Simulators [1], [2], [3] |
| S | Tue Apr 30 | Midterm exam due by 22:00:00 | |
| 21 | Wed May 01 | Multi-tape TMs; Equivalence with single-tape TMs | Slides; 3.2 up to p178 |
| 22 | Thu May 02 | Nondeterministic TMs; The RAM model; Church-Turing Thesis | Slides; 3.2, 3.3 |
| 23 | Fri May 03 | Enumerator TMs; Connections with deciders/recognizers | 3.2 |
| 24 | Mon May 06 | Decision problems for major language classes: ADFA, ACFG, ATM; Undecidability | 4.1 |
| S | Tue May 07 | Homework 5 due by 22:00:00 | |
| 25 | Wed May 08 | More decision problems: EX, ALLX, EQX, INTX; Undecidability and unrecognizability | 4.2 |
| 26 | Thu May 09 | Reductions, mapping reductions, and their applications | 5.1 up to p220, 5.3 |
| 27 | Fri May 10 | Time complexity; P and NP | 7.1, 7.2, 7.3 |
| Q | Mon May 13 | Quiz 2: closed notes, in class | |
| S | Tue May 14 | Homework 6 due by 22:00:00 | |
| 28 | Wed May 15 | NP-completeness and polynomial time reductions (intro) | Slides; 7.4 to p304, 7.5 to p318 |
| 29 | Thu May 16 | NP-completeness of SAT (without proof), 3-SAT, IND-SET | Slides; 7.5 |
| 30 | Fri May 17 | NP-completeness of CLIQUE, UHAMCYCLE, TSP | 7.5 |
| 31 | Mon May 20 | NP-completeness of 3-COL; Tractability of 2-COL and 2-SAT | 7.5 |
| S | Tue May 21 | Homework 7 due by 22:00:00 | |
| 32 | Wed May 22 | Computational tableaux | |
| 33 | Thu May 23 | Undecidability of INTCFG; Unrecognizability of ALLCFG | 5.1 |
| 34 | Fri May 24 | Proof of the Cook-Levin theorem | 7.4 |
| H | Mon May 27 | Memorial day | |
| S | Tue May 28 | Homework 8 due by 22:00:00 | |
| 35 | Wed May 29 | Wrap up |
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.