Week | Date | Topics | Readings | Tutorial | Notes |
---|---|---|---|---|---|
1 | May 16 | Course Introduction Computability and Turing machines |
Section 3.1 (review chapters 0, 1, 2 as needed) |
exercises | lecture notes |
2 | May 23 | Other models of computation | Sections 3.2, 3.3 | exercises | lecture notes Additional example of TM description |
3 | May 30 | Church-Turing Thesis, Decidability and recognizability |
Section 4.1 | exercises | lecture notes |
4 | June 6 | Diagonalization, the Halting problem | Section 4.2 | exercises | lecture notes |
5 | June 13 | Reducibility | Section 5.1 | exercises | lecture notes |
6 | June 20 | Term test 1 Mapping reducibility |
Section 5.3, exercise 5.28 | no tutorial | lecture notes |
7 | June 27 | Computational Complexity Models of efficient computation |
Sections 7.1, 7.2 | exercises | lecture notes |
8 | July 4 | Complexity classes P, NP, coNP | Section 7.3 | exercises | lecture notes |
9 | July 11 | Polytime reducibility and NP-completeness | Section 7.4 | exercises | lecture notes Additional example of ≤p |
10 | July 18 | NP-completeness | Section 7.5 | exercises | lecture notes |
11 | July 25 | Term test 2 Self-reducibility |
Section 8.1 | no tutorial | lecture notes |
12 | Aug 1 | Space complexity | Sections 8.2, 8.3 | exercises | lecture notes |
13 | Aug 8 | Other complexity classes Dealing with intractability |
Sections 8.4, 8.5, 9.1 | past exam (PDF) | lecture notes |
All readings are from the course textbook, Michael Sipser, Introduction to the Theory of Computation, 2nd edition.
Many of the lecture notes included here are adapted from Francois Pitt's CSC 363 notes.
The following topics will be covered in this course, in the order listed. For each topic, we have indicated the approximate number of weeks required to cover that topic as well as a list of the relevant sections in the textbook.
By the end of this course, students should
be familiar with fundamental restrictions on computability:
understand the importance of computational complexity:
|