COMP 560
Graph Algorithms and Applications

Fall 2006-07
Prof. Whitesides


General Information


Prerequisites: COMP 360 or MATH 343; higher versions of these courses are fine. There is no required programming. Please see the instructor if you believe you are qualified to take the course but did not take exactly a course on the above list, or its equivalent at another university.


Course Goals: See how basic graph theory can combine with an algorithmic approach to yield solutions to problems modeled by graphs. Survey recent results in graph theory that are essential background for research on graphs and problems modeled by graphs.


Time and Place: TuTh, 2:35-3:55, the building known as SH688, which is a highrise near the corner of University St. and Sherbrooke West, at 688 Sherbrooke West. The room number is 455.


Instructor: Prof. Whitesides, room 318 McConnell, sue@cs.mcgill.ca
Hours: (Fall 2006, until Nov. 29) MW 11-12:30 or by appointment


Co-Instructor: Dr. Christophe Paul, room 301 McConnell, 398-5913, Christophe.Paul@lirmm.fr


Teaching Assistant: TBA
Hours: TBA

Evaluation: homeworks (4-5) 20%, one midterm (the week before Thanksgiving, possibly in the evening) 20%, presentation (or project) 20%, 3-hour final exam 40% (or 100%, whichever gives the higher mark)

There is no extra work available to improve a mark. For those who are eligible, a university-administered supplemental exam will be given in May, 2007. The mark on the supplemental will count for 100% of the new course mark.

It is expected that you come to class.

All questions about marks for homework and the midterm and the presentation (e.g, missing marks, incorrectly recorded marks, requests for regrades, etc.) must be raised no later than the last day of the course.


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 an entire web site devoted to the issue of academic integrity at McGill.


Textbook: The text is Introduction to Graph Theory, by Douglas West, Prentice Hall, available in the Book Store.

Reference: Graph Theory, by Reinhard Diestel. This is available by free download from Diestel's website: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/


Background reading: For those who want to review the basic graph algorithms (e.g., didn't take COMP 360 or equivalent), the material is in Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, second edition, referred to as CLRS. .


Contents: (See the Approximate Course Contents for more details;

cycles, matching, connectivity, network flows, planarity, colouring, chordal graphs, spectral graph theory, path and tree decompositions; examples of applications e.g., to layout and visualization problems in 2D and 3D, to clustering problems, to expander networks for telecommunications, to computational biology





back to COMP 560 home page.