Computer Science 163/265, Spring 2017:
Graph Algorithms
Announcements:
 Midterm: Thursday, May 4, in class.
Reading: Material from weeks 14.
 Final (comprehensive): Thursday, June 8, 2:003:20pm,
in class. Reading: Material from weeks 110.
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, 11am12:30pm, Thursdays, 9:3011am, Fridays, noon1pm, 23pm,
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.

PrimDijkstraJarnik
algorithm, Boruvka's
algorithm, Kruskal's
algorithm.
MST slides
and
UnionFind 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,
BellmanFord 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.
MSTdoubling
heuristic,
Christofides' heuristic.
 Exponentialtime algorithm for TSP (CS 265 students only).
 Homework 4, Due Friday, May 12.
 Week 6.
 Baseball elimination case study.
Maximumflow slides,
Maximum flow problem,
maxflow
mincut theorem.

augmenting
path (FordFulkerson) algorithm,
EdmondsKarp algorithm.
EdmondsKarp slides
(PDF).

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

Minimum cut problem,
MinCut slides,
Karger's algorithm.
 Homework 5, Due Friday, May 19.
 Week 7.
 Medical
school residency assignment case study.
 Matchings, stable
marriage, GaleShapley 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.

kdegeneracy
(6color theorem).
5color
theorem,
5color theorem proof (except that v should be mindegree, not max),
4color 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ásiAlbert 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)
Degeneracybased triangle listing algorithm (CS 265 students only).
Cliques, MoonMoser
bound on maximal cliques, BronKerbosch
algorithm,
BronKerbosch 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:003: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.