CSC 463H: Computational Complexity and Computability
Fall 2011

Announcements

Final exam marks: Average 65/100 High 94/100
(email me for more information)

Click here to see the final exam.

Lectures: MW 2 in BA 1220

Tutorial: F2 in BA 1220

Instructor: Stephen Cook
email: sacook@cs.toronto.edu
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: Monday 4:15-5:00, Wednesday 4:30-5:30 Or make an appointment, or drop in.
E-MAIL QUESTIONS ARE WELCOME.

Tutor: Frank Vanderzwet

Text: "Introduction to the Theory of Computation", by Michael Sipser. (Second 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 15% each (Due at beginning of tutorials) Sept 30, Oct 21, Nov 11, Dec 2
  Assignments are due at the beginning of tutorial since solutions will be discussed during the tutorial.
• 1 closed-book test worth 10% (Oct 28: In tutorial)
• final exam worth 30%

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 (.ps files from CSC 364H)

• Turing Machines and Reductions
• Computability and Noncomputability
• NP and NP-Completeness

Problem Sets (.ps files)

• Problem Set 1 Due September 30

• Solutions to Problem Set 1 Average Mark: 26/35.

• Problem Set 2 Due October21

• Solutions to Problem Set 2 (Solution to Question 4 simplified Oct 25.)

• Marker's Comments on PS2

• Problem Set 3 (Question 1 revised Nov 3) Due November 11

• Solutions to Problem Set 3

• Marker's Comments on PS3

• Problem Set 4 Due Friday, December 2

• Solutions to Problem Set 4

• Marker's Comments on PS4

Tests (.ps files)

• Midterm Test October 28

• Solutions to Midterm Test October 28

• Marker's comments on Midterm Test