Participation
Please register for the course to gain access to the Adam workspace.
In the workspace forum you find the Zoom link for the lecture.
Lecture Slides
| No | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 1.3. | screen print4 print1 |
| A2 | Mathematical Foundations | 1.3. | screen print4 print1 |
| A3 | Proof Techniques | 3.3. | screen print4 print1 |
| B1 | Finite Automata | 8.3. | screen print4 print1 notebook |
| B2 | Grammars | 10.3. | screen print4 print1 |
| B3 | Regular Languages | 15.3. | screen print4 print1 |
| B4 | Regular Languages: Closure Properties and Decidability | 17.3. | |
| B5 | Regular Languages: Regular Expressions | 22.3. | screen print4 print1 |
| B6 | Regular Languages: Pumping Lemma | 24.3. | screen print4 print1 |
| B7 | Context-free Languages: Normal Form and PDA | 29.3. | screen print4 print1 |
| B8 | Context-free Languages: Closure & Decidability | 31.3. | screen print4 print1 |
| B9 | Turing Machines I | 7.4. | screen print4 print1 |
| B10 | Turing Machines II | 12.4. | screen print4 print1 |
| B11 | Type-0 and Type-1 Languages: Closure & Decidability | 12.4. | screen print4 print1 |
| C1 | Turing Machines as Formal Model of Computation | 14.4. | screen print4 print1 |
| C2 | Halting Problem | 19.4. | screen print4 print1 |
| C3 | Turing-Computability | 21.4. | screen print4 print1 |
| C4 | Reductions | 26.4. | screen print4 print1 |
| C5 | Post Correspondence Problem | 26.4. | screen print4 print1 |
| C6 | Rice's Theorem | 28.4. | screen print4 print1 |
| D1 | Nondeterministic Algorithms, P and NP | 3.5. | screen print4 print1 |
| D2 | Polynomial Reductions and NP-completeness | 5.5. | screen print4 print1 |
| D3 | Proving NP-completeness | 10.5. | screen print4 print1 |
| D4 | NP-complete Problems I | 12.5. | screen print4 print1 |
| D5 | NP-complete Problems II | 17.5. | screen print4 print1 |
| D6 | Beyond NP | 17.5. | screen print4 print1 |