Advanced Algorithms

Advanced Algorithms


LEC #TOPICSLECTURE NOTES
1Fibonacci heaps(PDF)
2Network flows(PDF)
3Maximum flow; minimum cost circulation(PDF)
4Goldberg-Tarjan min-cost circulation algorithm(PDF)
5Cancel-and-tighten algorithm; binary search trees(PDF)
6Splay trees(PDF)
7Dynamic trees (part 1)(PDF)
8Dynamic trees (part 2)(PDF)
9Linear programming (LP)(PDF)
10LP: duality, geometry, simplex(PDF)
11LP: complexity; introduction to the ellipsoid algorithm(PDF)
12LP: ellipsoid algorithm(PDF)
13LP: applications of the ellipsoid algorithmNotes not available
14Conic programming I(PDF)
15Conic programming II(PDF)
16Approximation algorithms(PDF)
17Approximation algorithms (facility location)(PDF)
18Approximation algorithms (max-cut)(PDF)
19Max-cut and sparsest-cut(PDF)
20Multi-commodity flows and metric embeddingsNotes not available
21Convex hullsNotes not available
22Convex hulls and fixed dimension LP(PDF)
23Voronoi diagrams(PDF)
24
Approximation scheme for the Euclidean traveling salesman problem
Notes not available
25
Streaming algorithms
Notes not available
26
Streaming algorithms (cont.)
Notes not available