Computer Science 484
Advanced Algorithms
Spring 2008
Instructor:
Daniel Stefankovic (office hours: Tu 2pm3pm, Th 2pm3pm).
Time: Tu,Th 12:30pm1:45pm.
Location: Computer Studies Building 601.
TA and office hours:
 Qi Ge (qge)  We 11am12noon, Fr 11am12noon.
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.
Prerequisites: CSC282 Design and Analysis of Efficient Algorithms.
Schedule
TOPIC 1: Probabilistic Analysis and Randomized Algorithms
Th 1/17  Basics (probability space, events, random variables, independence, linearity of expectation, Markov, Chebyshev, coupon collector).
Tu 1/22  Concentration inequalities (ChernoffHoeffding).
Th 1/24  Markov chains.
TOPIC 2: Maxflow
Tu 1/29  Ford Fulkerson, Maxflow = Mincut.
Th 1/31  EdmondsKarp, Dinic, maxmatching.
TOPIC 3: Matrix Operations/Linear Algebra
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
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
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  KnuthMorrisPratt, compression using SLPs, word equations.
TOPIC 7: NumberTheoretic Algorithms
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
Th 4/3  Convex hull.
Tu 4/8  Closes pair of points.
Th 4/10  Voronoi diagrams.
TOPIC 9: Approximation algorithms
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
lettersize 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.
This course follows
The University Policy on Academic Honesty .