Turning Points in the Information Sciences: Theoretical Computer Science

Since 2024, all first-years students in the BSc Computer Science, the BSc AI, and the BSc Information Studies at the University of Amsterdam start their studies with a lecture series on Turning Points in the Information Sciences. Together with Christian Schaffner, I'm responsible for the theory part of the course, organised around the questions of what can be computed and what can be computed efficiently. Below you will find the teaching materials I developed for this course.

Lecturer: Ulle Endriss (ILLC, University of Amsterdam)
Lecture 4: What can be computed? (covering Turing Machines and the Halting Problem)
Lecture 5: What can be computed efficiently? (covering Dijkstra's Algorithm and P vs NP)

The first lecture above is accompanied by a tutorial where students gain a deeper understanding of the proof of the undecidability of the Halting Problem and where they practice programming a Turing Machine.