Participation

Please register for the course to gain access to the Adam workspace.

Lecture Slides

NoTopicDateSlides
A1Organizational Matters28.2.screen
print4
print1
A2Mathematical Foundations28.2.screen
print4
print1
A3Proof Techniques4.3.screen
print4
print1
B1Formal Languages & Grammars6.3.screen
print4
print1
B2Regular Grammars: ε-Rules11.3.screen
print4
print1
B3Finite Automata11.3./
13.3
screen
print4
print1
B4Finite Automata: Characterization13.3.screen
print4
print1
B5Regular Languages: Closure Properties and Decidability18.3.screen
print4
print1
B6Regular Languages: Regular Expressions20.3.screen
print4
print1
B7Regular Languages: Pumping Lemma25.3.screen
print4
print1
B8Context-free Languages: ε-Rules & Chomsky Normal Form25.3./27.3.screen
print4
print1
B9Context-free Languages: Push-Down Automata27.3.screen
print4
print1
B10Context-free Languages: Closure Properties and Decidability3.4.screen
print4
print1
B11Turing Machines I3.4.screen
print4
print1
B12Turing Machines II8.4.screen
print4
print1
B13Type-1 and Type-0 Languages: Closure & Decidability10.4.screen
print4
print1
C1Turing Machines as Formal Model of Computation10.4.screen
print4
print1
C2The Halting Problem15.4.screen
print4
print1
C3Turing-Computability17.4.screen
print4
print1
C4Reductions22.4.screen
print4
print1
C5Post Correspondence Problem22.4.screen
print4
print1
C6Rice’s Theorem24.4.screen
print4
print1
D1Nondeterministic Algorithms, P and NP29.4.screen
print4
print1
D2Polynomial Reductions and NP-completeness6.5.screen
print4
print1
D3Proving NP-Completeness8.5.screen
print4
print1
D4Some NP-Complete Problems, Part I13.5.screen
print4
print1
D5Some NP-Complete Problems, Part II15.5.screen
print4
print1
D6Beyond NP22.5.screen
print4
print1