COMP 506
Winter 2007-08
|
|
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, sue@cs.mcgill.ca,
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, nyu3@cs.mcgill.ca, 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 www.cs.mcgill.ca/~sue/506, 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.
Contents:
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
Sources:
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, www.nada.kth.se/~viggo/problemlist/compendium.html
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.