Computer Science 163, Spring 2012:
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 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%).
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 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.
- Week 5. Transportation scheduling case study.
Euler tours.
Introduction to
the travelling salesman problem.
Whiteboard images from May 1.
- Midterm Thursday, May 3
- 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.
- 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.
- 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.
- 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.
Whiteboard images from May 29.
- 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.
Material from Previous Course Offerings