John Watrous
Email: my last name at

Course announcements and policies

Course outline [pdf]

Policies on grading and course work [html]

There is no required text for the course. Students interested in an additional source beyond the course notes may find the following text to be helpful:

M. Sipser. Introduction to the Theory of Computation (Third Edition). Cengage Learning, 2012.

(An older edition of this book would serve just as well for this course.)

Lecture schedule and notes

May 1 Lecture 1. Course overview and mathematical foundations [pdf]
May 3 Lecture 2. Countability for languages and deterministic finite automata [pdf]
May 8 Lecture 3. Nondeterministic finite automata [pdf]
May 10 Lecture 4. Regular operations and regular expressions [pdf]
May 15 Lecture 5. Proving languages to be nonregular [pdf]
May 17 Lecture 6. Further discussion of regular languages [pdf]
May 23 Lecture 7. Context-free grammars and languages [pdf]
May 24 Lecture 8. Parse trees, ambiguity, and Chomsky normal form [pdf]
May 29 Exam 1 (in class)
May 31 Lecture 9. Closure properties for context-free languages [pdf]
June 5 Lecture 10. Proving languages to be non-context-free [pdf]
June 7 Lecture 11. Further discussion of context-free languages [pdf]
June 12 Lecture 12. The Turing machine model of computation [pdf]
June 14 Lecture 13. Variants of Turing machines and encoding objects as strings [pdf]
June 19 Lecture 14. Decidable languages [pdf]
June 21 Lecture 15. Undecidable languages [pdf]
June 26 Lecture 16. Computable functions and mapping reductions [pdf]
June 28 Lecture 17. Further discussion of Turing machines [pdf]
July 3 Canada Day – no lecture
July 5 Lecture 18. Time-bounded computations [pdf]
July 10 Exam 2 (in class)
July 12 Lecture 19. NP, polynomial-time mapping reductions, and NP-completeness [pdf]
July 17 Lecture 20. Boolean circuits [pdf]
July 19 Lecture 21. The Cook-Levin theorem [pdf]
July 24 Lecture 22. Further discussion and summary [no notes for this lecture]
August 3 Final exam 19:30–22:00 in PAC 4

You can also download all 21 lectures in a single pdf file [pdf]. Before you send this file to a printer, please observe that it is over 200 pages long, and consider using an electronic copy instead.