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:

• The first problem set is out. It is due on Wednesday January 22 at 1pm.
• Office hours 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]

Problem Sets and Exams:

• Problem Set 1: (LaTeX source, pdf)