Computer Science 484

Advanced Algorithms

Spring 2007

Instructor: Daniel Stefankovic (office hours: Tu 2pm-3pm, Th 2pm-3pm).
Time: Tu,Th 12:30pm-1:45pm.
Location: Computer Studies Building 601.

TA and office hours:

Textbook: [CLRS01] Introduction to Algorithms (2nd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2001.

Other resources/recommended reading:

Prerequisites: CSC484 Design and Analysis of Efficient Algorithms.

Schedule

Date Topic Reading Due HW
Jan. 18 Th Probability I (basics) [MR95] Ch. 3, Appendix C; [MU05] Ch. 3; [CLRS01] Appendix C; Babai I
Jan. 23 Th Probability II (concentration inequalities) [MU05] Ch. 4 HW 1, due 1/30
Jan. 25 Th Probability III (balls and bins) [MU05] Ch. 5
Jan. 30 Tu Min-Cut, Max-Cut, Fingerprinting [CLRS01] Ch. 28
Feb. 1 Th Linear Algebra review Babai II
Feb. 6 Tu Markov Chains I (cover time) [MR95] Sec 6.1-6.5, Lovasz I
Feb. 8 Th Markov Chains II (mixing time) [MU05] Ch. 7, Ch. 10
Feb. 13 Tu Markov Chains III (counting) [MR95] Ch. 11
Feb. 15 Th Markov Chains IV (coupling) [MU05] Ch. 11
Feb. 20 Tu Markov Chains V (path coupling)
Feb. 22 Th Markov Chains VI (canonical paths) [J03] Ch. 5
Feb. 27 Tu Fourier Transform I (basics) [CLRS01] Ch. 30
Mar. 1 Th Fourier Transform II (expanders) here Sec. 2.1 - 2.4
Mar. 6 Tu Fourier Transform III
Mar. 8 Th MIDTERM
(spring break)
Mar. 20 Tu Algorithms in Number Theory I (basics) [CLRS01] Ch. 31
Mar. 22 Th Algorithms in Number Theory II (primality) [MR95] Ch. 14
Mar. 27 Tu Algorithms in Number Theory III (FFT)
Mar. 29 Th Algorithms in Number Theory III (LLL)
Apr. 3 Tu Linear Programming I (duality, simplex method) [CLRS01] Ch. 29, [DPV06] Ch. 7
Apr. 5 Th Linear Programming II
Apr. 10 Tu Semidefinite Programming Lovasz II
Apr. 12 Th Metric Embeddings I Indyk, Gupta
Apr. 17 Tu Metric Embeddings II
Apr. 19 Th Metric Embeddings III
Apr. 24 Tu Multicommodity flows [CLRS01] Ch. 26, LLR95
Apr. 26 Th Computational Algebra (Groebner basis)
May. 1 Tu String Matching [CLRS01] Ch. 32
May. 9 We FINAL EXAM (7:15pm, CSC 601)

Grading

Homework Rules

This course follows The University Policy on Academic Honesty .