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 4032.
Textbooks
Undergraduate-level review material: T. J. Smith, Theory of Computing: An Open Introduction. Self-published open educational resource, α pre-publication edition, 2024.
Graduate-level material: S. Arora and B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
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
- Mar. 2: The second quiz will be written this week during the Mar. 5 lecture. See the Quizzes section below for more details.
- Feb. 25: Lecture notes for the seventh week have been posted.
- Feb. 23: Assignment 2 has been posted. It is due by Mar. 12 at 1:30pm.
- Feb. 12: Due to inclement weather, today’s lecture and office hours are cancelled.
- Feb. 9: Lecture notes for the sixth week have been posted.
- Feb. 4: Lecture notes for the fifth week have been posted. Information about the group lecture and report has also been posted.
- Feb. 2: Due to inclement weather, today’s lecture and office hours are cancelled.
- Jan. 28: The first quiz will be written this week during the Jan. 29 lecture. See the Quizzes section below for more details.
- Jan. 26: Due to inclement weather, today’s lecture and office hours are cancelled.
- Jan. 19: Lecture notes for the third week have been posted.
- Jan. 12: Lecture notes for the second week have been posted. Assignment 1 has also been posted. It is due by Feb. 5 at 1:30pm.
- Jan. 7: Lecture notes for the first week have been posted.
- Jan. 5: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Notes | Readings |
| 1 | Introduction, Turing machines | Arora and Barak, 1.1–1.2 |
| 2 | Foundations of complexity: Running time, work space, speedup, compression | Arora and Barak, 1.3, 1.6 |
| 3 | Foundations of complexity (cont’d): Gap theorem, constructibility, resource bounds | Arora and Barak, 3.1–3.2, 4.1 |
| 4 | Foundations of complexity (cont’d): hierarchy theorems, Savitch’s theorem | Arora and Barak, 4.2 |
| 5 | Time and space complexity | Arora and Barak, 2.1, 2.5–2.7 |
| 6 | Hardness, completeness, and complements | Arora and Barak, 2.2–2.4, 4.3 |
| — | Winter study break | — |
| 7 | Probabilistic computation: Probabilistic TMs, Las Vegas/Monte Carlo algorithms | Arora and Barak, 7.1–7.2 |
| 8 | Probabilistic computation (cont’d): Randomized complexity | Arora and Barak, 7.3–7.5 |
Assignments
- Assignment 1, due Feb. 5
- Lesson Plan, due Feb. 12
- Assignment 2, due Mar. 12
- Report, due Apr. 2
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 lesson plan and report must be submitted on the due date. Late submissions will not be accepted.
Quizzes
Quiz 1
Date: Jan. 29, 2026
Time: 1:30pm–2:20pm
Place: Mulroney Hall, Room 4032
Content: All material from Weeks 1 to 4
Quiz 2
Date: Mar. 5, 2026
Time: 1:30pm–2:20pm
Place: Mulroney Hall, Room 4032
Content: All material from Weeks 5 to 8
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday 1:30pm–2:20pm and Thursday 11:30am–1:20pm, or by appointment