COMP 506
Introduction to Complexity Theory

Winter 2007-08
Prof. Whitesides

General Information

Prerequisites: a grade of C or higher in COMP 330 or COMP 360 or COMP 362 if you are an undergraduate, or the equivalent background if you are a graduate student. Please see the instructor if you have not had the prerequisite. This is to avoid having your registration cancelled by the system.

Course Goals: Students should come away from the course with good facility at reading and understanding NP-completeness and NP-hardness proofs and some skill at inventing their own proofs, plus some knowledge of methods for dealing with intractable problems and of current research themes in the area. There will be some in-class problem solving workshops.

Time and Place: TuTh, 1:05-2:25pm Trottier Building room 2100

Instructor: Prof. Whitesides,, room 318 McConnell, 398-7071 x00071
Hours: (Winter 2007-08) room 318 McConnell, Mon. 3-4pm and Wed. 10-noon, or by appointment

Teaching Assistant: Nathan Yuo,, room 305A McConnell
Hours: by appointment

Textbook: Course Pack for COMP 506, available in the McGill bookstore.

Evaluation: homeworks 15%, one midterm 20%, presentation or term paper or project 20%, class participation 5%, 3-hour final exam 40%; alternatively, for those who have been participating regularly in the class, the final exam can count for 100%. There will be about 4-5 assignments. The midterm will likely take place Thursday, February 21, just before the break.
Class Participation: There will be group work in class from time to time, and students will participate in the evaluation of the class presentations. While announcements and information will appear on the course web page at, it is expected that students regularly participate in class as they are responsable for the content and information given in class. This is not a course to take if it conflicts with a job, for example. Note that the opportunity to have the final exam count for 100%, if that would improve the course grade, is contingent on regular class participation.
No extra work is available to improve a mark. For those who are eligible, a university-administered supplemental exam will be given. The mark on the supplemental will count for 100% of the new course mark.

Academic Integrity: This is essential. If you are ever in doubt about what is expected or allowed on homeworks and exams, and how to cite references and sources properly for your class presentation, please ask the instructor. McGill has an academic integrity web site. The principle of academic integrity (e.g., respect for others, not misrepresenting the work of others as your own, crediting sources you have used) is an essential part of our community at McGill. As evidence of that, there is even an entire web site devoted to the issue of academic integrity at McGill. In general, you may work together on homework, but what you hand in should be your own formulation of the solution, which you should be prepared to explain and defend if asked to do so. Also, should should indicate on homework the names of the people you have worked with. You are not to look for solutions on the web, in books, etc. The exams will be in-class, done on your own. No books, notes, etc. The sources you use for your presentation, whether on the web or from the literature, must be fully cited, so that the class can easily find them.

The first part of the course will consist of lectures on the fundamentals of the subject: 1) Introduction: problems and algorithms 2) Review of Turing machines as models for sequential algorithms 3) Complexity classes and relations among them 4) Problem reducability and the relative difficulty of problems 5) NP-completeness, statement of Cook's Theorem 6) Examples of NP-completeness proofs 7) Proof of Cook's Theorem

The second part of the course will discuss some approaches to take once a problem we want to solve has been proved NP-complete or harder: approximation techniques, non-approximability results, the notion of fixed parameter tractability.

The third part of the course consists of student presentations of approximation techniques or complexity results from the research literature.

Background (references for prerequisites):

T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill, 1990, ISBN 0-262-03293-7

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997, ISBN 0-534-94728-X


G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchette-Spaccamela, and M. Protasi, Complexity and Approximation, 1999, 3-540-65431-3.

P. Crescenzi and V. Kann, A compendium of NP optimization problems,

R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999, ISBN 0-387-94883-X

Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0716710447 (out of print)

Dorit Hochbaum, ed., Approximation Algorithms for NP-hard Problems, PWS Publishing Co., 1997, ISBN 0-534-94968-1

Juraj Hromkovic, Algorithmics for Hard Problems, Springer-Verlag, Berlin, 2nd edition, 2003, ISBN 3-540-44134-4

Jon Kleinberg and Eva Tardos, Algorithm Design, Pearson Education Inc., Boston, 2006, ISBN 0321295358

Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford U. Press, 2006, ISBN 0198566077

Vijay Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2003, ISBN 3-540-65367-8

Return to COMP 506 home page.