# ICS 163, Spring 2006: Graph Algorithms

## General Course Information

Coursework will consist of weekly homeworks, a midterm, 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, 12:30 - 1:50 in ICF 103.

The final grade will be formed by combining the numerical scores from the homeworks (20%), midterm (35%), and final (45%).

The TA is Matt Johnson, with office hours Mondays 1:00-2:00 and Wednesdays 12:00-1:00 in CS/E 338. There is also a reader, Kebin Xu.

Homework solutions will be posted to the class noteboard on EEE.

## Tentative Schedule

• Week 1: Introduction, review, and basic concepts. [NF 1-5]
Homework, due Tuesday, April 11: NF 2.1, 4.19, 4.42, 5.2, 5.32.
• Week 2: Maximum flow. [NF 6-8]
Homework, due Tuesday, April 18: NF 6.1, 6.11, 6.16, 6.20
• Week 3: Variations of the flow problem. [NF 1.2, 6.2, 9-10, 15, 17]
Homework, due Tuesday, April 25: NF 9.1, 9.7, 9.18, 9.19
• Week 4: Matching. [NF 12]
No homework because of the midterm. Study problems: NF 12.8, 12.10, 12.26, 12.40
• Week 5: MIDTERM TUESDAY. Planar graph properties. [GD 1,4]
• Week 6: Planar graph recognition. Straight-line embedding algorithm. [GD 3,4]
Homework, due Thursday, May 18: GD 3.12, 3.13, 4.2, 4.5
• Week 7: st-Planar Graphs, Tesselation Representation, Dominance Drawing, Orthogonal Drawing and Flow. [GD 4-5]
Homework, due Thursday, May 25: GD 4.16, 5.2, 5.3
• Week 8: Additional graph drawing topics. [GD 6, 8]
Homework, due Thursday, June 1: GD 6.1, 6.2, 8.1
• Week 9: Layered graph drawing [GD 9]; Dynamic graph algorithms.
Homework, due Thursday, June 8: GD 9.3, 9.4, 9.7
• Week 10: Exponential-time graph algorithms.