Computer Science 163/265, Spring 2017:
Graph Algorithms

Michael T. Goodrich


General Course Information

Tentative Schedule of Topics

Week 1.
Web crawler case study. Representation of graphs. DFS, BFS, biconnected components. Tarjan's algorithm for strongly connected components.
Homework 1, Due Friday, April 14.
Week 2.
Maze generation and river network simulation via invasion percolation case study. Minimum spanning trees.
Prim-Dijkstra-Jarnik algorithm, Boruvka's algorithm, Kruskal's algorithm. MST slides and Union-Find slides.
The widest path problem.
Homework 2, Due Friday, April 21.
Week 3.
Directed graph slides. DAGs, topological ordering. Shortest Path slides. Shortest paths, Dijkstra's algorithm, Bellman-Ford algorithm.
Homework 3, Due Friday, April 28.
Week 4.
Centrality measures, Betweenness centrality. Johnson's algorithm.
Brandes' algorithm (for CS 265 students only).
All pairs shortest paths via matrix multiplication. Euler tours.
Midterm Study Questions (not due).
Week 5.
Midterm, Thursday, May 4. Here is a Previous Midterm.
Travelling salesman problem. approximation algorithms and the approximation ratio.
Approximation slides. MST-doubling heuristic, Christofides' heuristic.
Exponential-time algorithm for TSP (CS 265 students only).
Homework 4, Due Friday, May 12.
Week 6.
Baseball elimination case study. Maximum-flow slides, Maximum flow problem, max-flow min-cut theorem.
augmenting path (Ford-Fulkerson) algorithm, Edmonds-Karp algorithm. Edmonds-Karp slides (PDF).
Bipartite graphs, formulating bipartite maximum matching as a flow problem.
Minimum cut problem, Min-Cut slides, Karger's algorithm.
Homework 5, Due Friday, May 19.
Week 7.
Medical school residency assignment case study.
Matchings, stable marriage, Gale-Shapley algorithm, Nil's Stable Marriage slides.
Coupon collector's problem. Goodrich's Stable Marriage slides. Hopcroft–Karp algorithm.
Homework 6, Due Friday, May 26.
Week 8.
Register allocation case study. Graph coloring, greedy coloring, interval graphs. Graph Coloring Slides.
Planar graphs, planar duals, Euler's formula.
k-degeneracy (6-color theorem). 5-color theorem, 5-color theorem proof (except that v should be min-degree, not max), 4-color theorem.
Homework 7, Due Friday, June 2.
Week 9.
Social network analysis case study. Social network properties: sparsity, small world property, arboricity, power laws.
Barabási-Albert model. Clustering coefficient. Social Network Analysis slides (PDF).
Triangle Listing slides (PDF) (CS 163 students are responsible for the first 5 slides; CS 265 students are responsible for all)
Degeneracy-based triangle listing algorithm (CS 265 students only).
Cliques, Moon-Moser bound on maximal cliques, Bron-Kerbosch algorithm, Bron-Kerbosch slides.
For fun: Mathematical collaboration distance tool, The Oracle of Bacon.
Final Exam Study Questions (not due).
Week 10.
Planar separators. Boruvka in linear time for planar graphs. Planarity testing, and Fáry's theorem.

Final examination
Final examination (cumulative), Thursday, June 8, in class, 2:00-3:20pm.

Material from Previous Course Offerings

The syllabus from Dr. Eppstein's Graph Algorithms course from Spring 2016 has more links, to syllabi and exams from earlier quarters.