Computer Science 484

Advanced Algorithms

Spring 2011

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.

• [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

Reading: [CLRS09] chapters 3,4,5; [MR95] chapter 1; [MU05] chapters 1,2,3,4; Babai.

homework 1 (do NOT turn in).


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

Reading: [CLRS09] chapters 10,11,12,13,14,19,21; Erickson-ch16, Erickson-fibo.

homework 2 (do NOT turn in).


Jan. 27 Th - Union-find (basics, path compression, O(m log^* n) upper bound).
Feb. 1 Tu - Dynamic connectivity in amortized O(log² 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

reading: [CLRS] chapter 33.

homework 4 (do NOT turn in).


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

reading: [CLRS] chapter 32, Gusfield97, chapter 7 (handout), Demaine.

homework 5 (do NOT turn in).


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

reading: [CLRS] chapter 29, Ferguson.

homework 6 (do NOT turn in).

applied homework 1 (due April 5th). (Example inputs/outputs: in1, out1, in2, out2)


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

Exam Rules

• All tests are closed book. No text or notes, no scratch paper allowed.

This course follows The University Policy on Academic Honesty .