Participation
Please register for the course to gain access to the Adam workspace.
Lecture Slides
No | Topic | Date | Slides |
---|---|---|---|
A1 | Organizational Matters | 20.2. | screen print4 print1 |
A2 | Mathematical Foundations | 20.2. | screen print4 print1 |
A3 | Proof Techniques | 22.2. | screen print4 print1 |
B1 | Finite Automata | 6.3. | screen print4 print1 |
B2 | Grammars | 8.3. | screen print4 print1 |
B3 | Regular Languages | 13.3. | screen print4 print1 |
B4 | Regular Languages: Closure Properties and Decidability | 15.3. | screen print4 print1 |
B5 | Regular Languages: Regular Expressions | 20.3. | screen print4 print1 |
B6 | Regular Languages: Pumping Lemma | 22.3. | screen print4 print1 |
B7 | Context-free Languages: ε-Rules & Chomsky Normal Form | 27.3. | screen print4 print1 |
B8 | Context-free Languages: Push-Down Automata | 27.3. | screen print4 print1 |
B9 | Context-free Languages: Closure Properties and Decidability | 29.3. | screen print4 print1 |
B10 | Turing Machines I | 29.3. | screen print4 print1 |
B11 | Turing Machines II | 3.4. | screen print4 print1 |
B12 | Type-1 and Type-0 Languages: Closure & Decidability | 5.4. | screen print4 print1 |
C1 | Turing Machines as Formal Model of Computation | 5.4. | screen print4 print1 |
C2 | The Halting Problem | 12.4. | screen print4 print1 |
C3 | Turing-Computability | 17.4. | screen print4 print1 |
C4 | Reductions | 19.4. | screen print4 print1 |
C5 | Post Correspondence Problem | 19.4. | screen print4 print1 |
C6 | Rice't Theorem | 24.4. | screen print4 print1 |
D1 | Nondeterministic Algorithms, P and NP | 26.4. | screen print4 print1 |
D2 | Polynomial Reductions and NP-completeness | 3.5. | screen print4 print1 |
D3 | Proving NP-completeness | 8.5./ 10.5. | screen print4 print1 |
D4 | Some NP-complete Problems I | 10.5. | screen print4 print1 |
D5 | Some NP-complete Problems II | 15.5. | screen print4 print1 |
D6 | Beyond NP | 17.5. | screen print4 print1 |
E1 | LOOP & WHILE Computability | 22.5. | screen print4 print1 |
E2 | GOTO Computability & Comparsion | 24.5. | screen print4 print1 |