Fall 2010
Schedule:
Outlines due: Wednesday, Nov. 17, in class.
Presentations: Nov. 24–Dec. 6.
Papers due: Friday, Dec.~17, at noon.
We will schedule project presentations during the last two weeks of classes. Depending on class size, some presentations may be outside the usual lecture time.
Hand in your solutions to the "basic" problems by the specified due date (at the start of class).
If you submit solutions for the "advanced" problems by the due date, I will give you feedback on them; in any case, you may submit solutions to "advanced" problems until the last day of class.
First problem set now available in postscript and PDF. Due date Oct. 6.
Second problem set now available in postscript and PDF. Due date Nov. 8 (extended from Nov. 3).
Do your own work on all problems. If you inadvertantly run across a solution, consult the instructor as soon as possible.
Jonathan Buss, DC 3353, x34428, jfbuss%cs.uwaterloo.ca.
Office hours: Mondays and Wednesdays, 10:40–12:00. Please feel free to drop by with course questions or just to chat. You can often find me in at other times; email or phone to make sure.
Mondays and Wednesdays, 9:00–10:30, MC 2036. (Not 2036A!)
We will use two main sources:
S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Roughly two-thirds of the course will come from this book. It also makes a good reference on complexity theory; I recommend that you obtain your own copy.
J. Buss, Hardness of Fixed-Parameter Problems.
The following references also have material of interest.
Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
Uwe Schöning and Randall Pruim, Gems of Theoretical Computer Science, Springer, 1995.
Ming Li and Paul Vitanyi, Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997.
You should be familiar with the basics of computational complexity: the Turing machine model, time and space bounds, complexity classes (e.g. P and NP), and complete problems. For those who have taken UW courses, either CS 365 or both CS 360 and CS 341 will suffice.
Syllabus continually under construction.