Advanced topics in theoretical computer science

Slides

  • 24.10.2013: Introduction [introduction.pdf]
  • 31.10.2013: Turing Machines and Computability (Part 1)[recap-tm1.pdf]
  • 7.11.2013: Turing Machines and Computability (Part 2) [recap-tm2.pdf]
  • 7.11.2013: Register Machines (Part 1) [register-machines1.pdf]
  • 14.11.2013: Register Machines (Part 2) [register-machines2.pdf]
  • 21.11.2013: Register Machines (Part 3) [register-machines3.pdf]
  • 28.11.2013: Register Machines: Wrapping up [register-machines-recap.pdf]
  • 28.11.2013: Recursive functions (Part 1) [recursive-functions1.pdf] (after lecture: typos corrected on pages 45, 48-50)
  • 5.12.2013: Recursive functions (Part 2) [recursive-functions2.pdf]
  • 12.12.2013: Recursive functions (Part 3) [recursive-functions3.pdf]
  • 19.12.2013: Recursive functions (Part 4) [recursive-functions4.pdf]
  • 9.01.2014: Computability and (Un-)Decidability, Part I [computability1.pdf]
  • 16.01.2014: Computability and (Un-)Decidability, Part II [computability2.pdf] (we discussed the contents on pages 1-29)
  • 23.01.2014: Computability and (Un-)Decidability, Part III (same slides set as above; we will discuss the contents on pages 27-38)
  • 23.01.2014: Complexity, Part I [complexity1.pdf]
  • 30.01.2014: Complexity, Part II [complexity2.pdf] (after lecture: some typos corrected)
  • 06.02.2014: Complexity, Part III [complexity3.pdf]