**CS 21: Decidability and Tractability (Winter 2018)**

Instructor: Chris Umans

TAs:- Vivek Bharadwaj
- Jesse Cai
- Victor Chen
- Bhairav Chidambaram
- Surya Mathialagan
- Noah Nelson
- Gregory Rassolov
- Sean Yu

Ombudspeople: TBD

Office: Annenberg 311

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

Office hours:

- Monday 7-8pm in Annenberg 105 (Sean)
- Monday 8-9pm in Annenberg 105 (Bhairav)
- Monday 9-10pm in Annenberg 105 (Jesse)
- Monday 10-11pm in Annenberg 105 (Gregory)
- Tuesday 2-3pm in Annenberg 311 (Chris)
- Tuesday 7-8pm in Annenberg 106 (Victor)
- Tuesday 8-9pm in Annenberg 105 (Vivek)
- Tuesday 9-10pm in Annenberg 105 (Surya)
- Tuesday 10-11pm in Annenberg 105 (Noah)

Announcements:

- Solution set 1 has been posted.
- The second problem set has been posted.
- If you are thinking of adding the course, please complete the problem sets so you are not behind! No extension for PS2 or later will be granted on the basis of adding the course "late"

Handouts:

- Syllabus (pdf)

Lecture Slides:

- Lecture 1: Introduction, Problems and Languages, Finite Automata (ppt, pdf) [p. 1-31]
- Lecture 2: Finite Automata, Nondeterministic Finite Automata, closure under regular operations, DFA/NFA equivalence (ppt, pdf) [p. 31-63]
- Lecture 3: regular expressions, regular expression and FA equivalence, the pumping lemma and non-regular languages (ppt, pdf) [p. 63-76]
- Lecture 4: the pumping lemma and non-regular languages, pushdown automata (ppt, pdf) [p. 77-82, 111-115]
- Lecture 5: Context-Free Grammars, Parse trees (ppt, pdf) [p. 101-105]
- Lecture 6: NPDA and CFG equivalence, non-context free languages, proof of Pumping Lemma for CFLs (ppt, pdf) [p. 115-127]

Video recording of some lectures from 2015 available here. Recording quality is poor, unfortunately.

Problem Sets and Exams:

- Problem Set 1: (LaTeX source, pdf) Solutions: (pdf)
- Problem Set 2: (LaTeX source, pdf)