Computer Science 484
Advanced Algorithms
Spring 2011
Instructor:
Daniel Stefankovic (office hours: Thursday 5pm-6pm, Computer Science Building 620).
Class: Tuesday, Thursday 12:30pm-1:45pm, Computer Studies Building 601.
Problem Sessions: Tuesday 5pm-6pm, Computer Studies Building 601.
Textbook:
-
[CLRS09] Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
Other resources/recommended reading (most of these are on the reserve in the library):
-
[MU05]
Probability and Computing: Randomized Algorithms and Probabilistic Analysis,
M. Mitzenmacher, E. Upfal, 2005.
-
[MR95]
Randomized Algorithms,
R. Motwani, P. Raghavan, 1995.
-
[V04]
Approximation Algorithms,
V. Vazirani, 2004.
Prerequisites: CSC282 Design and Analysis of Efficient Algorithms; recommended reading:
-
[KT05]
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
-
[DPV06]
Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, 2006.
-
[K91]
The Design and Analysis of Algorithms, D. Kozen, 1991.
-
[AHU74]
The Design and Analysis of Computer Algorithms,
A. Aho, J. Hopcroft, J. Ulman, 1974.
Schedule
TOPIC: Randomized algorithms
Jan. 13 Th - Basics of probability theory, randomized min-cut algorithm.
Jan. 18 Tu - Expectation, coupon collector, randomized quicksort, randomized median.
Jan. 20 Th - Polynomial identity testing (testing matrix product, matchings using Tutte matrix).
Jan. 25 Tu - Tail inequalities.
TOPIC: Data structures
Jan. 27 Th - Union-find (basics, path compression, O(m log* n) upper bound).
Feb. 1 Tu - Dynamic connectivity in amortized O(log2 n).
Feb. 3 Th - Fibonacci heaps.
Feb. 8 Tu - EXAM #1
TOPIC: Graph algorithms
Reading: [CLRS09] chapters 22, 26 (also chapters 23,24,25 if you did not cover them in your undergraduate course); [K91] chapters 16, 17, 18, 19, 20.
homework 3 (do NOT turn in).
Feb. 10 Th - Flows (Ford-Fulkerson, Max-flow = Min-cut).
Feb. 15 Tu - Flows (Edmonds-Karp, Dinic).
Feb. 17 Th - Matchings, minimum-cost maximum matching (using Bellman-Ford, Dijkstra).
TOPIC: Computational geometry
Feb. 22 Tu - Convex hull (Graham, Jarvis, Chan).
Feb. 24 Th - Sweep paradigm: does a pair of segments intersect?.
Mar. 1 Tu - Voronoi diagrams.
Mar. 3 Th - EXAM #2
Mar. 8 Tu - SPRING BREAK
Mar. 10 Th - SPRING BREAK
TOPIC: String matching
Mar. 15 Tu - KMP.
Mar. 17 Th - Suffix trees - suffix arrays I (applications).
Mar. 22 Tu - Suffix trees - suffix arrays II (linear time construction).
TOPIC: Optimization
Mar. 24 Th - Linear programming, duality.
Mar. 29 Tu - Applications, zero-sum games.
Mar. 31 Th - Ellipsoid method
Apr. 5 Tu - Semidefinite programming.
Apr. 7 Th - Max-Cut, linear programming in small dimensions
Apr. 12 Tu - Metric embeddings (basics)
Apr. 14 Th - EXAM #3
TOPIC: Something fun (*not* tested on exams)
Apr. 19 Tu - MCMC I (stationary distribution, ergodicity, detailed banlance equation).
Apr. 21 Th - MCMC II (coupling).
Apr. 26 Tu - MCMC III.
FINAL EXAM (May 4, Wednesday, 7:15pm, CSB 601)
Grading (subject to change)
- Quizzes: 45% (each quiz is worth 15%).
- Final: 40%.
- Applied homework: 15%.
Policies