CSC 463H: Computational Complexity and Computability
Winter 2019


ASSIGNMENTS (due at the start of lecture or tutorial)

Lectures: MW 2-3 in Bahen 1200

Tutorial: F 2-3 in Bahen 1200

Instructor: Benjamin Rossman (
Office hours: M 3-4 in Bahen 6214

Teaching Assistants: Adrian She ( and Evi Micha (

Click here for the course information sheet.

Text: "Introduction to the Theory of Computation" by Michael Sipser (Second or Third Edition). Chapters 3,4,5,7,8, and part of Chapter 9.


Course Contents

Marking Scheme

The work you submit must be your own. You may discuss problems with each other; however, you should prepare written solutions alone. Copying assignments is a serious academic offence and will be dealt with accordingly.

Supplementary Lecture Notes (.pdf files from earlier versions of this course)

Previous Years' Problem Sets (.pdf files)

Previous Years' Midterm Tests