ICS 163, Spring 2011:
Graph Algorithms
General Course Information
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 Monday, Wednesday, and Fridays, 3:00 - 3:50,
in ICS 180. My office hours will be Mondays and Tuesdays
4:00 - 4: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
Lowell Trott.
Tentative Schedule of Topics
- Week 1. Web crawler case study. DFS, BFS, Tarjan's
algorithm for strongly connected
components. PageRank
algorithm. Representation of graphs.
Homework 1, due Wednesday, April 6 — solutions.
- Week 2. Software call graph visualization case study. DAGs,
topological
ordering, transitive
closure, transitive
reduction, layered
graph drawing, Coffman-Graham layering.
Homework 2, due Wednesday, April 13 — 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.
Homework 3, due Wednesday, April 20 — 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.
Homework 4, due Wednesday, April 27 — solutions.
- Weeks 4-5. 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.
- Midterm Friday, April 29 — 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.
Homework 5, due Wednesday, May 11 — solutions.
- Week 7. 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, capacity scaling, Edmonds-Karp
(shortest augmenting path) algorithm. Widest path problem, preference voting case study.
Homework 6, due Wednesday, May 18 — solutions.
- Week 8. Social network analysis case study. Cliques, Moon-Moser
bound on maximal cliques, Bron-Kerbosch
algorithm (guest lectures Monday and Wednesday by Darren Strash).
Clustering
coefficient, Dynamic
graph algorithms, h-index based dynamic triangle counting algorithm.
Homework 7, due Wednesday, May 25 — solutions.
- 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 3 — solutions.
- Week 10. Memorial day holiday Monday. 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,
Fáry's theorem,
Schnyder's
straight-line embedding algorithm.
Material from Previous Course Offerings