John Watrous |
Email: my last name at uwaterloo.ca |
John Watrous |
Email: my last name at uwaterloo.ca |
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.)
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.