Computer Science 163/265, Spring 2017:
- 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)
Open laptop computers are not allowed during lectures.
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
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
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.
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.
algorithm for strongly connected
- Homework 1, Due Friday, April 14.
- Week 2.
- Maze generation
and river network simulation via invasion percolation case
- Homework 2, Due Friday, April 21.
- Week 3.
Directed graph slides.
Shortest Path slides.
- Homework 3, Due Friday, April 28.
- Week 4.
algorithm (for CS 265 students only).
All pairs shortest paths via matrix multiplication.
- 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.
- Exponential-time algorithm for TSP (CS 265 students only).
- Homework 4, Due Friday, May 12.
- Week 6.
- Baseball elimination case study.
Maximum flow problem,
path (Ford-Fulkerson) algorithm,
Bipartite graphs, formulating bipartite maximum matching as a flow problem.
Minimum cut problem,
- Homework 5, Due Friday, May 19.
- Week 7.
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.
- Homework 6, Due Friday, May 26.
- Week 8.
- Register allocation case study.
Graph Coloring Slides.
5-color theorem proof (except that v should be min-degree, not max),
- Homework 7, Due Friday, June 2.
- Week 9.
Social network analysis case study.
properties: sparsity, small
Social Network Analysis slides
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).
bound on maximal cliques, Bron-Kerbosch
Mathematical collaboration distance tool, The Oracle of Bacon.
- Final Exam Study Questions (not due).
- Week 10.
Boruvka in linear time for planar graphs.
Planarity testing, and Fáry's theorem.
- Final examination
- Final examination (cumulative), Thursday, June 8, in class,
Material from Previous Course Offerings
Dr. Eppstein's Graph Algorithms course from Spring 2016 has more links, to syllabi and exams from earlier quarters.