CSC 463H: Computational Complexity and Computability
Winter 2018


May 1: I have submitted final marks for the course.
The average mark on the final exam is 69/100, but there was a very wide range of marks, including 3 students with 90 - 100, 5 students 80 - 89, and 15 students 70 - 79.

You may email me to request your exam mark and final mark.

Lectures: MW 2 in GB 303

Tutorials: F2
T1 GB 303 A - L Robert Robere
T2 RW 140 M - Z Ian Mertz
(No tutorial Jan 5)

Instructor: Stephen Cook
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 3:15-4:00 Or make an appointment, or drop in.

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.

M. Garey and D. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Chapters 1-3 especially relevant.

Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms (Second Edition), MIT Press and McGraw-Hill. Chapter 34 on NP-completeness is the relevant chapter here.

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

Problem Sets (.pdf files)

Midterm Test Midterm Test (2018)

Last Year's Problem Sets

Last Years' midterm test Midterm Test (2017)