Computer Science 163/265, Winter 2024: 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 homework and exam problems. They will have their lectures on Monday, Wednesday, and Fridays, 2:00 – 2:50, in Humanities Instruction Building 100. The final exam will be in the same place at the scheduled time: Friday, March 22, 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, Arushi Arora, Alvin Chiu, and Ryuto Kitagawa. There is an online discussion forum on 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 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 8 – January 12):
 
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
 
Week 2 (January 15 – January 19):
 
Holiday Monday, January 15: Martin Luther King, Jr. Day
 
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.
 
Practice problem set 2
Lecture notes: Wednesday, Friday
 
Week 3 (January 22 – January 26):
 
Spreadsheet and critical path scheduling case studies. DAGs and topological ordering.
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.
 
Practice problem set 3
Lecture notes: Monday, Wednesday, Friday
 
Week 4 (January 29 – February 2):
 
Midterm Monday, January 29
 
Preference voting case study and the widest path problem.
Transportation scheduling case study. Euler tours and the traveling salesperson problem.
 
Practice problem set 4
Lecture notes: Wednesday, Friday
 
Week 5 (February 5 – February 9):
 
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.
 
Practice problem set 5
Lecture notes: Monday, Wednesday, Friday
 
Week 6 (February 12 – February 16):
 
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.
 
Practice problem set 6
Lecture notes: Monday, Wednesday, Friday
 
Week 7 (February 19 – February 23):
 
Holiday Monday, February 19: 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.
 
Practice problem set 7
Lecture notes: Wednesday, Friday
 
Week 8 (February 26 – March 1):
 
Midterm Monday, February 26
 
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.
 
Practice problem set 8
Lecture notes: Wednesday, Friday
 
Week 9 (March 4 – March 8):
 
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.
 
Practice problem set 9
Lecture notes: Monday, Wednesday, Friday
 
Week 10 (March 11 – March 15):
 
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.
 
Practice problem set 10
Lecture notes: Monday, Wednesday, Friday
 

Material from Previous Course Offerings

Midterm and final from Fall 2022

Midterm from Winter 2019

The syllabus from Spring 2012 has exams from that year and more links to syllabi and exams from earlier quarters.

Final exam from Spring 2012 (Note: The transitive reduction question concerns material not covered in more recent offerings.)