|
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
| 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 |
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
|