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.)
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. Contextfree 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 contextfree languages
[pdf]

June 5 
Lecture 10. Proving languages to be noncontextfree
[pdf]

June 7 
Lecture 11. Further discussion of contextfree 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. Timebounded computations
[pdf]

July 10 
Exam 2 (in class)

July 12 
Lecture 19. NP, polynomialtime mapping reductions, and
NPcompleteness
[pdf]

July 17 
Lecture 20. Boolean circuits
[pdf]

July 19 
Lecture 21. The CookLevin 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.