COMP 560
Fall 200607

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:353: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 1112:30
or by appointment
CoInstructor: Dr. Christophe Paul, room 301 McConnell,
3985913, Christophe.Paul@lirmm.fr
Teaching Assistant: TBA
Hours: TBA
Evaluation: homeworks (45) 20%, one midterm (the week before Thanksgiving, possibly in the evening) 20%, presentation (or project) 20%, 3hour 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 universityadministered 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.unihamburg.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