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 text we will be using is *Graph
Algorithms*, a collection of readings compiled from Wikipedia.

The course meets Tuesdays and Thursdays, 12:30 - 1:50 in SSL 290. The T.A. is Paweł Pszona (ppszona@ics.uci.edu); his office hours are Tuesdays 2:00-4:00 and Wednesdays 12:00-2:00 in Bren Hall room 4219. Homeworks will be returned during T.A. office hours. We also have Cesar Ghali as a reader. Instructor office hours will be Thursdays 2:00-3:00 or by appointment.

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. DFS, BFS, Tarjan's
algorithm for strongly connected
components. PageRank
algorithm. Representation of graphs.

Homework 1, due Thursday, April 12 -- Solutions. - Week 2. Software call graph visualization case study. DAGs,
topological
ordering, transitive
closure, and transitive
reduction. Layered
graph drawing and the Coffman-Graham algorithm.

Whiteboard images from April 10. Whiteboard images from April 12.

Homework 2, due Thursday, April 19 -- Solutions. - 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.

Whiteboard images from April 17. Whiteboard images from April 19.

Homework 3, due Thursday, April 26 -- Solutions. - 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.

Preference voting case study and the widest path problem.

Whiteboard images from April 24. Whiteboard images from April 26.

Homework 4, due Thursday, May 3 -- Solutions. - Week 5. Transportation scheduling case study.
Euler tours.
Introduction to
the travelling salesman problem.

Whiteboard images from May 1. - Midterm Thursday, May 3 -- Solutions
- 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, König's theorem, partition into a minimum number of rectangles.

Whiteboard images from May 8. Whiteboard images from May 10.

Homework 5, due Thursday, May 17 -- Solutions. - Week 7. exponential-time dynamic programming for the traveling salesman problem,
approximation algorithms and the approximation ratio,
MST-doubling
heuristic,
Christofides' heuristic.

Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem, formulating maximum matching as a flow problem. Augmenting path (Ford-Fulkerson) algorithm.

Whiteboard images from May 15. Whiteboard images from May 17.

Homework 6, due Thursday, May 24 -- Solutions. - 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.

Whiteboard images from May 22. Whiteboard images from May 24.

Homework 7, due Thursday, May 31 -- Solutions. - Week 9. Memorial day holiday Monday.

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.

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.

Whiteboard images from May 29. Whiteboard images from May 31.

Homework 8, due Thursday, June 8 -- Solutions. - Week 10. Guest lecture by Mike Goodrich: Fáry's theorem and
Schnyder's
straight-line embedding algorithm.

Review session Thursday led by T.A. Paweł Pszona. - Final exam.

- 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.