CSCI 541: Theory of Computing (Fall 2023)

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.


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

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.



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 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.


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



Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Monday/Wednesday/Friday, 9:30am–10:30am