The table specifies the topics we will cover in each week. Make sure to read the relevant sections of the text
for a given week. Read as much as possible before you
come to class and lab.
Summaries of the most important definitions and theorems can
be found here.
| 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 |