ICS 163, Spring 2002:
Graph Algorithms

General Course Information

Coursework will consist of biweekly homeworks and a comprehensive final exam. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. The course texts will be Network Flows (Ahuja, Magnanti, and Orlin) and Graph Drawing (Di Battista, Eades, Tamassia, and Tollis). The course meets Tuesdays and Thursdays, 2:00 - 3:20 in ICF 101.

Tentative Schedule

• Week 1: Introduction, review, and basic concepts. [NF 1-5]
• Week 2: Maximum flow. [NF 6-8]
      Homework due Thurs. April 18th: NF 6.3, 6.9, 7.4
• Week 3: Variations of the flow problem. [NF 1.2, 6.2, 9-10, 15, 17]
• Week 4: Matching. [NF 12]
      Homework due Thurs. May 2nd: NF 6.2, 9.14, 12.1
• Week 5: Planar graph properties. [GD 1,4]
• Week 6: Planar graph recognition. Straight-line embedding algorithm. [GD 3,4]
      Homework due Thurs. May 16th: GD 3.13, 4.4
• Weeks 7-8: Additional graph drawing topics. [GD 5-11]
      Homework due Thurs. May 30th: GD 4.5, 5.3, 5.4, 7.1
• Week 9: Dynamic graph algorithms.
• Week 10: Exponential-time graph algorithms.