Graph Algorithms

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.
Recommended (but not required) course texts will be *Network Flows*
(Ahuja, Magnanti, and Orlin) and *Graph Drawing* (Di Battista, Eades, Tamassia, and
Tollis). The course meets Monday, Wednesday, and Fridays, 2:00 - 2:50,
in Bren Hall, room 1300. My office hours will be Mondays and Tuesdays
3:00 - 3:50, in Bren Hall, room 4214, or by appointment.

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

- Week 1. Web crawler case study. DFS, BFS, Kosaraju's
algorithm for strongly connected
components. PageRank
algorithm. Representation of graphs.

Homework 1, due April 7. - Week 2. Software call graph visualization case study. DAGs,
topological
ordering, transitive
closure, transitive
reduction, layered
graph drawing.

Homework 2, due April 14. - Week 3.
Road map path planning case study.
Shortest paths,
relaxation algorithms,
Dijkstra's algorithm,
Bellman-Ford algorithm,
Johnson's algorithm,
A*
algorithm,
15-puzzle example,
Euclidean
distance based distance estimation,
landmark-based distance estimation.

Homework 3, due April 21. - Week 4. Maze
and river network simulation via invasion percolation case
study. Minimum
spanning trees, Prim-Dijkstra-Jarnik
algorithm, Boruvka's
algorithm, Kruskal's
algorithm. Dynamic
graph algorithms, incremental connectivity testing, union-find
data structure.

Homework 4, due April 28. - Week 5. Social network analysis case study. Cliques, finding triangles, Moon-Moser bound on maximal cliques, Bron-Kerbosch algorithm. MIDTERM FRIDAY.
- Week 6. Medical
school residency assignment case study. Matchings, stable
marriage, Gale-Shipley
algorithm for stable marriage, bipartite
graphs, Hopcroft-Karp
algorithm for bipartite matching.

Homework 5, due May 12. - Week 7. Rectangular
cartogram case study. Maximum flow
problem, minimum cut
problem, max-flow
min-cut theorem, formulating maximum matching as a flow problem, baseball elimination, augmenting
path (Ford-Fulkerson) algorithm, bend
minimization via min cost flow, Edmonds-Karp
(shortest augmenting path) algorithm.

Homework 6, due Friday May 21. - Week 8. Transportation scheduling case study.
Euler tours,
the Chinese postman problem,
the travelling salesman problem,
exponential-time dynamic programming for the TSP,
approximation algorithms and the approximation ratio,
MST-doubling
heuristic,
Christofides' heuristic.

Homework 7, due Friday May 28. - Week 9. Register allocation case study.
Graph coloring,
greedy coloring,
intersection graphs,
interval graphs,
chordal graphs,
perfect graphs,
perfect elimination ordering,
lexicographic BFS.

Homework 8, due Friday June 4. - Week 10. MEMORIAL DAY HOLIDAY MONDAY. Sensor network localization case study, relative neighborhood graphs. Planar graphs; review of planarity-related topics from earlier weeks (graph drawing, road maps, invasion percolation via minimum spanning trees of grid graphs, bend minimization in cartograms, graph coloring and the four-color theorem). Duality, duality of Euler tours and bipartiteness, Euler's formula, Fáry's theorem, Schnyder's straight-line embedding algorithm.

- Syllabus from Spring 2006.
- Syllabus and final exam from Spring 2002.
- Syllabus, midterm, and final exam from Winter 1994.