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 | |
---|---|---|---|
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
Lateness policy