Advanced topics in theoretical computer science


Slides

  • 30.10.2014: Introduction [introduction.pdf]
  • 6.11.2014: Turing Machines and Computability (Part 1) [recap-tm1.pdf]
  • 13.11.2014: Turing Machines and Computability (Part 2) [recap-tm2.pdf] (updated after the lecture)
  • 13.11.2013: Register Machines (Part 1) [register-machines1.pdf] (updated after the lecture)
  • 20.11.2014: Register Machines (Part 2) [register-machines2.pdf] (updated after the lecture)
  • 27.11.2014: Register Machines (Part 3) [register-machines3.pdf] (updated after the lecture; last update: December 3: recursive functions in separate file)
  • 27.11.2014: Register Machines: Wrapping up [register-machines-recap.pdf] (added on December 3, 2014)
  • 27.11.2014: Recursive functions (Part 1) [recursive-functions1.pdf] (after lecture)
  • 4.12.2014: Recursive functions (Part 2) [recursive-functions2.pdf] (after the lecture)
  • 11.12.2014: Recursive functions (Part 3) [recursive-functions3.pdf] (after the lecture)
  • 18.12.2014: Recursive functions (Part 4) [recursive-functions4.pdf]
  • 8.01.2015: Computability and (Un-)Decidability, Part I [computability1.pdf]
  • 15.01.2015: Computability and (Un-)Decidability, Part II [computability2.pdf] (we discussed the contents on pages 1-33)
  • 22.01.2015: Computability and (Un-)Decidability, Part III (same slides set as above; we will discuss the contents on pages 33ff)
  • 29.01.2015: Complexity, Part I [complexity1.pdf]
  • 5.02.2015: Complexity, Part II [complexity2.pdf]
  • 12.02.2015: Complexity, Part III [complexity3.pdf]