CS 21: Decidability and Tractability (Winter 2024)
Instructor: Chris
Umans
TAs:
Ombudspeople: TBD
Office: Annenberg 311
Times: MWF 1:00-1:55 in Annenberg 105
Office hours:
- Friday 5-6pm Annenberg 105 (Sulekha)
- Monday 7-8pm Annenberg 105 (Annika)
- Monday 8-9pm Annenberg 105 (Ricardo)
- Monday 9-10pm Annenberg 105 (Eileen)
- Tuesday 1-2pm Annenberg 311 (Chris)
- Tuesday 7-8pm Annenberg 105 (Andrei)
- Tuesday 8-9pm Annenberg 105 (Akshar)
- Tuesday 9-10pm Annenberg 105 (Sreeyutha)
- Tuesday 10-11pm Annenberg 105 (Catherine)
Announcements:
- The solutions to the final have been posted.
- Enjoy the break!
- Regrade request should go to the TAs first (and I will look at
them if they can't be resolved). All regrade requests should be made
within 2 weeks of the date the grades are released.
Handouts:
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: 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, CFL pumping lemma (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, reductions based on computation histories (pptx,
pdf) [p. 209-210, 216-218, 234-237]
- Lecture 14: reductions based on computation histories, Rice's
Theorem (pptx,
pdf) [p. 219-226]
- Lecture 15: PCP, beyond RE and co-RE, Recursion Theorem (pptx,
pdf) [p. 227-234, 238, 245-252]]
- Lecture 16: complexity classes, TIME(t(n)), 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, the class NP
(pptx,
pdf) [p. 292-295]
- Lecture 19: alternate characterization of NP,
Circuit-SAT is NP-complete, 3-SAT is NP-complete (pptx,
pdf) [p. 379-388]
- Lecture 20: NP-complete problems:
Search vs. Decision, Independent Set, Vertex Cover,
Clique, Hamilton path (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; PSPACE, QSAT (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, course review, quantum computation (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) Solutions (pdf)