Winter 2017

** Announcements **

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

T2 UC 85 M - Z

** 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)
Jan 27, Feb 17, March 17, March 31

Assignments are due at the**beginning**of tutorial since solutions will be discussed during the tutorial. - 1 closed-book test worth 20% (March 3 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
- NP and NP-Completeness Revised
- Search and Optimization Problems
- CFL's and Noncomputability