CSC363 - Computational Complexity and Computability (Summer 2005)

This is the administrative page. Go to: Teaching page.

Instructor
Matei David
Email: matei at cs toronto edu
Office: SF4302-F. I'm sharing this office with others, so generally I will hold office hours somewhere else.
Phone: 416-946-3924. This one is shared, too, so don't be shy and ask for Matei.

Timetable
Lectures: Tuesdays, 6-8pm, MP202.
Instructor Office Hours: Thursdays 5-6pm, BA3234. Send me an email if you want to meet some other time.
Tutorials: Tuesdays, 8-9pm.
your last name room TA name email
A - K BA1230 Enping Tu passtu at cs
L - P BA3008 Nazanin Mirmohammadi nazanin at cs
Q - Z BA3012 Mihaela Gheorghiu mg at cs

Recommended books
M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997. This is the main book I will be following. We will be interested in chapters 3, 4, 5, 7 and possibly 10. A new edition of this book is due soon, and the main difference between the two is that the second one contains answers to selected exercises. However, the old edition will do.

M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. (1979) This book is an excellent reference, and contains a large compendium of NP-complete problems in the back.

Cormen, Leiserson, Rivest and Stein. Introduction to algorithms (second edition). McGraw-Hill, 2001. This book is mainly concerned with algorithms, and some other courses may be based on it. For our purposes, chapters 34 and 35 are relevant.

Grading scheme

In order to pass this course, you must achieve a grade of at least 40% on the final exam.

Lateness policy

Due dates

Links