Computer Science 163/265, Spring 2016:
Graph Algorithms

General Course Information

The course meets Monday, Wednesday, and Fridays, 2:00 - 2: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 assistant is Nitin Agarwal, office hours Tuesdays 3:00 - 4:00 in DBH 3013 and Wednesdays 5:00 - 6:00 in DBH 4011. We also have two readers, Shu Kong and Jia Chen.

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 via the eee web site.

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%).

For the UCI honesty policy, please see honesty.uci.edu. Students who are caught cheating in this class (for instance by copying exam solutions or allowing other students to copy from them) risk getting an F in the class or other disciplinary action as allowed by this policy.

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 8.

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.

Preference voting case study and the widest path problem.

Homework 2, Due Friday, April 15.

Week 3.

No class Monday, April 11, or Wednesday, April 13.

DAGs and topological ordering.

Homework 3, Due Friday, April 22.

Week 4.

Road map path planning case study. Shortest paths, relaxation algorithms, Dijkstra's algorithm, Bellman-Ford algorithm, Johnson's algorithm.

A* algorithm, Euclidean distance based distance estimation, landmark-based distance estimation.

Homework 4, Due Friday, April 29.

Week 5.

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.

Week 6.

Midterm, Monday, May 2.

Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem, augmenting path (Ford-Fulkerson) algorithm.

Homework 5, Due Friday, May 13.

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.

Homework 6, Due Friday, May 20.

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.

Guest lecture Friday, May 20: Mike Goodrich on graph drawing

Homework 7, Due Friday, May 27.

Week 9.

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.

Homework 8, Due Friday, June 3.

Week 10.

Memorial day holiday, Monday, May 30.

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), Wednesday, Jun 8, 10:30-12:30.

Material from Previous Course Offerings

The syllabus from Spring 2015 has more links, to syllabi and exams from earlier quarters.