CS 21: Decidability and Tractability (Winter 2009)
Instructor: Chris
Umans
TAs:
Ombudsperson: Sasha Boulgakov
Office: Jorgensen 286
Times: MWF 1:00-1:55 in Jorgensen 74
Office hours:
- Tuesday 3-4pm in Jorgensen 286 (Chris)
- Tuesday 7-8pm in VLSI Lab (=JRG 154) (William)
- Tuesday 8-9pm in VLSI Lab (=JRG 154) (Ben)
- Tuesday 9-10pm in VLSI Lab (=JRG 154) (Abhi)
Announcements:
- Solutions for the final (and all problem sets) are now
posted. Packets of graded material and final grades for the course are
available for pickup from Diane Goodfellow, in JRG 266.
Handouts:
Lecture Slides:
- Lecture 1: Introduction, Languages, Finite Automata (ppt, pdf)
[p. 1-43]
- Lecture 2: Nondeterministic Finite Automata, closure
under regular operations, NFAs and FAs (ppt, pdf)
[p. 44-64]
- Lecture 3: Regular Expressions, equivalence of FAs and Regular
Expressions, non-regular languages via the Pumping Lemma (ppt, pdf)
[p. 64-82]
- Lecture 4: proof of Pumping Lemma, NPDAs and Context Free
Grammars (ppt, pdf) [p. 109-114, 99-102]
- Lecture 5: CFGs, parse trees, ambiguity, Chomsky Normal Form, NPDA and
CFG equivalence (ppt, pdf) [p. 103-109,
115-118]
- Lecture 6: NPDA and CFG equivalence (continued), Pumping Lemma
for CFLs and non-context-free languages (ppt, pdf) [p. 118-127]
- Lecture 7: Pumping Lemma proof, deterministic PDAs (ppt, pdf)
- Lecture 8: finishing deterministic PDAs, deciding CFLs, Turing Machines (ppt, pdf) [p. 137-139]
- Lecture 9: Turing Machines, multi-tape Turing Machines,
nondeterministic TMs (ppt, pdf) [p. 139-150]
- Lecture 10: NTMs, Church-Turing Thesis, recursive enumerability,
undecidable languages (ppt, pdf) [p. 151-159, 174-179]
- Lecture 11: cancelled
- Lecture 12: the Halting Problem, undecidability, co-RE, a non-RE language, reductions (ppt, pdf) [p. 179-182, 187-190]
- Lecture 13: many-one reductions, undecidable and undecidable
problems, reductions based on computation histories (ppt, pdf) [p. 206-210, 190-196]
- Lecture 14: undecidable and undecidable
problems, Rice's Theorem, a natural non-RE and non-co-RE language (ppt, pdf) [p. 171,
197-198, (199-205), 210]
- Lecture 15: the Recursion Theorem, Godel Incompleteness Theorem (ppt, pdf) [p. 217-223]
- Lecture 16: Godel Incompleteness Theorem continued, asymptotic
and worst-case analysis (ppt, pdf) [p. 247-248]
- Lecture 17: asymptotic and worst-case analysis, time complexity,
the class P, Euclid's algorithm (ppt, pdf) [p. 248-255, 256-262]
- Lecture 18: 2SAT in P, the class EXP, Time Hierarchy Theorem,
poly-time reductions, hardness and completeness (ppt, pdf) [p. 341-342,
272-273]
- Lecture 19: an EXP-complete problem, the class NP, an NP-complete
problem, alternative characterization of NP (ppt, pdf) [p. 264-267]
- Lecture 20: Cook-Levin Theorem (3SAT is NP-complete); search
vs. decision; Independent Set is NP-complete (ppt, pdf) [p. 351-360]
- Lecture 21: NP-complete problems: vertex-cover, clique, directed
and undirected Hamilton path (ppt, pdf) [p. 274-275, 286-291]
- Lecture 22: NP-complete problems: travelling salesperson problem,
subset sum, a scheduling problem (ppt, pdf) [p. 292-294]
- Lecture 23: NP-complete problems: NAE-3-SAT, max cut; the class coNP (ppt, pdf)
- Lecture 24: coNP vs. NP, the class NP intersect coNP, factoring
in NP intersect coNP, the class PSPACE, QSAT (ppt, pdf) [p. 308-311]
- Lecture 25: QSAT is PSPACE-complete, PSPACE and games,
communication complexity of EQ (ppt, pdf) [p. 312-320]
- Lecture 26: randomness in communication complexity, polynomial
identity testing, the power of randomness (ppt, pdf)
- Lecture 27: quantum computation, Shor's factoring algorithm,
course summary and review (ppt, pdf)
Problem Sets and Exams:
- Problem Set 1 (pdf) Solutions (pdf) (pts: 24; mean: 20.6)
- Problem Set 2 (pdf) Solutions (pdf) (pts: 27; mean: 23.6)
- Problem Set 3 (pdf) Solutions (pdf) (pts: 21; mean: 17.1)
- Midterm (pdf) Solutions (pdf) (pts: 30; mean 24.7)
- Problem Set 4 (pdf) Solutions (pdf) (pts: 9; mean 7.5)
- Problem Set 5 (pdf) Solutions (pdf) (pts: 14; mean 13)
- Problem Set 6 (pdf) Solutions (pdf) (pts: 15; mean 13.4)
- Problem Set 7 (pdf) Solutions (pdf) (pts: 12; mean 9.7)
- Final (pdf) Solutions (pdf) (pts: 30; mean 22.6)