CSC 463H: Computational Complexity and Computability
Winter 2017


Final Marks have been turned in and should appear on ACORN soon.
Four students received 100 on the exam, and the average mark was 69.

Lectures: MW 2 in MP 137

Tutorials: F2
T1 MP 137 A - L Venkatesh Medabalimi
T2 UC 85 M - Z Ian Mertz

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