Computer Science 284/484

Advanced Algorithms

Spring 2009

Instructor: Dan Gildea office hours Wed 2-3pm
TA: Yi Chu office hours Tu Th 10-11am

Homeworks

Required text: T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2001, Introduction to Algorithms (2nd edition)

Recommended: Mitzenmacher and Upfal, 2005, Probability and Computing.

Syllabus

Onwe will coverwhich means that after class you will understandif before class you have read
1/15 Probability Theory Chebyshev, coupon collector M&U Ch 3
1/20 Concentration inequalities Chernoff M&U Ch 4
1/22 Bloom filters balls and bins M&U Ch 5.5
1/27 Max-flow Ford-Fulkerson CLRS Ch 26
1/29 max-matching Edmonds-Karp, Dinic
2/3 Linear Algebra norms, inverse, rank, determinant, congruence CLRS Ch 28
2/5 Similarity, eigenvalues SVD, positive semidefiniteness, Cholesky, least squares
2/10 Systems of equations LU/LUP decomposition
2/12 Linear Programming duality, Farkas lemma CLRS Ch 29
2/17 Strong duality
2/19 Simplex algorithm
2/24 Fourier Transform Plancharel/Parseval, convolution CLRS Ch 30
2/26 FFT characters
3/3 FFT applications string matching
3/5 String matching CLRS Ch 32
3/17 Review
3/19 Midterm
3/24 Number Theory CRT, prime number theorem CLRS Ch 31
3/26 Number Theory quadratic reciprocity, primality testing
3/31 Integer Factorization
4/2 Computational geometry convex hull CLRS Ch 33
4/7 closest pair of points
4/9 voronoi digrams
4/14 Approximation Algorithms relaxation, integrality gap CLRS Ch 35
4/16 TSP, knapsack
4/21 max cut semidefinite programming
4/23 Something Fun
4/28 Review come to class with questions!
Final Exam: Wednesday, May 6, 7:15-10:15pm

Grading

  • Final exam: 35%
  • Homeworks: 35%
  • Midterm: 25%
  • Class participation: 5%

gildea @ cs rochester edu
July 27, 2009