CS 365: Models of Computation

University of Waterloo, Winter 2026

Babbage’s Difference Engine No. 2, 2002 by the Science Museum, London / CC BY 4.0

Lecture Notes

1. Introduction
2. Turing Machines
3. Decidable Languages
4. Recursion Theorem
5. Undecidability
6. Reductions
7. Time Complexity
8. P vs. NP
9. Polynomial Hierarchy
10. Boolean Circuits
11. Non-Uniform Computation
12. Boolean Formulas
13. Satisfiability
14. Randomized Computation
15. P vs. BPP
16. Randomized Verification
17. Space Complexity
18. Logarithmic Space
19. Sublogarithmic Space
20. Nonregular Languages
21. Communication Complexity