CS369: Advanced Graph Algorithms

Instructor: Tim Roughgarden (Office hours: Thursdays 1-2 PM in Gates 462)

Teaching Assistant: Shaddin Dughmi (Office hours: Tue 1:15-2:15 PM and Wed 11-Noon in Gates 460; Email: shaddin "at" cs)

Time/location: 2:15-3:30 PM on Tuesdays and Thursdays in Gates B12.

Course description: Fast algorithms for fundamental graph optimization problems, including maximum flow, minimum cuts, minimum spanning trees, nonbipartite matching, planar separators and applications, and shortest paths. Data structures including Fibonacci heaps, splay trees, and dynamic trees. Tools from linear programming, matroid theory, minmax theorems, polytope theory, and random sampling. Pre- or corequisite: CS261 or equivalent.

Course requirements: 4 problem sets and a take-home final. Students taking the course for credit should attempt 4 of 5 problems on each. Students taking the course pass/fail should attempt 2 of 5 problems on each. No late assignments accepted.

General references: The following are on two-hour reserve at the Math-CS library.

Detailed schedule and references: