Computer Science 163/265, Winter 2026: Graph Algorithms

General Course Information

The two courses CS 163 (for undergraduates) and CS 265 (for graduate students) are co-located: they will have the same lectures, but different exam problems. They will have their lectures on Monday, Wednesday, and Fridays, 2:00 – 2:50, Bren Hall 1100. The final exam will be in the same place at the scheduled time: Friday, March 20, 1:30PM – 3:30PM. Lectures and exams will only be offered in-person. The instructor is David Eppstein, and we also have three teaching assistants, Yubin Kim, Cole Groen, and Abraham Illickan. There is an online discussion forum on Ed Discussion, linked from Canvas.

For both courses, I will assign weekly practice problem sets at the start of each week, covering that week's material, and I strongly recommend that all students do these, but they will not be collected and graded. Instead, solutions will be posted at the end of the week to "Resources" in Ed Discussion, and you can expect to see similar problems (or even in some cases the same problems) on the exams. There will be three exams (two midterms and a final) each covering the material from roughly one third of the class (not comprehensive), each equally weighted in the overall course grade. Exams will be closed book, closed notes, and closed friends.

The lecture notes are linked online, starting from last year's lecture notes, and are subject to change until the start of each lecture (possibly also including minor corrections after the lecture). This web page will also include weekly additional reading for the graduate course, related to the topic of each week's material but going beyond the lectures. Undergraduates are welcome to try reading this material as well, but will not be tested on it. I will try to link free copies when I can find them, but you may need to use a UCI internet address to gain access to some of the readings.

The text we will be using is Graph Algorithms, a collection of readings compiled from Wikipedia (unfortunately, there is no published textbook that covers this material with the same depth and focus as this course). The lecture slides will be linked online here, prior to each lecture.

Office hours:

Tentative Schedule of Topics

Week 1 (January 5 – January 9):
 
Extracting information from graph structure: Web search engines and the PageRank algorithm.
Computer representation of graphs and the decorator pattern.
Web crawler case study; review of breadth-first search.
Depth-first search and Tarjan's algorithm for strongly connected components.
 
Practice problem set 1
Lecture notes: Monday, Wednesday, Friday
Graduate reading: "Graph reconstruction with a betweenness oracle, M. Abrahamson, G. Bodwin, E. Rotenberg, and M. Stöckel, STACS 2016.
 
Week 2 (January 12 – January 16):
 
Maze and river network simulation via invasion percolation case study. Minimum spanning trees and their properties.
Prim-Dijkstra-Jarnik algorithm, Boruvka's algorithm, and Kruskal's algorithm.
Spreadsheet and critical path scheduling case studies. DAGs and topological ordering.
 
Week 3 (January 19 – January 23):
 
Holiday Monday, January 19: Martin Luther King, Jr. Day
 
Road map path planning case study. Shortest paths, relaxation, Dijkstra, and Bellman-Ford.
Reweighting: Johnson's algorithm, Suurballe's algorithm, A*, and Landmark-based distance estimation.
 
Week 4 (January 26 – January 30):
 
Midterm Monday, January 26
 
Preference voting case study and the widest path problem.
Transportation scheduling case study. Euler tours and the traveling salesperson problem.
 
Week 5 (February 2 – February 6):
 
Approximation algorithms and the approximation ratio, MST-doubling heuristic, Christofides' heuristic.
Exponential-time dynamic programming for the traveling salesperson problem.
Social network analysis case study. Erdős numbers, the Oracle of Bacon, and the Milgram small-world experiment.
Social network properties: sparsity, small world property, power laws.
Methods for generating synthetic networks: Erdős–Rényi model, ERGM, random graphs with fixed degrees, Barabási-Albert (preferential attachment), Kleinberg's model.
 
Week 6 (February 9 – February 13):
 
Centrality, degeneracy and k-cores.
Cliques, Moon-Moser bound on maximal cliques, Bron-Kerbosch algorithm.
Register allocation case study. Strahler number, graph coloring, greedy coloring, interval graphs.
 
Week 7 (February 16 – February 20):
 
Holiday Monday, February 16: Presidents' Day
 
Chordal graphs, and perfect graphs and using Lexicographic breadth-first search to find an elimination ordering.
Pathwidth, treewidth, the logic of graphs, and Courcelle's theorem.
 
 
Week 8 (February 23 – February 27):
 
Midterm Monday, February 23
 
Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem.
Augmenting path (Ford-Fulkerson) algorithm. New fast algorithms for integer flows.
 
Week 9 (March 2 – March 6):
 
Matchings, Bipartite graphs, formulating bipartite maximum matching as a flow problem.
Using matchings to find vertex covers and independent sets, partition into a minimum number of rectangles.
The assignment problem and the Hungarian algorithm.
Medical school residency assignment case study, stable matching, Gale-Shapley algorithm for stable matching.
 
Week 10 (March 9 – March 13):
 
Planar graphs; review of planarity-related topics from earlier weeks.
Road maps, spanning trees of grid graphs, graph coloring and the four-color theorem.
Duality, duality of Euler tours and bipartiteness, Euler's formula.
Planarity testing and the cycle-based planarity testing algorithm.
Fáry's theorem and Schnyder woods.

Material from Previous Course Offerings

Midterm I, Midterm II, and Final from Winter 2024.