Instructor:
Dan Gildea office hours Wed 23pm
TA: Yi Chu office hours Tu Th 1011am
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
On  we will cover  which means that after class you will understand  if 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 
Maxflow 
FordFulkerson
 CLRS Ch 26 
1/29 
maxmatching 
EdmondsKarp, 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:1510:15pm
Grading
 Final exam: 35%
 Homeworks: 35%
 Midterm: 25%
 Class participation: 5%
gildea @ cs rochester edu
July 27, 2009
