Computer Science 163/265, Winter 2013:
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 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, 11:00 - 11:50
in ICS 174.
Prof. Eppstein's office hours are Tuesdays 1:00 - 3:00 (or by
appointment) in Bren 4214.
The T.A. is Michael
Bannister; his office hours are Wednesdays 1:00 - 3:00 (Bren 4013)
and Thursdays 10:00 - 12:00 (Bren 3011). Homeworks will be
returned during T.A. office hours. We also have Mehdi Sadri as a reader.
The final grade will be formed by combining the numerical scores from
the homeworks (20%), midterm (35%), and final (45%).
Tentative Schedule of Topics
- Week 1. Web crawler case study. PageRank
algorithm. DFS, BFS, Tarjan's
algorithm for strongly connected
components. Representation of graphs.
Whiteboard images from January 7.
Whiteboard images from January 9.
Whiteboard
images from January 11.
Homework 1, due Friday, January 18.
- 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 January 14.
Whiteboard
images from January 16.
Whiteboard
images from January 18.
Homework 2, due Friday, January 25
- Week 3.
Martin Luther King, Jr. Day (holiday), Monday, January 21.
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 January 23.
Whiteboard
images from January 25.
Homework 3, due Friday, February 1
- Week 4.
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 January 28.
Whiteboard
images from January 30.
Whiteboard
images from February 1.
Homework 4, due Friday, February 8
- Week 5. Baseball
elimination case study. Maximum flow
problem, minimum cut
problem, max-flow
min-cut theorem, augmenting
path (Ford-Fulkerson) algorithm.
Midterm Friday, February 8
Whiteboard
images from February 4.
Whiteboard
images from February 6.
Homework 5, due Friday, February 15
- 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.
Whiteboard
images from February 11.
Whiteboard
images from February 13.
Whiteboard
images from February 15.
Homework 6, due Friday, February 22
- Week 7.
Presidents' Day (holiday), Monday, February 18.
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.
Whiteboard
images from February 20.
Whiteboard
images from February 22.
Homework 7, due Friday, March 1
- 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 February 25.
Whiteboard
images from February 27.
Whiteboard
images from March 1.
Homework 8, due Friday, March 8
- Week 9. 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.
Whiteboard
images from March 4.
Whiteboard
images from March 6.
Homework 9, due Friday, March 15
- 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.
Material from Previous Course Offerings