Course Description
An advanced course building on foundational ideas in the theory of computing. Further properties of regular and context-free languages, language classes beyond context-free, parsing, randomness and probabilistic computation, relativized computation, complexity hierarchies, and circuit complexity will be discussed. Prior experience with theory of computing at the undergraduate level is recommended.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 12:30pm–1:20pm; Wednesday, 11:30am–12:20pm; Thursday, 1:30pm–2:20pm
All lectures are held in Mulroney Hall, room 2034.
Special Note for Fall 2023. On Tuesday, December 5, the Monday schedule of classes and labs will be offered again. On Wednesday, December 6, the Friday schedule of classes and labs will be offered.
Textbooks
Undergraduate-level review material: M. Sipser, Introduction to the Theory of Computation. Cengage, 3rd edition, 2012.
Graduate-level material: S. Arora and B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
The undergraduate-level textbook is available for sale at the campus bookstore. A free electronic copy of a draft edition of the graduate-level textbook is available online. Course notes will also be provided for each lecture.
Marking Scheme
- Two assignments (10% each, total 20%)
- Two quizzes (15% each, total 30%)
- Group lecture (total 30%): a lesson plan (10%) and the lecture itself (20%)
- Individual report on the group lecture (10%)
- Participation (total 10%): class participation (5%) and reviewing group lectures (5%)
You must complete the group lecture and individual report components in order to pass the course. You may not complete one without completing the other.
News
- Nov. 2: Lecture notes for the ninth week have been posted.
- Oct. 25: Lecture notes for the eighth week have been posted.
- Oct. 20: Lecture notes for the seventh week have been posted.
- Oct. 18: Assignment 2 has been posted. It is due by Nov. 2 at 1:30pm.
- Oct. 12: Lecture notes for the sixth week have been posted.
- Oct. 5: Lecture notes for the fifth week have been posted. Information about the group lecture and report has also been posted.
- Sep. 27: Lecture notes for the fourth week have been posted.
- Sep. 21: Lecture notes for the third week have been posted.
- Sep. 14: Lecture notes for the second week have been posted. Assignment 1 has also been posted. It is due by Oct. 5 at 1:30pm.
- Sep. 7: Lecture notes for the first week have been posted.
- Sep. 1: Welcome to the course! The first lecture is on Sep. 6.
Lectures
| Week | Notes | Readings |
| 1 | Introduction, review of basic notions | Arora and Barak, 0.1–0.3, 1.1 |
| 2 | Turing machines: deterministic, nondeterministic, variants | Arora and Barak, 1.2–1.5 |
| 3 | Time and space complexity, resource bounds | Arora and Barak, 1.6, 2.1, 2.6–2.7 |
| 4 | Fundamental complexity hierarchy | Arora and Barak, 3.1–3.2 |
| 5 | Fundamental complexity hierarchy (cont’d); Reductions | Arora and Barak, 2.2–2.4 |
| 6 | Reductions (cont’d) | Arora and Barak, 4.2–4.3 |
| 7 | Probabilistic computation | Arora and Barak, 7.1–7.2 |
| 8 | Probabilistic computation (cont’d) | Arora and Barak, 7.3–7.5 |
| 9 | Interactive proof systems, zero-knowledge proofs | Arora and Barak, 8.1–8.3, 9.4 |
| — | Fall study break | — |
| 10 | Group lectures | — |
| 11 | Group lectures | — |
| 12 | Group lectures | — |
Assignments
- Assignment 1, due Oct. 5
- Lesson Plan, due Oct. 12
- Assignment 2, due Nov. 2
- Report, due Dec. 5
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
The topic proposal and report must be submitted on the due date. Late submissions will not be accepted.
Quizzes
Quiz 1
Date: Sep. 28, 2023
Time: 1:30pm–2:20pm
Place: Mulroney Hall, room 2034
Content: All material from Weeks 1 to 4
Quiz 2
Date: Oct. 26, 2023
Time: 1:30pm–2:20pm
Place: Mulroney Hall, room 2034
Content: All material from Weeks 5 to 8
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Monday/Wednesday/Friday, 9:30am–10:30am