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

- David Eppstein, Mondays 1:30 – 2:30, Bren Hall 4082.
- Nitya Raju, Tuesdays 2:15 – 3:15, Bren Hall 4013.
- Daniel Frishberg, Wednesdays 2:00 – 3:00, online/Zoom (see Ed Discussion for link).
- Evrim Ozel, Thursdays 2:00 – 3:00, Bren Hall 4013.

**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

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