Computer Science 163, Spring 2012:
General Course Information
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 text we will be using is Graph
Algorithms, a collection of readings compiled from Wikipedia.
The course meets Tuesdays and Thursdays, 12:30 - 1:50
in SSL 290.
The T.A. is Paweł
Pszona (firstname.lastname@example.org); his office hours are Tuesdays 2:00-4:00
and Wednesdays 12:00-2:00 in Bren Hall room 4219. Homeworks will be
returned during T.A. office hours. We also have Cesar Ghali as a reader.
Instructor office hours will be Thursdays 2:00-3:00 or by appointment.
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. DFS, BFS, Tarjan's
algorithm for strongly connected
algorithm. Representation of graphs.
Homework 1, due Thursday, April 12 -- Solutions.
- Week 2. Software call graph visualization case study. DAGs,
closure, and transitive
graph drawing and the Coffman-Graham algorithm.
Whiteboard images from April 10.
Whiteboard images from April 12.
Homework 2, due Thursday, April 19 -- Solutions.
- Week 3.
Road map path planning case study.
distance based distance estimation,
landmark-based distance estimation.
Whiteboard images from April 17.
Whiteboard images from April 19.
Homework 3, due Thursday, April 26 -- Solutions.
- Week 4. Maze
and river network simulation via invasion percolation case
spanning trees, Prim-Dijkstra-Jarnik
voting case study and
Whiteboard images from April 24.
Whiteboard images from April 26.
Homework 4, due Thursday, May 3 -- Solutions.
- Week 5. Transportation scheduling case study.
the travelling salesman problem.
Whiteboard images from May 1.
- Midterm Thursday, May 3 -- Solutions
- Week 6. Medical
school residency assignment case study. Matchings, stable
algorithm for stable marriage.
algorithm for bipartite matching,
partition into a minimum number of rectangles.
Whiteboard images from May 8.
Whiteboard images from May 10.
Homework 5, due Thursday, May 17 -- Solutions.
- Week 7. exponential-time dynamic programming for the traveling salesman problem,
approximation algorithms and the approximation ratio,
elimination case study. Maximum flow
problem, minimum cut
min-cut theorem, formulating maximum matching as a flow problem. Augmenting
path (Ford-Fulkerson) algorithm.
Whiteboard images from May 15.
Whiteboard images from May 17.
Homework 6, due Thursday, May 24 -- Solutions.
- Week 8. Social network analysis case study. Cliques, Moon-Moser
bound on maximal cliques, Bron-Kerbosch
properties: sparsity, small
laws. Barabási-Albert model,
based dynamic triangle counting algorithm.
Whiteboard images from May 22.
Whiteboard images from May 24.
Homework 7, due Thursday, May 31 -- Solutions.
- Week 9. Memorial day holiday Monday.
Register allocation case study.
and perfect graphs.
breadth-first search to find an elimination ordering.
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 of Euler
tours and bipartiteness,
greedy 6-coloring, Boruvka in linear time,
Whiteboard images from May 29.
Whiteboard images from May 31.
Homework 8, due Thursday, June 8 -- Solutions.
- Week 10. Guest lecture by Mike Goodrich: Fáry's theorem and
straight-line embedding algorithm.
Review session Thursday led by T.A. Paweł Pszona.
- Final exam.
Material from Previous Course Offerings