Instructor

John Watrous
Email: my last name at uwaterloo.ca
Office: QNC 3312
Office hours: Wednesday 2–3, Thursday 10–11, and by appointment.

Teaching assistants

Taylor Hornby Abel Molina
Email: taylor at defuse dotca Email: abelmolinauw at gmail dotcom
Office: QNC 4201 Office: QNC 2212
Office hours: Tuesday 10–11 Office hours: Wednesday 4–5

Lectures

Monday and Wednesday 10–11:20 in MC 2038

Course announcements and policies

Announcements:

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.

Assignments

Assignment 1 (due Friday May 19) [pdf, LaTeX]   Solutions [pdf]
Assignment 2 (due Friday June 9) [pdf, LaTeX]   Solutions [pdf]
Assignment 3 (due Friday June 30) [pdf, LaTeX]  
Assignment 4 (due Monday July 24)  

Additional handouts

Practice problems for exam 1 [pdf]
Solutions to exam 1 [pdf]