Advanced topics in theoretical computer science

Slides

  • 18.10.2017: Introduction [introduction.pdf]
  • 25.10.2017: Turing Machines and Computability (Part 1) [recap-tm.pdf]
  • 8.11.2017: Turing Machines and Computability (Part 2) [recap-tm2.pdf]
  • 8.11.2017: Register Machines (Part 1) [register-machines1.pdf]
  • Slides about structural induction: [structural-induction.pdf]
  • 15.11.2017: Register Machines (Part 2) [register-machines2.pdf] (after the lecture)
  • 22.11.2017: Register Machines (Part 3) [register-machines3.pdf] (after the lecture)
  • 22.11.2017: Register Machines: Wrapping up [register-machines-recap.pdf]
  • 22.11.2017: Recursive functions (Part 1) [recursive-functions1.pdf] (after the lecture)
  • 29.11.2017: Recursive functions (Part 2) [recursive-functions2.pdf] (after the lecture)
  • 6.12.2017: Recursive functions (Part 3) [recursive-functions3.pdf] (after the lecture)
  • 13.12.2017: Recursive functions (Part 4) [recursive-functions4.pdf] (after the lecture)
  • 13.12.2017: Computability and (Un-)Decidability, Part I [computability1.pdf] (after the lecture)
  • 20.12.2017: Computability and (Un-)Decidability, Part II [computability2.pdf] (after the lecture)
  • 10.01.2018: Computability and (Un-)Decidability, Part III [computability3.pdf] (after the lecture)
  • 17.01.2018: Computability and (Un-)Decidability, Part IV [computability4.pdf] (after the lecture)
  • 17.01.2018: Complexity, Part I [complexity1.pdf] (after the lecture)
  • 24.01.2018: Complexity, Part II [complexity2.pdf] (after the lecture)
  • 31.01.2018: Complexity, Part III [complexity3.pdf] (after the lecture)
  • 7.02.2018: Complexity, Part IV [complexity4.pdf] (after the lecture)
  • Coloring is NP-complete: Proof [coloring-np-complete-proof.pdf]
  • 3-colorability is NP-complete: Proof [External Link]
    • List of topics: [summary.pdf]