ICS 265, Spring 2002:
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.
- 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,
- Week 3: Variations of the flow problem. [NF 1.2, 6.2, 9-10, 15,
- 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.
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:
David Eppstein, Dept.
Information & Computer Science, UC Irvine, 11 Apr 2002