Instructor

John Watrous
Email: my last name at uwaterloo.ca
Office: QNC 3312

Teaching assistants

Rylo Ashmore Vijay Subramanya
Email: rjashmor AT uwaterloo DOT ca Email: v7subram AT uwaterloo DOT ca
Office: DC 2551A Office: DC 2569

Lectures

Monday and Wednesday 11:30–12:50 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

Notes for each lecture are linked below. 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 about 230 pages long, and consider using an electronic copy instead.

May 6 Lecture 1. Course overview and mathematical foundations [pdf]
May 8 Lecture 2. Countability for languages and deterministic finite automata [pdf]
May 13 Lecture 3. Nondeterministic finite automata [pdf]
May 15 Lecture 4. Regular operations and regular expressions [pdf]
May 20 Victoria Day – no lecture
May 22 Lecture 5. Proving languages to be nonregular [pdf]
May 27 Lecture 6. Further discussion of regular languages [pdf]
May 29 Lecture 7. Context-free grammars and languages [pdf]
June 3 Lecture 8. Parse trees, ambiguity, and Chomsky normal form [pdf]
June 5 Lecture 9. Closure properties for context-free languages [pdf]
June 10 Exam 1 (in class)
June 12 Lecture 10. Proving languages to be non-context-free [pdf]
June 17 Lecture 11. Pushdown automata [pdf]
June 19 Lecture 12. Stack machines [pdf]
June 24 Lecture 13. Decidable and semidecidable languages; computable functions [pdf]
June 26 Lecture 14. Turing machines and their equivalence to stack machines [pdf]
July 1 Canada Day – no lecture
July 2 Lecture 15. Encodings; examples of decidable languages [pdf]
July 3 Lecture 16. Universal stack machines and a non-semidecidable language [pdf]
July 8 Lecture 17. Undecidable languages [pdf]
July 10 Lecture 18. Further discussion of computability [pdf]
July 15 Exam 2 (in class)
July 17 Lecture 19. Time-bounded computations [pdf]
July 22 Lecture 20. NP, polynomial-time mapping reductions, and NP-completeness [pdf]
July 24 Lecture 21. Ladner's theorem [pdf]
July 29 Lecture 22. Further discussion and summary [no notes for this lecture]
August 2 Final exam 12:30–3 PM in STC 0010

Assignments

Assignments will be posted as they become available. If you like to typeset your solutions using LaTeX, feel free to use the source files linked with each assignment.

Assignment 1 (due Thursday May 30) [pdf, LaTeX]
Assignment 2 (due Thursday June 20) [pdf, LaTeX]
Assignment 3 (due Thursday July 4) [pdf, LaTeX]
Assignment 4 (due Thursday July 25) [pdf, LaTeX]

Additional handouts

Practice problems for exam 1 [pdf]
Practice problems for exam 2 [pdf]
Practice problems for the final exam [pdf]