Computer Science 284/484

Advanced Algorithms

Spring 2013

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 12:30pm-13:45pm, CSB 632.
Instructor office hours (CSB 620): 10am-11am Monday, Wednesday, or by appointment.
TA: Rahman Lavaee
TA office hours (CSB 726): 2-3pm Monday, Wednesday, or by appointment.

Textbooks: there is no required textbook; see each section for the recommended reading.

Other resources/recommended reading (most on a 2 hour reserve in the library):

• [CLRS09] Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
• [MU05] Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
• [MR95] Randomized Algorithms, R. Motwani, P. Raghavan, 1995.


• [WS11] The Design of Approximation Algorithms, D.Williamson, D. Shmoys, 2011
• [V04] Approximation Algorithms, V. Vazirani, 2004.


• [K91] The Design and Analysis of Algorithms, D. Kozen, 1991.
• [KT05] Algorithm Design, J. Kleinberg and E. Tardos, 2005.
• [AHU74] The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.


• [BE98] Online Computation and Competitive Analysis, A. Borodin, R. El-Yaniv, 1998.
• [M05] Data Streams: Algorithms and Applications, S. Muthukrishnan, 2005.

Prerequisites: CSC282.

Schedule

TOPIC: Randomized algorithms

reading: chapters 1,2,3,5, and appendix in [CLRS09], chapters 1,2,3,4,7 in [MU05], chapters 1,3,4,6.1,6.2,6.3,6.4,6.5,7.2,7.3 in [MR95].


Jan. 17 Th - 172/282 diagnostic exam (basic data structures, graph algorithms, and dynamic programming), only required for students taking the class on the 400 level.

Jan. 22 Tu - Basics of probability theory, randomized min-cut algorithm.
Jan. 24 Th - Expectation, coupon collector, randomized quicksort, randomized median.

Jan. 29 Tu - Polynomial identity testing (testing matrix product, matchings using Tutte matrix, Isolation Lemma).
Jan. 31 Th - Concentration inequalities, Monte Carlo.

Feb. 5 Tu - Random walks, cover time, hitting time.
Feb. 7 Th - Markov chains, mixing time.



TOPIC: Optimization

reading: chapter 29 in [CLRS09], chapters 21 and 26 in [V04].


Feb. 12 Tu - Linear Programming.
Feb. 14 Th - Semidefinite programming (Max Cut).

Feb. 19 Tu - Metric Embeddings.
Feb. 21 Th - Sparsest cut.


Feb. 26 Tu - EXAM #1 (topics from Jan. 22 - Feb. 21)

TOPIC: Data Structures

reading: Lectures 10 and 11 in [K91], Broder-Mitzenmacher, Demaine, Chapter 8.3 in [MR95].


Feb. 28 Th - Union Find.

Mar. 5 Tu - Dynamic connectivity in amortized O(log^2 n) time.
Mar. 7 Th - Bloom Filters.

Mar. 12 Tu - SPRING BREAK.
Mar. 14 Th - SPRING BREAK.

Mar. 19 Tu - Skip lists.


TOPIC: Online Algorithms

reading: Chapters 1,2,3,4,10 in [BE98], chapter 13 in [MR95].


Mar. 21 Th - Ski rental.

Mar. 26 Tu - Caching, paging, k-server.


TOPIC: Streaming algorithms

reading: Chapters 1,2,3,4 in [M05].


Mar. 28 Th - Heavy hitters.

Apr. 2 Tu - Frequency moments.


Apr. 4 Th - EXAM #2 (topics from Feb. 28 - Apr. 2)

TOPIC: Sampling algorithms

reading: chapters 10,11 in [MU05], chapter 11 in [MR95]


Apr. 9 Tu - Determinant based algorithms, spanning trees, matchings in planar graphs.
Apr. 11 Th - Markov Chains, mixing time.

Apr. 16 Tu - Coupling I.
Apr. 18 Th - Coupling II.

Apr. 23 Tu - Path coupling.
Apr. 25 Th - Coupling from the past I.

Apr. 30 Tu - Coupling from the past II.


May. 8 Wed - comprehensive FINAL EXAM, 7:15pm, CSB 632.

Grading

The grade for the course is the combination of the exam grade and the homework grade. Each exam (midterm) contributes 25% to the exam grade; the final exam contributes 50% to the exam grade.

Homework Rules

• Homework is collected on the due date, before class.
• No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).
• In the final evaluation the lowest homework score will be dropped.
• You may work with other people on the homework, but you must each write up your solutions separately (without any written aid). If you work with other people, indicate who you worked with on your solution.

Test Rules

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

This course follows The University Policy on Academic Honesty .