 |
 |
||
|
|
|
|
 |
 |
|
|
|
|
|
 |
 |
|
|
|
|
|
 |
||
|
|
||
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. |
BBDs 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) |