CS 21: Decidability and Tractability (Winter 2018)
Office: Annenberg 311
Times: MWF 1:00-1:55 in Annenberg 105
- 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)
- 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"
- 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
pdf) [p. 115-127]
Video recording of some lectures from 2015 available here. Recording quality is poor, unfortunately.
Problem Sets and Exams: