CSC 463H: Computational Complexity and Computability
Winter 2018

Announcements

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
email: sacook@cs.toronto.edu
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 3:15-4:00 Or make an appointment, or drop in.
E-MAIL QUESTIONS ARE WELCOME.

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.

References:
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

• Computability Theory (5 weeks): Turing machines, Church's Thesis, decidability and semi-decidability, diagonal arguments, the Halting Problem and other undecidable problems, reductions, complete problems.

• Computational Complexity (7 weeks): The classes P and NP, polynomial time reducibility, NP-completeness, Cook-Levin Theorem, various NP-complete problems, intractable problems, log space, other topics.

Marking Scheme:

• 4 assignments worth 10% each (Due at beginning of tutorials/class) Jan 26, Feb 16, March 16, April 2 (Monday class)
  Assignments are due at the beginning of tutorial/class, since solutions will be discussed during the tutorial/class.
• 1 closed-book test worth 20% (March 2 In tutorial)
• final exam worth 40%

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

• Turing Machines and Reductions
• Computability and Noncomputability
• CFL's and Noncomputability
• NP and NP-Completeness Revised
• Search and Optimization Problems

• Problem Set 1 (2018)
• Problem Set 2 (2018)
• Problem Set 3 (2018)
• Problem Set 4 (2018)

Midterm Test Midterm Test (2018)

Last Year's Problem Sets

• Problem Set 1 (2017)
• Problem Set 2 (2017)
• Problem Set 3 (2017)
• Problem Set 4 (2017)

Last Years' midterm test Midterm Test (2017)