Lecture Slides
| No | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 21.2. | screen print4 print1 |
| A2 | Mathematical Foundations | 21.2. | screen print4 print1 |
| A3 | Proof Techniques | 23.2. | screen print4 print1 |
| B1 | Finite Automata | 28.2. | screen print4 print1 |
| B2 | Grammars | 14.3. | screen print4 print1 |
| B3 | Regular Languages | 16.3. | screen print4 print1 |
| B4 | Regular Languages: Closure & Decidability | 21.3. | screen print4 print1 |
| B5 | Regular Languages: Regular Expressions | 23.3. | screen print4 print1 |
| B6 | Regular Languages: Pumping Lemma | 30.3. | screen print4 print1 |
| B7 | Context-free Languages: epsilon-Rules and Chomsky Normal Form | 4.4. | screen print4 print1 |
| B8 | Context-free Languages: PDAs | 4.4. | screen print4 print1 |
| B9 | Context-free Languages: Closure & Decidability | 6.4. | screen print4 print1 |
| B10 | Turing Machines I | 11.4. | screen print4 print1 |
| B11 | Turing Machines II | 13.4. | screen print4 print1 |
| B12 | Type-1 and Type-0 Languages: Closure & Decidability | 20.4. | screen print4 print1 |
| C1 | Turing Machines as Formal Model of Computation | 25.4. | screen print4 print1 |
| C2 | The Halting Problem | 25.4. | screen print4 print1 |
| C3 | Turing-Computability | 2.5. | screen print4 print1 |
| C4 | Reductions | 4.5. | screen print4 print1 |
| C5 | Rice's Theorem | 9.5. | screen print4 print1 |
| D1 | Nondeterministic Algorithms, P and NP | 11.5. | screen print4 print1 |
| D2 | Polynomial Reductions and NP-completeness | 16.5. | screen print4 print1 |
| D3 | Proving NP-Completeness | 18.5. | screen print4 print1 |
| D4 | NP-complete Problems I | 23.5. | screen print4 print1 |
| D5 | NP-complete Problems II | 25.5. | screen print4 print1 |
| D6 | Beyond NP | 30.5. | screen print4 print1 |