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

T2 RW 140 M - Z

(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

** Midterm Test **
Midterm Test (2018)

** Last Year's Problem Sets **

** Last Years' midterm test **
Midterm Test (2017)