# 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.

## Material from Previous Course Offerings