Advanced topics in theoretical computer science

Slides

  • 24.10.2018: Introduction [introduction.pdf]
  • 31.10.2018: Turing Machines and Computability (Part 1) [recap-tm.pdf]
  • 7.11.2018: Turing Machines and Computability (Part 2) [recap-tm2.pdf]
  • 7.11.2018: Register Machines (Part 1) [register-machines1.pdf] (after the lecture)
  • Slides about structural induction: [structural-induction.pdf]
  • 14.11.2018: Register Machines (Part 2) [register-machines2.pdf] (after the lecture)
  • 21.11.2018: Register Machines (Part 3) [register-machines3.pdf]
  • 21.11.2018: Register Machines: Wrapping up [register-machines-recap.pdf]
  • 21.11.2018: Recursive functions (Part 1) [recursive-functions1.pdf] (after the lecture)
  • 28.11.2018: Recursive functions (Part 2) [recursive-functions2.pdf] (after the lecture)
  • 5.12.2018: Recursive functions (Part 3) [recursive-functions3.pdf] (after the lecture)
  • 12.12.2018: Recursive functions (Part 4) [recursive-functions4.pdf] (after the lecture)
  • 19.12.2018: Computability and (Un-)Decidability, Part I [computability1.pdf]
  • 9.01.2019 and 16.01.2019 Computability and (Un-)Decidability, Part II [computability2.pdf]
  • 16.01.2019 and 23.01.2019: Complexity, Part I [complexity1.pdf](after the lecture)
  • 30.01.2019: Complexity, Part II [complexity2.pdf] (after the lecture)
  • 6.02.2019: Complexity, Part III [complexity3.pdf]
  • Coloring is NP-complete: Proof [coloring-np-complete-proof.pdf]
  • 3-colorability is NP-complete: Proof [External Link]
    • List of topics: [summary.pdf]