CS 365 - Models of Computation
(See here for the 2023 version of the notes and here for the 2021 version of the notes.)
Preface
The lectures contained here provide an introduction to the theory of computation. These notes have been developed for the CS 365 course at the University of Waterloo.
The material covered in these notes has been significantly revised to minimize overlap with content seen in earlier courses in the University of Waterloo’s undergraduate curriculum. This version of the course itself covers six broad topics:
- Decidability. What problems can computers solve, even with unbounded resources?
- Time Complexity. What problems can computers solve in a reasonable amount of time?
- Circuit Complexity. What problems can reasonably simple computers solve?
- Randomized Computation. How does the ability to flip a coin affect the power of computers?
- Space Complexity. What problems can computers solve with a reasonable amount of memory?
- Communication and Query Complexity. What problems can we solve with computers that are limited only in how much information they can inspect or share?
If you are enrolled in the class, you can find more information about the course itself in the official Learn page.
If you are not enrolled in the class, you are most welcome to use these notes in your independent study as well. The notes are meant to complement the lectures given in person for the class, so many incidental discussions about the results presented in the notes are omitted. However, there are many great resources (online and in the form of textbooks) available to complement the notes.
Theoretical computer science is a rich area of mathematical research with many beautiful results and countless fascinating open problems. Hopefully, these notes will convey at least a bit of the interest in this area and leave you ready to continue studying more advanced topics in the field.
Happy explorations!
Eric Blais
Waterloo, ON, Canada
January 5, 2024