Future dates are estimates, and may vary.
Entries for past dates may have been updated to match reality.
All section and page references are from Sipser. The related end-of-chapter
exercises form part of the reading, even if not given explicitly.
- Thurs., Jan. 5
- Course overview, including a bit of history; formal definition of strings.
Associated readings: Prefaces and Ch. 0, pp. xi–28.
- Tues., Jan. 10
- Formal languages; finite automata.
Readings: Section 1.1, pp. 29–43.
- Thurs., Jan. 12
- Regular expressions. Non-deterministic automata; their equivalence to
deterministic automata.
Readings: Sections 1.1–1.3, pp. 29–65.
- Tues., Jan. 17
- Every finite automaton has a corresponding regular expression.
Non-regular languages and the "pumping lemma".
Readings: Sections 1.3 and 1.4, pp. 58–81.
- Thurs., Jan. 19
- Proving languages non-regular, cont'd.
Introduction to context-free grammars: examples; normal forms; ambiguity.
Readings: Notes on (mis-)use of the pumping
lemma (originally prepared by Jeff Shallit).
Section 1.4 and 2.1, pp. 66–108.
- Tues., Jan. 24
- Further examples of context-free grammars and ambiguity.
Parsing CFLs via pushdown automata.
Readings: Section 2.2, pp. 106–118
- Thurs., Jan. 26
- Converting PDAs to CFGs. Closure properties for CFLs.
Non-context-free languages: another pumping lemma.
Readings: Sections 2.2–3, pp. 119–134.
- Tues., Jan. 31
- Proof of the CFL pumping lemma. Additional examples of non-CFLs.
Survey of additional topics on CFLs (e.g., deterministic
PDAs and the DCFLs.)
Readings: Section 2.3, pp. 123–134.
- Thurs., Feb. 2
- The Turing machine model: definitions and basic examples. Variants
on the model.
Readings: Section 3.1, pp. 135–147.
- Tues., Feb. 7
- Multi-tape Turning machines. The Church-Turing thesis.
Nondeterministic Turing machines. Enumeration of a language.
Readings: Sections 3.2–3, pp. 148–159.
- Thurs., Feb. 9
-
Decidable problems about regular and context-free languages;
Diagonalization and undecidable languages.
Readings: Chapter 4, pp. 165–182.
- Tues., Feb 14, and
Thurs., Feb. 16
- More on undecidable languages. Reductions among languages.
Readings: Chapter 5, pp. 187–215.
- Tues., Feb 21 and
Thurs., Feb. 23
- READING WEEK: no lectures
Possible reading: Stanisław Lem, The Cyberiad: Fables for
the cybernetic age (tr. M. Kandel), 1974.
- Tues., Feb. 28
- Time complexity; the classes P and NP.
Space complexity.
Readings: Sections 7.1–7.3, pp. 247–270; Sections 8.0,
8.1, pp. 303–307.
- Thurs., Mar. 1
- MIDTERM EXAM (in class)
Reading: Chapters 1–5, pp. 1–215.
- Tues., Mar. 6
- Single-tape vs. multi-tape Turing machines the example of
palindromes.
- Thurs., Mar. 8
- Verification of languages.
- Tues., Mar. 13
- The Cook-Levin theorem.
- Thurs., Mar. 15
- Polynomial-time reductions and NP-completeness. Examples:
Hamiltonian cycle.
- Tues., Mar. 20
- PSPACE-complete problems.
The Immerman-Szelepcsényi theorem.
Readings: Sections 8.2–6, pp. 308–327.
- Thursday, March 22
- Randomized computation; RP and BPP; the Schwartz-Zippel lemma
and polynomial identity testing.
Readings: from Section 10.2: pp. 368–370, 375–380.
- Tuesday, March 27 and
Thursday, March 29
- Interactive proof systems; IP = PSPACE.
Overview of some further topics.
Readings: Section 10.4, pp. 387–399.