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