CS 21: Decidability and Tractability
Instructor: Chris
Umans
TAs:
Ombudsperson: Chris Kennelly
Office: Jorgensen 286
Times: MWF 1:00-1:55 in Jorgensen 74
Office hours: TBD
- Tuesday 3-4pm in Jorgensen 286 (Chris)
- Tuesday 4-5pm in VLSI Lab (=JRG 154) (Ila)
- Tuesday 7-8pm in VLSI Lab (=JRG 154) (William)
- Tuesday 8-9pm in VLSI Lab (=JRG 154) (Fedor)
Announcements:
- Packets of graded material (including final grades for the
course) may be picked up from Diane Goodfellow in Jorgensen 266,
starting 3/26/08.
- The solutions for the final, midterm and all problem sets are posted.
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-62]
- Lecture 3: Regular Expressions, FAs and Regular Expressions,
Pumping Lemma and non-regular languages (ppt, pdf) [p. 62-82]
- Lecture 4: NPDAs and Context Free Grammars (ppt, pdf) [p. 109-114, 99-102]
- Lecture 5: parse trees, ambiguity, Chomsky Normal Form, NPDAs and CFGs (ppt, pdf) [p. 103-109, 115-120]
- Lecture 6: NPDAs and CFGs, Pumping Lemma for CFLs and
non-context-free languages, Deterministic CFLs (ppt, pdf) [p. 121-127]
- Lecture 7: Deterministic CFLs, deciding CFLs, Turing Machines (ppt, pdf)
- Lecture 8: Turing Machines, multi-tape TMs, NTMs (ppt, pdf) [p. 137-150]
- Lecture 9: NTMs, Church-Turing Thesis, recursive enumerability,
undecidable languages (ppt, pdf) [p. 151-159, 174-179]
- Lecture 10: the Halting Problem, a non-RE language, reductions,
undecidable problems (ppt, pdf) [p. 179-182, 187-190]
- Lecture 11: many-one reductions,
undecidable and undecidable problems (ppt, pdf) [p. 206-210, 190-196, 171-172]
- Lecture 12: reductions based on computation histories, Rice's
Theorem, PCP (ppt, pdf) [p. 197-198, 199, 205]
- Lecture 13: PCP, a natural non-RE and non-coRE language,
Recursion Theorem (ppt, pdf) [p. 200-204, 210, 117-223]
- Lecture 14: Godel Incompleteness Theorem (ppt, pdf)
- Lecture 15: asymptotic and worst-case analysis, time complexity,
the class P (ppt, pdf) [p. 247-258]
- Lecture 16: Euclid's algorithm, 2SAT in P, the class EXP, Time
Hierarchy Theorem (ppt, pdf) [p. 261, 341-342]
- Lecture 17: poly-time reductions, hardness and
completeness, an EXP-complete problem, the class NP, an NP-complete problem
(ppt, pdf) [p. 272-273, 264-267]
- Lecture 18: alternative characterization of NP, Cook-Levin theorem (ppt, pdf) [p. 351-360]
- Lecture 19: NP-complete problems: Independent Set, Vertex Cover, Clique,
Ham. Path (ppt, pdf) [p. 351-360, 274-275]
- Lecture 20: NP-complete problems: directed/undirected Hamilton
path/cycle, TSP (ppt, pdf) [p. 286-291]
- Lecture 21: NP-complete problems: Subset Sum, a scheduling
problem, NAE-3-SAT, Max Cut (ppt, pdf) [p. 292-294]
- Lecture 22: the class coNP, coNP-complete problems, NP intersect
coNP, factoring + primes in NP intersect coNP (ppt, pdf)
- Lecture 23: the class PSPACE, a PSPACE-complete problem, 2-player
games, Generalized Geography (ppt, pdf) [p. 308-320]
- Lecture 24: cancelled due to Student Experience Conference.
- Lecture 25: randomness in communication complexity, randomized
complexity classes (ppt, pdf)
- Lecture 26: polynomial identity testing, the power of randomness,
a model for quantum computation (ppt, pdf)
- Lecture 27: quantum complexity, 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 22.7)
- Problem Set 3 (pdf) Solutions (pdf) (pts:21; mean 17.0)
- Midterm (pdf) Solutions (pdf) (pts:30; mean 23.8)
- Problem Set 4 (pdf) Solutions (pdf) (pts:14; mean 12.5)
- Problem Set 5 (pdf) Solutions (pdf) (pts:15; mean 12.9)
- Problem Set 6 (pdf) Solutions (pdf) (pts:15; mean 12.3)
- Problem Set 7 (pdf) Solutions (pdf) (pts:12; mean 10.4)
- Final (pdf) Solutions (pdf) (pts:30; mean 22.0)