ICS 163, Spring 2010:
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.
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.
Tentative Schedule of Topics
- 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.
Material from Previous Course Offerings