Participation
Please register for the course to gain access to the Adam workspace.
Lecture Slides
| No | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 28.2. | screen print4 print1 |
| A2 | Mathematical Foundations | 28.2. | screen print4 print1 |
| A3 | Proof Techniques | 4.3. | screen print4 print1 |
| B1 | Formal Languages & Grammars | 6.3. | screen print4 print1 |
| B2 | Regular Grammars: ε-Rules | 11.3. | screen print4 print1 |
| B3 | Finite Automata | 11.3./ 13.3 | screen print4 print1 |
| B4 | Finite Automata: Characterization | 13.3. | screen print4 print1 |
| B5 | Regular Languages: Closure Properties and Decidability | 18.3. | screen print4 print1 |
| B6 | Regular Languages: Regular Expressions | 20.3. | screen print4 print1 |
| B7 | Regular Languages: Pumping Lemma | 25.3. | screen print4 print1 |
| B8 | Context-free Languages: ε-Rules & Chomsky Normal Form | 25.3./27.3. | screen print4 print1 |
| B9 | Context-free Languages: Push-Down Automata | 27.3. | screen print4 print1 |
| B10 | Context-free Languages: Closure Properties and Decidability | 3.4. | screen print4 print1 |
| B11 | Turing Machines I | 3.4. | screen print4 print1 |
| B12 | Turing Machines II | 8.4. | screen print4 print1 |
| B13 | Type-1 and Type-0 Languages: Closure & Decidability | 10.4. | screen print4 print1 |
| C1 | Turing Machines as Formal Model of Computation | 10.4. | screen print4 print1 |
| C2 | The Halting Problem | 15.4. | screen print4 print1 |
| C3 | Turing-Computability | 17.4. | screen print4 print1 |
| C4 | Reductions | 22.4. | screen print4 print1 |
| C5 | Post Correspondence Problem | 22.4. | screen print4 print1 |
| C6 | Rice’s Theorem | 24.4. | screen print4 print1 |
| D1 | Nondeterministic Algorithms, P and NP | 29.4. | screen print4 print1 |
| D2 | Polynomial Reductions and NP-completeness | 6.5. | screen print4 print1 |
| D3 | Proving NP-Completeness | 8.5. | screen print4 print1 |
| D4 | Some NP-Complete Problems, Part I | 13.5. | screen print4 print1 |
| D5 | Some NP-Complete Problems, Part II | 15.5. | screen print4 print1 |
| D6 | Beyond NP | 22.5. | screen print4 print1 |