ICS 163, Spring 2010:
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.
Recommended (but not required) course texts will be Network Flows
(Ahuja, Magnanti, and Orlin) and Graph Drawing (Di Battista, Eades, Tamassia, and
Tollis). The course meets Monday, Wednesday, and Fridays, 2:00 - 2:50,
in Bren Hall, room 1300. My office hours will be Mondays and Tuesdays
3:00 - 3:50, in Bren Hall, room 4214, or by appointment.
The final grade will be formed by combining the numerical scores from
the homeworks (20%), midterm (35%), and final (45%). The reader is Liyan
Tentative Schedule of Topics
- Week 1. Web crawler case study. DFS, BFS, Kosaraju's
algorithm for strongly connected
algorithm. Representation of graphs.
Homework 1, due April 7.
- Week 2. Software call graph visualization case study. DAGs,
Homework 2, due April 14.
- Week 3.
Road map path planning case study.
distance based distance estimation,
landmark-based distance estimation.
Homework 3, due April 21.
- Week 4. Maze
and river network simulation via invasion percolation case
spanning trees, Prim-Dijkstra-Jarnik
graph algorithms, incremental connectivity testing, union-find
Homework 4, due April 28.
- Week 5. Social network analysis case study. Cliques, finding
bound on maximal cliques, Bron-Kerbosch
algorithm. MIDTERM FRIDAY.
- Week 6. Medical
school residency assignment case study. Matchings, stable
algorithm for stable marriage, bipartite
algorithm for bipartite matching.
Homework 5, due May 12.
- Week 7. Rectangular
cartogram case study. Maximum flow
problem, minimum cut
min-cut theorem, formulating maximum matching as a flow problem, baseball elimination, augmenting
path (Ford-Fulkerson) algorithm, bend
minimization via min cost flow, Edmonds-Karp
(shortest augmenting path) algorithm.
Homework 6, due Friday May 21.
- Week 8. Transportation scheduling case study.
the Chinese postman problem,
the travelling salesman problem,
exponential-time dynamic programming for the TSP,
approximation algorithms and the approximation ratio,
Homework 7, due Friday May 28.
- Week 9. Register allocation case study.
perfect elimination ordering,
Homework 8, due Friday June 4.
- Week 10. MEMORIAL DAY HOLIDAY MONDAY.
case study, relative
neighborhood graphs. Planar
graphs; review of planarity-related topics from earlier weeks (graph
drawing, road maps, invasion percolation via minimum spanning trees of
grid graphs, bend minimization in cartograms, graph coloring and the
four-color theorem). Duality,
duality of Euler
tours and bipartiteness,
straight-line embedding algorithm.
Material from Previous Course Offerings