Computer Science 484

Advanced Algorithms

Spring 2008

TA and office hours:

• Qi Ge (qge) - We 11am-12noon, Fr 11am-12noon.

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

Other resources/recommended reading:

• [KT05] Algorithm Design, J. Kleinberg and E. Tardos, 2005.
• [DPV06] Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani (a draft is available online), 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.
• [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.
• [J03] Counting, Sampling and Integrating (Algorithms and Complexity Series), M. Jerrum, 2003.

Schedule

TOPIC 1: Probabilistic Analysis and Randomized Algorithms

reading: [MR95] Ch. 3, Appendix C; [MU05] Ch. 3; [CLRS01] Appendix C; Babai I
Homework #1

Th 1/17 - Basics (probability space, events, random variables, independence, linearity of expectation, Markov, Chebyshev, coupon collector).
Tu 1/22 - Concentration inequalities (Chernoff-Hoeffding).
Th 1/24 - Markov chains.


TOPIC 2: Max-flow

reading: [CLRS01] Ch. 26;
Homework #2

Tu 1/29 - Ford Fulkerson, Max-flow = Min-cut.
Th 1/31 - Edmonds-Karp, Dinic, max-matching.


TOPIC 3: Matrix Operations/Linear Algebra

reading: [CLRS01] Ch. 28;
Homework #3

Tu 2/5 - Basics (matrix norms, inverse, rank, determinant, congruence, matrix multiplication).
Th 2/7 - Similarity, eigenvalues, SVD, positive semidefiniteness, Cholesky, least squares.
Tu 2/12 - Solving systems of equations, LU/LUP decomposition.


TOPIC 4: Linear Programming

reading: [CLRS01] Ch. 29;
Homework #4

Th 2/14 - Basics (linear programs, duality, Farkas lemma).
Tu 2/19 - Proof of strong duality.
Th 2/21 - Simplex algorithm, discussion of other algorithms (ellipsoid, interior point methods).


TOPIC 5: Fourier Transform

reading: [CLRS01] Ch. 30;
Homework #5

Tu 2/26 - Basics (fourier transform, Plancharel/Parseval, convolution).
Th 2/28 - FFT, Integer multiplication.
Tu 3/4 - Applications (string matching, tomography).


TOPIC 6: String Matching

reading: [CLRS01] Ch. 32;

Th 3/6 - Basic string matching.


MIDTERM: Th 3/18 (NOTE: the midterm date moved)

Tu 3/20 - Knuth-Morris-Pratt, compression using SLPs, word equations.


TOPIC 7: Number-Theoretic Algorithms

reading: [CLRS01] Ch. 31;
Homework #7

Tu 3/25 - Basics (modular arithmetic, modular exponentiation, CRT, prime number theorem).
Th 3/27 - Jacobi/Legendre symbol, quadratic reciprocity, primality testing.
Tu 4/1 - Integer factorization.


TOPIC 8: Computational geometry

reading: [CLRS01] Ch. 33;
Homework #8

Th 4/3 - Convex hull.
Tu 4/8 - Closes pair of points.
Th 4/10 - Voronoi diagrams.


TOPIC 9: Approximation algorithms

reading: [CLRS01] Ch. 35;
Homework #9

Tu 4/15 - Vertex cover/set cover, relaxation, integrality gap.
Th 4/17 - TSP, knapsack.
Tu 4/22 - MaxCut, semidefinite programming.


REVIEW: Th 4/24

FINAL: Tu 4/29

Grading

• Homework: 20% (theoretical) + 20% (applied).
• Midterm: 30%.
• Final: 30%.

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 everybody's one lowest homework score will be dropped.
• Each problem must be written on a separate letter-size paper.
• 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 another person, indicate who you worked with on your solution.