Computer Science 163/265, Fall 2022: Graph Algorithms

General Course Information

The course will have lectures on Monday, Wednesday, and Fridays, 11:00 – 11:50, in Engineering Lecture Hall 100. The final exam will be in the same place at the scheduled time: Friday, December 9, 8:00AM – 10:00AM. Lectures and exams will only be offered in-person. The lectures will not be broadcast online or recorded, but the lecture slides will be linked online here. The text we will be using is Graph Algorithms, a collection of readings compiled from Wikipedia. The instructor is David Eppstein, and we also have three teaching assistants, Daniel Frishberg, Nitya Raju, and Evrim Ozel.

Coursework will consist of weekly homeworks, a midterm exam, and a comprehensive end-of-quarter final exam. You may work together on homeworks, but the exams should be your own work, and are closed book and closed notes. Students caught copying in exams are subject to UCI academic honesty policies and may get a failing grade in the course. All homework collection and grading will be done through GradeScope. Each weekly homework set will have one of the assigned problems graded, and will be scored 50% for that problem and 50% for whether it included an answer on the other other problems. 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, on this web page, and due on the following Friday. GradeScope regrade requests will not be accepted after the end of week 10; in particular, regrade requests for the final exam will not be accepted.

The final grade will be formed by combining the numerical scores from the homeworks (with the lowest weekly homework score dropped) and the final exam or homework. The homeworks will count for 20% of the course grade, the midterm will count for 35%, and the final exam will count for 45%.

Office hours:

Tentative Schedule of Topics

Week 0 (September 23):
Extracting information from graph structure: Web search engines and the PageRank algorithm.
Lecture notes: Friday
No homework (first homework will be assigned at end of week 1)
Week 1 (September 26 – September 30):
Computer representation of graphs and the decorator pattern.
Web crawler case study. Review of depth-first search and breadth-first search.
Tarjan's algorithm for strongly connected components.
Lecture notes: Monday, Wednesday, Friday
Homework 1, due Friday, October 7
Week 2 (October 3 – October 7):
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 case study. DAGs and topological ordering.
Lecture notes: Monday, Wednesday, Friday
Homework 2, due Friday, October 14
Week 3 (October 10 – October 14):
Critical path scheduling case study. Shortest and longest paths in directed acyclic graphs.
Road map path planning case study. Shortest paths and relaxation algorithms.
Dijkstra's algorithm, Bellman-Ford algorithm.
Johnson's algorithm, Suurballe's algorithm, A* algorithm.
Landmark-based distance estimation.
Lecture notes: Monday, Wednesday, Friday
Homework 3, due Friday, October 14
Week 4 (October 17 – October 21):
Preference voting case study and the widest path problem.
Transportation scheduling case study. Euler tours and the traveling salesperson problem.
Approximation algorithms and the approximation ratio, MST-doubling heuristic, Christofides' heuristic.
Lecture notes: Monday, Wednesday, Friday
No new homework this week because of next week's midterm
Week 5 (October 24 – October 28):
Exponential-time dynamic programming for the traveling salesperson problem.
MIDTERM Wednesday, October 26
Social network analysis case study. Erdős numbers, the Oracle of Bacon, and the Milgram small-world experiment.
Lecture notes: Monday, Friday
Homework 4, due Friday, November 4
Week 6 (October 31 – November 4):
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.
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.
Lecture notes: Monday, Wednesday, Friday
Homework 5, due Friday, November 11
Week 7 (November 7 – November 11):
Guest lectures by TA Daniel Frishberg:
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.
Lecture notes: Monday, Wednesday
Homework 6, due Friday, November 18
HOLIDAY Friday, November 11: Veteran's Day
Week 8 (November 14 – November 18):
Matchings, Bipartite graphs, Hopcroft–Karp algorithm.
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.
Lecture notes: Monday, Wednesday, Friday
Homework 7, due Friday, November 25
Week 9 (November 21 – November 25):
Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem, formulating bipartite maximum matching as a flow problem.
Augmenting path (Ford-Fulkerson) algorithm.
Lecture notes: Monday, Wednesday
Homework 8, due Friday, December 2
HOLIDAY Friday, November 25: Thanksgiving
Week 10 (November 28 – December 2):
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.
Lecture notes: Monday, Wednesday, Friday
No homework this week

Material from Previous Course Offerings

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