CS172 Computability and Complexity (Spring'09)
Mihai replaced Bill
Steiger.
[Home]
[Lectures]
[Assignments]
Lectures
- Jan. 21 — Bureaucracy and overview of the course.
- Jan. 26 — Deterministic finite automata. Regular languages
(Sipser 1.1)
- Jan. 28 — Closure under regular operations. Non-determinism.
NFAs recognize regular languages (Sipser 1.2)
- Feb. 4 — NFA equivalence with DFA. Regular expressions
(Sipser 1.3).
- Feb. 9 — Equivalence of regular expressions and finite
automata.
- Feb. 11 — Languages that are not regular. The pumping
lemma (Sipser 1.4)
- Feb. 18 — Myhill-Nerode theorem and DFA minimization.
Handout: Minimizing Finite Automata (from Fall
2004, courtesy of Alistair Sinclair)
- Feb. 23 — Pattern matching. [Knuth-Morris-Pratt] and
[Boyer-Moore].
- 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]
- 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.)
- Mar. 4 — Entropy and one-way communication lower bound for
indexing. Context free grammars.
- Mar. 9 — Parsing by dynamic programming. The
Earley parser.
The Church-Turing thesis. Equivalence of Turing machines and the Word RAM.
- Mar. 11 — Countable and uncountable sets. Diagonalization. A
language not recognized by Turing machines.
- Mar. 16 — Midterm.
Sample midterm.
- Mar. 18 — Midterm discussion.
- Mar. 30 — The halting problem. Many undecidable problems
shown via reduction. LBAs.
- Apr. 1 — Natural undecidable problems: making a rectangle
out of Wang
tiles; determining whether a context-free grammar generates all
strings.
- Apr. 6 — Gödel's incompleteness. Hilbert's 10th
problem. Gödel's letter to von Neumann. Definition of NP, coNP.
- Apr. 8 — Backtracking; dynamic programming. Polynomial-time
reductions. SAT, 3SAT.
- Apr. 13 — Reductions between Set-Cover and SAT. CircuitSAT
is as hard as SAT. CircuitSAT is NP-complete (Cook-Levin).
- Apr. 15 — Cook-Levin. Subset-Sum.
- Apr. 20 — Hamiltonian-Path. PSPACE. Two-player games; minimax.
- Apr. 22 — Savitch's theorem. QBF is PSPACE-complete.
- Apr. 27 — Final exam. Sample exam.
- Apr. 29 — Geography is PSPACE-complete. L, NL.
Space/time trade-offs.
- May 4 — Hierarchy theorems. Relativization and P vs NP.
- May 6 — Fixed-parameter tractability. k-SUM; hardness from SAT.
- May 11 — Inapproximability.