CS 21: Decidability and Tractability (Winter 2012)

Instructor: Chris Umans

• Martin Michelsen
• Ilya Nepomnyashchiy
• Haoyang Ren
• Ben Weitz
• Shiyu Zhao

Ombudspeople: Benjamin Hu, Eric Martin, Jessica Su

Office: Annenberg 311

Times: MWF 1:00-1:55 in Annenberg 105

Office hours:

• Mondays (7-8) in Annenberg 107 (Haoyang)
• Mondays (8-9) in Annenberg 107 (Shiyu)
• Tuesdays (4-5) in Annenberg 311 (Chris)
• Tuesdays (8-9) in Annenberg 107 (Ilya)
• Tuesdays (9-10) in Annenberg 107 (Ben)
• Tuesdays (10-11) in Annenberg 107 (Martin)

Announcements:

• Problem Set 4 has been posted; it is due Feb 15 at the beginning of class.

Handouts:

• Syllabus (pdf)

Lecture Slides:

• Lecture 1: Introduction, Problems and Languages (ppt, pdf) [p. 1-28]
• Lecture 2: Finite Automata, Nondeterministic Finite Automata, closure under regular operations (ppt, pdf) [p. 29-54,58-63]
• Lecture 3: NFA and FA equivalence, regular expressions, regular expression and FA equivalence (ppt, pdf) [p. 54-58, 64-72]
• Lecture 4: regular expression and FA equivalence continued, the pumping lemma and non-regular languages (ppt, pdf) [p. 73-82]
• Lecture 5: Pushdown automata, Context-Free Grammars (ppt, pdf) [p. 99-103, 109-114]
• Lecture 6: Context-Free Grammars, parse trees, ambiguity, Chomsky Normal Form, NPDA and CFG equivalence (ppt, pdf) [p. 103-109, 115-118]
• Lecture 7: NPDA and CFG equivalence, Pumping Lemma for CFLs and non-context-free languages (ppt, pdf) [p. 118-127]
• Lecture 8: deterministic CFLs, closure of DCFLs under complement, deciding CFLs (CKY algorithm) (ppt, pdf)
• Lecture 9: Turing Machines, decidable and RE languages (ppt, pdf) [p. 137-147]
• Lecture 10: multi-tape TMs, nondeterministic TMs, Church-Turing thesis, recursive enumerability (ppt, pdf) [p. 142-159]
• Lecture 11: undecidable (and non-RE) languages, the Halting Problem, co-RE, a natural non-RE language, reductions (ppt, pdf) [p. 152-153, 173-182]
• Lecture 12: reductions, many-one reductions, undecidable languages (ppt, pdf) [p. 187-191, 206-210]
• Lecture 13: decidable and undecidable problems, reductions based on computation histories, Rice's Theorem (ppt, pdf) [p. 192-198]
• Lecture 14: a non-RE and non-co-RE language, Recursion Theorem, Godel Incompleteness Theorem (ppt, pdf) [p. 210, 217-224]
• Lecture 15: proof of Godel Incompletness Theorem, summary of "part II" (ppt, pdf)
• Coming up: [p. 247-255]

Problem Sets and Exams:

• Problem Set 1: (LaTeX source, pdf) Solutions: (pdf) (pts: 24; mean: 19.6; median 21)
• Problem Set 2: (LaTeX source, pdf) Solutions: (pdf) (pts: 24; mean: 19.4; median 20.5)
• Problem Set 3: (LaTeX source, pdf) Solutions: (pdf) (pts: 24; mean: 18.3; median 19.0)
• Midterm: (LaTeX source, pdf) Solutions: (pdf)
• Problem Set 4: (LaTeX source, pdf)