Computer Science 163/265, Spring 2015:
Graph Algorithms

General Course Information

The course meets Monday, Wednesday, and Fridays, 2:00 - 2:50 in Steinhaus 134. Prof. Eppstein's office hours are Tuesdays 1:30 - 3:00 (or by appointment) in Bren 4082. The T.A. is Jenny Lam; her office hours are Mon 9:00 - 10:30 in Bren 4032, Wed 10:30-12:00 in Bren 4013, and Fri 10:30-12 in Bren 3013. We also have Shu "Aimery" Kong as a reader.

Coursework will consist of weekly homeworks, a midterm, and a comprehensive final exam. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. 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 be due electronically in PDF format via the eee web site.

The text we will be using is Graph Algorithms, a collection of readings compiled from Wikipedia. Homework solutions will be posted here.

The final grade will be formed by combining the numerical scores from the homeworks (20%), midterm (35%), and final (45%).

Tentative Schedule of Topics

• Week 1. Web crawler case study. PageRank algorithm. DFS, BFS, Tarjan's algorithm for strongly connected components. Representation of graphs.
  Homework 1, due on eee Friday, April 10.
• Week 2. Software call graph visualization case study. DAGs, topological ordering, transitive closure, and transitive reduction. Layered graph drawing and the Coffman-Graham algorithm.
  Homework 2, due on eee Friday, April 17.
• Week 3. Road map path planning case study. Shortest paths, relaxation algorithms, Dijkstra's algorithm, Bellman-Ford algorithm, Johnson's algorithm.
  A* algorithm, Euclidean distance based distance estimation, landmark-based distance estimation.
  Homework 3, due on eee Friday, April 24.
• Week 4. Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem, augmenting path (Ford-Fulkerson) algorithm.
  Preference voting case study and the widest path problem.
  Homework 4, due on eee Friday, May 1.
• Week 5. Maze and river network simulation via invasion percolation case study. Minimum spanning trees, Prim-Dijkstra-Jarnik algorithm, Boruvka's algorithm, Kruskal's algorithm.
  Homework 5, due on eee Friday, May 8.

  Midterm Friday, May 1

• Week 6. Transportation scheduling case study. Euler tours. Travelling salesman problem.
  exponential-time dynamic programming for the TSP, approximation algorithms and the approximation ratio, MST-doubling heuristic, Christofides' heuristic.
  Homework 6, due on eee Friday, May 15.
• Week 7. Medical school residency assignment case study. Matchings, stable marriage, Gale-Shapley algorithm for stable marriage.
  Bipartite graphs, formulating bipartite maximum matching as a flow problem, using matchings to find vertex covers, partition into a minimum number of rectangles.
  Homework 7, due on eee Friday, May 22.
• Week 8. Social network analysis case study. Social network properties: sparsity, small world property, power laws. Barabási-Albert model.
  Clustering coefficient, degeneracy and k-cores, h-index based dynamic triangle counting algorithm.
  Cliques, Moon-Moser bound on maximal cliques, Bron-Kerbosch algorithm.
  Homework 8, due on eee Friday, May 29.
• Week 9. Memorial day holiday, Monday, May 25.
  Register allocation case study. Graph coloring, greedy coloring, interval graphs, and perfect graphs.
  Chordal graphs and using Lexicographic breadth-first search to find an elimination ordering.
  Homework 9, due on eee Friday, June 5.
• Week 10. Planar graphs; review of planarity-related topics from earlier weeks (graph drawing, road maps, invasion percolation via minimum spanning trees of grid graphs, graph coloring and the four-color theorem).
  Duality, duality of Euler tours and bipartiteness, Euler's formula, greedy 6-coloring, Boruvka in linear time. Planarity testing, Fáry's theorem and Schnyder's straight-line embedding algorithm.

• Final examination (cumulative), Wednesday, Jun 10, 10:30-12:30.

Material from Previous Course Offerings

• Syllabus from Winter 2013.
• Syllabus from Spring 2012.
• Syllabus from Spring 2011.
• Syllabus from Spring 2010.
• Syllabus from Spring 2006.
• Syllabus and final exam from Spring 2002.
• Syllabus, midterm, and final exam from Winter 1994.