Advanced topics in theoretical computer science

Slides

  • 12.04.2016: Introduction [introduction.pdf]
  • 19.04.2016: Turing Machines and Computability (Part 1) [recap-tm.pdf]
  • 26.04.2016: Turing Machines and Computability (Part 2) [recap-tm2.pdf]
  • 26.04.2016: Register Machines (Part 1) [register-machines1.pdf]
  • Slides about structural induction: [structural-induction.pdf]
  • 3.05.2016: Register Machines (Part 2) [register-machines2.pdf] (after the lecture)
  • 10.05.2016: Register Machines (Part 3) [register-machines3.pdf] (after the lecture)
  • 10.05.2016: Register Machines: Wrapping up [register-machines-recap.pdf]
  • 10.05.2016: Recursive functions (Part 1) [recursive-functions1.pdf] (after the lecture)
  • 24.05.2016: Recursive functions (Part 2) [recursive-functions2.pdf] (after the lecture)
  • 31.05.2016: Recursive functions (Part 3) [recursive-functions3.pdf] (after the lecture)
  • 7.06.2016: Recursive functions (Part 4) [recursive-functions4.pdf] (after the lecture)
  • 14.06.2016: Computability and (Un-)Decidability, Part I [computability1.pdf]
  • 21.06.2016: Computability and (Un-)Decidability, Part II [computability2.pdf] (on 21.06 we discussed the contents on pages 1-27)
  • 28.06.2016: Computability and (Un-)Decidability, Part III (same slides set as above; we will discuss the contents on pages 25ff)
  • 28.06.2016: Complexity, Part I [complexity1.pdf] (after the lecture)
  • 5.07.2016: Complexity, Part II [complexity2.pdf] (after the lecture)
  • 12.07.2016: Complexity, Part III [complexity3.pdf] (before the lecture)
  • Coloring is NP-complete: Proof [coloring-np-complete-proof.pdf]
  • 3-colorability is NP-complete: Proof [External Link]
  • 19.07.2016: Complexity, Part IV [complexity4.pdf] (before the lecture)
    • List of topics: [summary.pdf]