15-453 Handouts
Date Lecture Slides Additional Readings and Notes
Tue Jan 13 [ppt] [pdf] Intro Chapter 0 and Section 1.1
Thu Jan 15 [ppt] [pdf] Section 1.2
Tue Jan 20 Pumping Lemma (using slides from last class)  
Thu Jan 22 [ppt] Converting between NFAs and regular expressions Section 1.3
Tue Jan 27 [ppt] Sections 2.1 and 2.2
Thu Jan 29 [pptx] [ppt] Sections 2.1 and 2.2
Tue Feb 3 Constructing minimal DFAs (using previous lecture's slides)
Thu Feb 5 OBBDs as minimal DFAs.
The Myhill-Nerode Theorem.
Lectures notes on BDDs
Myhill-Nerode Theorem
Handout on the Myhill-Nerode Theorem
Thu Feb 10 Myhill-Nerode Theorem.
Two-way DFAs.
Nerode Handout 2
Nerode Handout 3
Two-way DFA handout
Thu Feb 12 Two-way DFAs.
Tue Feb 17 Lecture5x.ppt. Context-free languages, push-down automata.
Thu Feb 20 continued
Tue Feb 24 Younger's Algorithm for parsing strings in a CFG. Handout on Younger's Algo
Thu Feb 26 Equivalence of CFGs and PDAs.
Tue Mar 3 Midterm Exam
Thu Mar 5 Turing machines; busy-beaver function. Handout on Turing machines.
Tue Mar 17 Turing machines; busy-beaver function. Second handout on Turing machines.
http://en.wikipedia.org/wiki/Busy_beaver www.logique.jussieu.fr/~michel/ha.html
Thu Mar 19 Lecture7x.ppt
Tue Mar 24 Lecture9x.ppt
Thu Mar 26 Lecture9x.ppt continued.
Tue Mar 31 Lecture10x.ppt
Thu Apr 2 Lecture11.pptx [as a PPT]
Tue Apr 7 Lecture15x.ppt [ pdf ]
Thu Apr 9 Handout on Cook's Theorem
Tue Apr 14 More on NP Complete Problems
Thu Apr 16 No class; CMU Spring Carnival.
Tue Apr 21 Propositional logic and SAT Solvers. slides GRASP Tech Report
Thu Apr 23 Sudoku Encoding Slides (ppt). Handout (pdf). For notes regarding the Tseitin transformation, see the "Final Exam" section on the Assignments page.
Tue Apr 28 GRASP slides (ppt) [ pdf ] Chaff (not covered on the exam): paper (pdf), slides (ppt)