ICS 265, Spring 2002:
Graph Algorithms

General Course Information

Coursework will consist of biweekly homeworks, including a homework due in finals week. There will be no exams. 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.9, 7.3, 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.
      Homework due Thurs. June 13th: online assignment