Computer Science 163/265, Spring 2017:
Graph Algorithms

Michael T. Goodrich

Announcements:

• Midterm: Thursday, May 4, in class. Reading: Material from weeks 1-4.
• Final (comprehensive): Thursday, June 8, 2:00-3:20pm, in class. Reading: Material from weeks 1-10.

General Course Information

• Course Description. This course is directed at algorithms for solving fundamental problems in graph theory. It includes topics involving graph representations, graph traversal, network flow, connectivity, graph layout, and matching problems. The prerequisite for CS 163 is CS 161 or CSE 161. The prerequisite for CS 265 is CS 161 and CS 261 (or equivalent).
• Lectures and Office Hours. The course meets Tuesdays and Thursdays, 2:00 - 3:20pm in SSPA 1100. Recording the lectures is not allowed, unless it is for personal use to accommodate a disability. Other uses of recorded lectures (including making them available online) is forbidden. Open laptop computers are not allowed during lectures. Here's why. Prof. Goodrich's office hours are Tuesdays and Thursdays from 3:30 - 4:30pm (or by appointment) in Bren 4091.
• Teaching Assistant and Readers. The teaching assistant is Nil Mamano, office hours Tuesdays, 11am-12:30pm, Thursdays, 9:30-11am, Fridays, noon-1pm, 2-3pm, in Bren 4061. We also have two readers, Elham Havvaei and Pedro Matias.
• Coursework. 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, however, and list the names of his or her collaborator(s). 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 on Fridays, at 11:45pm, and must be submitted electronically in PDF format (not as a scan of a handwritten assignment) via the eee web site. The final grade will be formed by combining the numerical scores from the homeworks (20%), midterm (35%), and final (45%). For the overall total homework score, the lowest homework score will be dropped.
• Textbook The text we will be using is Graph Algorithms, a collection of readings compiled from Wikipedia. Lecture materials will not be distributed to the class; instead, you are encouraged to attend the lecture yourself and take your own notes.
• Academic Honesty. For the UCI honesty policy, please see honesty.uci.edu. Students who are caught cheating in this class (for instance by copying exam solutions or allowing other students to copy from them) risk getting an F in the class or other disciplinary action as allowed by this policy.

Tentative Schedule of Topics

Week 1.

Web crawler case study. Representation of graphs. DFS, BFS, biconnected components. Tarjan's algorithm for strongly connected components.

Homework 1, Due Friday, April 14.

Week 2.

Maze generation and river network simulation via invasion percolation case study. Minimum spanning trees.

Prim-Dijkstra-Jarnik algorithm, Boruvka's algorithm, Kruskal's algorithm. MST slides and Union-Find slides.

The widest path problem.

Homework 2, Due Friday, April 21.

Week 3.

Directed graph slides. DAGs, topological ordering. Shortest Path slides. Shortest paths, Dijkstra's algorithm, Bellman-Ford algorithm.

Homework 3, Due Friday, April 28.

Week 4.

Centrality measures, Betweenness centrality. Johnson's algorithm.
Brandes' algorithm (for CS 265 students only).

All pairs shortest paths via matrix multiplication. Euler tours.

Midterm Study Questions (not due).

Week 5.

Midterm, Thursday, May 4. Here is a Previous Midterm.

Travelling salesman problem. approximation algorithms and the approximation ratio.

Approximation slides. MST-doubling heuristic, Christofides' heuristic.

Exponential-time algorithm for TSP (CS 265 students only).

Homework 4, Due Friday, May 12.

Week 6.

Baseball elimination case study. Maximum-flow slides, Maximum flow problem, max-flow min-cut theorem.

augmenting path (Ford-Fulkerson) algorithm, Edmonds-Karp algorithm. Edmonds-Karp slides (PDF).

Bipartite graphs, formulating bipartite maximum matching as a flow problem.

Minimum cut problem, Min-Cut slides, Karger's algorithm.

Homework 5, Due Friday, May 19.

Week 7.

Medical school residency assignment case study.

Matchings, stable marriage, Gale-Shapley algorithm, Nil's Stable Marriage slides.

Coupon collector's problem. Goodrich's Stable Marriage slides. Hopcroft–Karp algorithm.

Homework 6, Due Friday, May 26.

Week 8.

Register allocation case study. Graph coloring, greedy coloring, interval graphs. Graph Coloring Slides.

Planar graphs, planar duals, Euler's formula.

k-degeneracy (6-color theorem). 5-color theorem, 5-color theorem proof (except that v should be min-degree, not max), 4-color theorem.

Homework 7, Due Friday, June 2.

Week 9.

Social network analysis case study. Social network properties: sparsity, small world property, arboricity, power laws.
Barabási-Albert model. Clustering coefficient. Social Network Analysis slides (PDF).
Triangle Listing slides (PDF) (CS 163 students are responsible for the first 5 slides; CS 265 students are responsible for all)
Degeneracy-based triangle listing algorithm (CS 265 students only).
Cliques, Moon-Moser bound on maximal cliques, Bron-Kerbosch algorithm, Bron-Kerbosch slides.
For fun: Mathematical collaboration distance tool, The Oracle of Bacon.

Final Exam Study Questions (not due).

Week 10.

Planar separators. Boruvka in linear time for planar graphs. Planarity testing, and Fáry's theorem.

Final examination

Final examination (cumulative), Thursday, June 8, in class, 2:00-3:20pm.

Material from Previous Course Offerings

The syllabus from Dr. Eppstein's Graph Algorithms course from Spring 2016 has more links, to syllabi and exams from earlier quarters.