Computer Science 163/265, Spring 2018:
Graph Algorithms
General Course Information
The course meets Monday, Wednesday, and Fridays, 3:00 - 3:50
in Bren Hall, room 1100. Prof. Eppstein's office hours are Mondays and Wednesdays from 4:00 - 5:00 (or by
appointment) in Bren 4082. The teaching assistants are Nil Mamano
(nil.mamano@gmail.com, office hours Wed 2-3, Fri 2-3 and 4-5 in DBH 4061) and
Elham Havvaei (ehavvaei@uci.edu, office hours Mon 2-3 and Tue 3-5 in DBH 4061). We
also have a reader, Kanika Baijal. After the lectures, the lecture
slides will be available for viewing at the TA office hours.
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. Homeworks will typically be assigned on Fridays and due on the following Friday,
electronically in PDF format using gradescope (check your course emails
or the course forum on Piazza for details).
The text we will be using is Graph
Algorithms, a collection of readings compiled from
Wikipedia. Lecture materials will not be distributed to the class; instead, you are encouraged to attend the lecture yourself and take your own notes. Recording the lectures for your own personal use is allowed, but other uses of recorded lectures (including making them available online) is forbidden.
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.
- Homework 1, due
Friday, April 13. To start working from this template, click "clone
this project", and then when your answers are complete, download your
copy by clicking "pdf". However, you are not required to use this
template for your answers. After the
deadline, the same link will be updated with the solutions.
- Week 2.
- Maze
and river network simulation via invasion percolation case
study. Minimum
spanning trees, Prim-Dijkstra-Jarnik
algorithm, Boruvka's
algorithm, Kruskal's
algorithm.
- Spreadsheet case study. DAGs and
topological
ordering.
- Homework 2, due
Friday, April 20.
- Week 3.
- Road map path planning case study.
Shortest paths,
relaxation algorithms,
Dijkstra's algorithm,
Bellman-Ford algorithm,
Johnson's algorithm.
- A*
algorithm.
- Week 4.
- Preference
voting case study and
the widest
path problem.
- Guest lecture Wednesday, April 25: Euler tours.
- Transportation scheduling case study.
Travelling salesman problem.
- Exponential-time dynamic programming for the TSP.
- Week 5.
- Approximation
algorithms and the approximation ratio,
MST-doubling
heuristic,
Christofides' heuristic.
- Review session Wednesday, May 2.
- Midterm Friday, May 4.
- Week 6.
- Baseball
elimination case study. Maximum flow
problem, minimum cut
problem, max-flow
min-cut theorem, augmenting
path (Ford-Fulkerson) algorithm.
- Week 7.
- 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,
Hopcroft–Karp algorithm.
Using
matchings to find vertex covers and independent sets,
partition into a minimum number
of rectangles.
- Week 8.
- 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.
- Week 9.
- Memorial day holiday, Monday, May 28.
- Social network analysis case study.
Social network
properties: sparsity, small
world
property, power
laws. Barabási-Albert model.
Clustering
coefficient, degeneracy
and k-cores, degeneracy-based dynamic triangle counting algorithm.
Cliques, Moon-Moser
bound on maximal cliques, Bron-Kerbosch
algorithm.
- 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, and Fáry's theorem.
- Finals week
- Final examination (cumulative), Mon, June 11, 4:00-6:00pm.
Material from Previous Course Offerings
The syllabus from Spring 2015 has more links, to syllabi and exams from earlier quarters.