Graphs & Algorithms

Instructors

Prof. Dr. Angelika Steger, Dan Hefetz

Assistants

Henning Thomas

Time and Place

Wednesday, 10.00 - 12.00 a.m., CAB G 61 (Lecture) and Thursday, 10.00 - 11.00 a.m., CAB H 53 (Exercises)

Exam

Wednesday, 27th May, 10.00 - 12.00 a.m., CAB G 61

Open book exam. You are allowed to use any books, handouts, lecture notes, exercises and solutions and personal notes. The use of electronic devices is not allowed.

The exam is 70% of your final grade. The remaining 30% are covered by graded homework (see Exercises).

Here you find 2007's exam.

Topics

Graphs are an important concept in mathematics and computer science. This lecture presents algorithms for fundamental problems in graph theory. Amongst others, it covers the following topics:

• Trees
• Connectivity
• Matchings
• Hamilton cycles
• Planar graphs
• Coloring
• Extremal graph theory

Participants

Students of Computer Science or Mathematics in the 6th semester or later.

Material

Lecture slides (ETH login required)

Exercises

Regular Exercises: Every week there will be an exercise sheet handed out a couple of days before the exercise class. Students are expected to read and understand the exercises and are welcome to solve them and hand in writeups which will be corrected, but not graded. Solutions will be presented in the exercise class.

Graded Homework: In week 4, 6, 8 and 10 of the term (roughly) we will hand out a specially marked exercise, whose solution (typeset in LaTeX or similar; see our guide to learning LaTeX in the theses section) is due two weeks later. These solutions will be graded, and three best grades will each account for 10% of your final grade. You are welcome to discuss these exercises with your colleagues, but we expect you to hand in your own writeup.

For PhD students the following rule applies for obtaining credit points (KE) for the course. If you successfully solve (grade 4.0 or better) three out of the four special exercises you get a "Testat" and 3 KE. In order to obtain the remaining 3 KE, you have to take and pass the final exam. No credit points are given for simply sitting in the course.

First Exercise session: February 19th. 

Graded Homework

Exercise 01 (pdf)

Exercise 02 (pdf)

Exercise 03 (pdf)

Exercise 04 (pdf)

Regular Exercises

Exercise 01 (pdf) (Solutions (pdf))

Exercise 02 (pdf) (Solutions (pdf))

Exercise 03 (pdf) (Solutions (pdf))

Exercise 04 (pdf) (Solutions (pdf))

Exercise 05 (pdf) (Solutions (pdf))

Exercise 06 (pdf) (Solutions (pdf))

Exercise 07 (pdf) (Solutions (pdf))

Exercise 08 (pdf) (Solutions (pdf))

Exercise 09 (pdf) (Solutions (pdf))

Literature

• D. B. West: Introduction to Graph Theory, Prentice Hall, 2001
• R. Diestel: Graph Theory, Springer-Verlag, 2005
• T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990
• B. Bollobas: Modern Graph Theory, Springer Verlag, 1998
• The Stony Brook Algorithm Repository: A shortened version of Skiena's Algorithm Design Manual. Covers many important algorithms with downloadable implementations.