| Week | Topic of the Week | Readings | Dates |
|---|
| - Introduction and overview; administrivia; math review
| | 9/5 |
| - Strings and languages; finite automata: formal definition and state transition diagrams
- Regular languages; combining languages; closure properties
| - Sipser 0, 1.1, FA-Formal-Definitions.pdf
- Sipser 1.1
| 9/10, 12 |
| - Nondeterminism; equivalence of NFAs and DFAs; closure properties
- Regular operations; regular expressions
| - Sipser 1.2, FA-Formal-Definitions.pdf
- Sipser 1.3
| 9/17, 19 |
| - Equivalence of regular expressions and FA
- Nonregular languages: Pumping Lemma
| - Sipser 1.3
- Sipser 1.4, Pumping-Lemma-Reg-Langs.pdf
| 9/24, 26 |
| - Application of Pumping Lemma and closure properties
- Context-free languages; context-free grammars; parse trees; ambiguity
| | 10/1, 3 |
| | | 10/10 |
| - Pushdown automata
- Equivalence of CFLs and PDAs
| - Sipser 2.2, Pushdown-Automata.pdf
- Sipser 2.2
| 10/15, 17 |
| - Pumping Lemma for CFLs; closure properties; non-context-free languages
- Turing machines: state diagrams; decidable and Turing-recognizable languages
| - Sipser 2.3, Pumping-Lemma-CFLs.pdf
- Sipser 3.1, TM-Examples.pdf, Deciders-vs-Recognizers.pdf
| 10/22, 24 |
| - Turing machine variants: multi-tape and nondeterministic
- Closure properties; Church-Turing thesis
| - Sipser 3.2, TM-Variants.pdf
- Sipser 3.3
| 10/29, 31 |
| - Exam 2
- Decision problems; decidability
| - Review
- Sipser 3.3, 4.1, Decision-Problems.pdf, Decidability-Results.pdf
| 11/5, 7 |
| - Countable and uncountable sets; more languages than TMs
| | 11/14 |
| - Undecidability, Halting Problem, mapping reductions
- Time complexity
| - Sipser 4.2, 5.1, 5.3, Undecidability-Results.pdf, SchemeMappingReductionDemos
- Sipser 7.1, Time-Complexity.pdf
| 11/19 |
| - P and NP
- Polytime reductions, NP-Completeness
| - Sipser 7.2, 7.3, P-and-NP.pdf, P-Examples.pdf, NP-Examples.pdf
- Sipser 7.4, NP-Completeness.pdf
| 11/26, 28 |
| | | 12/3, 5 |