CS 21: Decidability and Tractability (Winter 2023)

Instructor: Chris Umans

• Mohammedsaid Alhalimi
• Katelyn Chu
• Arushi Gupta
• Kimia Hassibi
• Sulekha Kishore
• Adam Krivka
• Eileen Li
• Damon Lin
• Sophie Piao
• Juan Quiroz

Ombudspeople: TBD

Office: Annenberg 311

Times: MWF 1:00-1:55 in Beckman Institute auditorium

Office hours:

• Friday 5-6pm Annenberg 105 (Sulekha)
• Monday 7-8pm Keck 142 (Damon)
• Monday 8-9pm Keck 142 (Arushi)
• Monday 9-10pm Annenberg 105 (Eileen)
• Tuesday 2-3pm Annenberg 311 (Chris)
• Tuesday 3-4pm STL 102 (Sophie)
• Tuesday 4-5pm Annenberg 105 (Mohammed)
• Tuesday 7-8pm Annenberg 106 (Kimia)
• Tuesday 8-9pm Annenberg 106 (Juan)
• Tuesday 9-10pm Annenberg 105 (Adam)
• Tuesday 10-11pm Annenberg 105 (Katy)

Announcements:

• Please see first slide of Lecture 21 for an important message from the BoC.
• The solutions to the final have been posted.
• Have a good Spring Break!

Handouts:

• Syllabus (pdf)

Lecture Slides:

• 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: DFA/NFA equivalence, regular expressions (pptx, pdf) [p. 53-65]
• Lecture 4: regular expressions and finite automata equivalence; non-regular languages and the Pumping Lemma (pptx, pdf) [p. 66-82]
• Lecture 5: non-regular languages and the Pumping Lemma, pushdown automata (pptx, pdf) [p. 111-116]
• Lecture 6: Pushdown Automata, Context-Free Grammars, CFG for balanced parentheses (pptx, pdf) [p. 111-116, 101-105]
• Lecture 7: NPDA and CFG equivalence (pptx, pdf) [p. 106-108, 117-129]
• Lecture 8: CFL pumping lemma, Chomsky Normal form, algorithm for deciding CFLS (pptx, pdf) [p. 108-110, 130-134]
• Lecture 9: Deterministic CFLS, Turing Machines (pptx, pdf)
• Lecture 10: Turing machines, decidable and RE languages, multitape and nondeterministic TMs (pptx, pdf) [p. 165-182]
• Lecture 11: Church-Turing Thesis, recursive enumerability, countable and uncountable sets (pptx, pdf) [p. 176-187]
• Lecture 12: the Halting Problem, undecidability of HALT, reductions (pptx, pdf) [p. 180-18, 193-207]
• Lecture 13: reductions, many-one reductions, (pptx, pdf) [p. 209-210, 216-218, 234-237]
• Lecture 14: reductions based on computation histories (pptx, pdf) [p. 219-226]
• Lecture 15: Rice's Theorem, PCP, beyond RE and co-RE, Recursion Theorem (pptx, pdf) [p. 227-234, 238, 245-252]]
• Lecture 16: finishing the Recursion Theorem, TIME(t(n)) complexity classes, the class P (pptx, pdf) [p. 275-292]
• Lecture 17: problems in P, 2-SAT in P (pptx, pdf) [p. 368-371]
• Lecture 18: the class EXP, hardness and completeness, an EXP-complete problem (pptx, pdf) [p. 292-295]
• Lecture 19: the class NP, alternate characterization of NP, Circuit-SAT is NP-complete (pptx, pdf) [p. 379-388]
• Lecture 20: NP-complete problems: 3-SAT is NP-complete, Search vs. Decision, Independent Set, Vertex Cover, Clique (pptx, pdf) [p. 311-319]
• Lecture 21: NP-complete problems: Hamilton cycle and path, TSP (pptx, pdf)
• Lecture 22: NP-complete problems: subset sum, NAE-3-CNF, max-cut (pptx, pdf)
• Lecture 23: the class NP intersect coNP, complexity of factoring (pptx, pdf) [p. 336-340]
• Lecture 24: QSAT is PSPACE-complete, PSPACE and 2-player games (pptx, pdf)
• Lecture 25: randomness in computation (pptx, pdf)
• Lecture 26: randomness in computation, quantum computation (pptx, pdf)
• Course Review: (pptx, pdf)
• Lecture 27: quantum computation, Shor's factoring algorithm (pptx, pdf)

Lecture recordings from a past year: here

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) Solutions (pdf)
• Problem Set 5: (LaTeX source, picture, pdf) Solutions (pdf)
• Problem Set 6: (LaTeX source, pdf) Solutions: (pdf)
• Problem Set 7: (LaTeX source, pdf) Solutions: (pdf)
• Final: (LaTeX source, pdf) (pdf)