CS 21: Decidability and Tractability (Winter 2025)

Instructor: Chris Umans

• Ricardo Garcia
• Ryan Hu
• Emily Parnell
• Nilo Rivera
• Allison Xin

Ombudspeople: TBD

Office: Annenberg 311

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

Office hours:

• Monday 7-8pm Annenberg 121 (Nilo)
• Monday 8-9pm Annenberg 121 (Ricardo)
• Tuesday 3-4pm Annenberg 311 (Chris)
• Tuesday 7-8pm Annenberg 121 (Allison)
• Tuesday 8-9pm Annenberg 121 (Emily)
• Tuesday 9-10pm Annenberg 121 (Ryan)

Announcements:

• Class on Wednesday February 12th is moved to Beckman Institute Auditorium, due to a special event in Annenberg.
• The 4th problem set has been posted. It is due Wednesday, February 19th.
• The third solution set and the midterm solutions have been posted.

Handouts:

• Syllabus (pdf)

Lecture Slides: posted after each lecture

• Lecture 1: Introduction, Problems and Languages (pptx, pdf) [p. 1-28]
• Lecture 2: Finite Automata, Nondeterministic Finite Automata (pptx, pdf) [p. 29-52]
• Lecture 3-4: DFA/NFA equivalence, regular expressions, regular expressions and finite automata equivalence; non-regular languages and the Pumping Lemma (pptx, pdf) [p. 53-82]
• Lecture 5: proof of Pumping Lemma, Pushdown Automata, Context-Free Grammars (pptx, pdf) [p. 111-116, 101-105]
• Lecture 6: Context-Free Grammars, NPDA and CFG equivalence (pptx, pdf) [p. 106-108]
• Lecture 7: NPDA and CFG equivalence, CFL pumping lemma (pptx, pdf) [p. 106-108, 117-129]
• Lecture 8: Chomsky Normal form, algorithm for deciding CFLs, Deterministic CFLs (pptx, pdf) [p. 108-110, 130-134]
• Lecture 9: Deterministic CFLS, Turing Machines, Turing machines, decidable and RE languages (pptx, pdf)
• Lecture 10: multitape and nondeterministic TMs, Church-Turing Thesis, recursive enumerability (pptx, pdf) [p. 165-182]
• Lecture 11: countable and uncountable sets, the Halting Problem, undecidability of HALT, reductions (pptx, pdf) [p. 176-188, 193-207]
• Lecture 12: reductions, many-one reductions (pptx, pdf) [p. 209-210]
• Lecture 13: reductions based on computation histories (pptx, pdf) [p. 216-218, 234-237]
• Lecture 14: reductions based on computation histories (cont'd), Rice's Theorem, PCP, beyond RE and co-RE (pptx, pdf) [p. 219-234, 238, 245-252]
• Lecture 15: Recursion Theorem, Godel Incompleteness Theorem (pptx, pdf) [p. 245-252]
• Lecture 16: finishing Godel Incompleteness Theorem, intro to complexity (pptx, pdf)
• Lecture 17: problems in P (pptx, pdf) [p. 368-371]

Problem Sets and Exams:

• Problem Set 1: (LaTeX source, pdf) Solutions: (pdf)
• Problem Set 2: (LaTeX source, pdf) Solutions: (pdf)
• Problem Set 3: (LaTeX source, pdf) Solutions (pdf)
• Midterm: (LaTeX source, pdf) Solutions (pdf)
• Problem Set 4: (LaTeX source, pdf)