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. The undergraduate (163) and graduate (265) courses will share lectures, and some homework problems; however, the graduate course will have additional homework problems and different exams.

The text we will be using is *Graph
Algorithms*, a collection of readings compiled from Wikipedia.

The course meets Monday, Wednesday, and Fridays, 2:00 - 2:50 in Steinhaus 134. Prof. Eppstein's office hours are Tuesdays 1:30 - 3:00 (or by appointment) in Bren 4082. The T.A. is Jenny Lam; her office hours are Mon 9:00 - 10:30, Wed 10:30-12:00, and Fri 10:30-12 in Bren 4032. Homeworks will be returned during T.A. office hours. We also have Shu "Aimery" Kong as a reader.

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

- Week 1. Web crawler case study. PageRank algorithm. DFS, BFS, Tarjan's algorithm for strongly connected components. Representation of graphs.
- Week 2. Software call graph visualization case study. DAGs, topological ordering, transitive closure, and transitive reduction. Layered graph drawing and the Coffman-Graham algorithm.
- 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.
- Week 4. Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem, augmenting path (Ford-Fulkerson) algorithm.
- Week 5.
Maze
and river network simulation via invasion percolation case
study. Minimum
spanning trees, Prim-Dijkstra-Jarnik
algorithm, Boruvka's
algorithm, Kruskal's
algorithm.

Preference voting case study and the widest path problem.Midterm Friday, May 1

- Week 6.
Transportation scheduling case study.
Euler tours.
Travelling salesman problem.

exponential-time dynamic programming for the TSP, approximation algorithms and the approximation ratio, MST-doubling heuristic, Christofides' heuristic. - Week 7.
Medical
school residency assignment case study. Matchings, stable
marriage, Gale-Shapley
algorithm for stable marriage.

Bipartite graphs, formulating bipartite maximum matching as a flow problem, using matchings to find vertex covers, partition into a minimum number of rectangles. - Week 8. Social network analysis case study. Cliques, Moon-Moser
bound on maximal cliques, Bron-Kerbosch
algorithm.

Social network properties: sparsity, small world property, power laws. Barabási-Albert model, clustering coefficient, h-index based dynamic triangle counting algorithm. - Week 9. Memorial day holiday, Monday, May 25.

Register allocation case study. Graph coloring, greedy coloring, interval graphs, and perfect graphs.

Chordal graphs and using Lexicographic breadth-first search to find an elimination ordering. Recognition of bipartite graphs. - Week 10. Planar graphs; review of planarity-related topics from earlier weeks (graph drawing, road maps, invasion percolation via minimum spanning trees of grid graphs, graph coloring and the four-color theorem). Duality, duality of Euler tours and bipartiteness, Euler's formula, greedy 6-coloring, Boruvka in linear time. Planarity testing, Fáry's theorem and Schnyder's straight-line embedding algorithm.
Final examination (cumulative), Wednesday, Jun 10, 10:30-12:30.

- Syllabus from Winter 2013.
- Syllabus from Spring 2012.
- Syllabus from Spring 2011.
- Syllabus from Spring 2010.
- Syllabus from Spring 2006.
- Syllabus and final exam from Spring 2002.
- Syllabus, midterm, and final exam from Winter 1994.