CS172 Computability and Complexity (Spring'09)

Instructor: Mihai Pătraşcu     GSI: Omid Etesami

Mihai replaced Bill Steiger.


[Home] [Lectures] [Assignments]

Lectures

  1. Jan. 21 — Bureaucracy and overview of the course.

  2. Jan. 26 — Deterministic finite automata. Regular languages (Sipser 1.1)

  3. Jan. 28 — Closure under regular operations. Non-determinism. NFAs recognize regular languages (Sipser 1.2)

  4. Feb. 4 — NFA equivalence with DFA. Regular expressions (Sipser 1.3).

  5. Feb. 9 — Equivalence of regular expressions and finite automata.

  6. Feb. 11 — Languages that are not regular. The pumping lemma (Sipser 1.4)

  7. Feb. 18 — Myhill-Nerode theorem and DFA minimization.
    Handout: Minimizing Finite Automata (from Fall 2004, courtesy of Alistair Sinclair)

  8. Feb. 23 — Pattern matching. [Knuth-Morris-Pratt] and [Boyer-Moore].

  9. Feb. 25 — Streaming algorithms. Majority element. Estimating the second moment.
    Slides by Piotr Indyk. (Note: In lecture, we used normally distributed hash codes, not codes in {-1,1}. This saved us some technical details.) Gödel Prize citation for [Alon-Matias-Szegedy]

  10. Mar. 2 — Communication complexity. Reduction from indexing to deciding whether a majority element exists. Reduction showing Ω(1/ɛ2) lower bound for second moment.
    Slides by Piotr Indyk. (The presentation in class was somewhat different.)

  11. Mar. 4 — Entropy and one-way communication lower bound for indexing. Context free grammars.

  12. Mar. 9 — Parsing by dynamic programming. The Earley parser. The Church-Turing thesis. Equivalence of Turing machines and the Word RAM.

  13. Mar. 11 — Countable and uncountable sets. Diagonalization. A language not recognized by Turing machines.

  14. Mar. 16 — Midterm. Sample midterm.

  15. Mar. 18 — Midterm discussion.

  16. Mar. 30 — The halting problem. Many undecidable problems shown via reduction. LBAs.

  17. Apr. 1 — Natural undecidable problems: making a rectangle out of Wang tiles; determining whether a context-free grammar generates all strings.

  18. Apr. 6 — Gödel's incompleteness. Hilbert's 10th problem. Gödel's letter to von Neumann. Definition of NP, coNP.

  19. Apr. 8 — Backtracking; dynamic programming. Polynomial-time reductions. SAT, 3SAT.

  20. Apr. 13 — Reductions between Set-Cover and SAT. CircuitSAT is as hard as SAT. CircuitSAT is NP-complete (Cook-Levin).

  21. Apr. 15 — Cook-Levin. Subset-Sum.

  22. Apr. 20 — Hamiltonian-Path. PSPACE. Two-player games; minimax.

  23. Apr. 22 — Savitch's theorem. QBF is PSPACE-complete.

  24. Apr. 27 — Final exam. Sample exam.

  25. Apr. 29 — Geography is PSPACE-complete. L, NL. Space/time trade-offs.

  26. May 4 — Hierarchy theorems. Relativization and P vs NP.

  27. May 6 — Fixed-parameter tractability. k-SUM; hardness from SAT.

  28. May 11 — Inapproximability.