Advanced Algorithms

Course Description

This is a graduate course on the design and analysis of algorithms, covering several advanced topics not studied in typical introductory courses on algorithms. It is especially designed for doctoralstudents interested in theoretical computer science.

Lecture Notes

The students in this course were required to take turns scribing lecture notes. They were provided with detailed instructions and a template. The process of scribing lecture notes provides students with valuable experience preparing mathematical documents, and also generates a useful set of lecture notes for the class.

Notes are used with the permission of the student scribes.

LEC #	TOPICS	LECTURE NOTES
1	Fibonacci heaps	(PDF)
2	Network flows	(PDF)
3	Maximum flow; minimum cost circulation	(PDF)
4	Goldberg-Tarjan min-cost circulation algorithm	(PDF)
5	Cancel-and-tighten algorithm; binary search trees	(PDF)
6	Splay trees	(PDF)
7	Dynamic trees (part 1)	(PDF)
8	Dynamic trees (part 2)	(PDF)
9	Linear programming (LP)	(PDF)
10	LP: duality, geometry, simplex	(PDF)
11	LP: complexity; introduction to the ellipsoid algorithm	(PDF)
12	LP: ellipsoid algorithm	(PDF)
13	LP: applications of the ellipsoid algorithm	Notes not available
14	Conic programming I	(PDF)
15	Conic programming II	(PDF)
16	Approximation algorithms	(PDF)
17	Approximation algorithms (facility location)	(PDF)
18	Approximation algorithms (max-cut)	(PDF)
19	Max-cut and sparsest-cut	(PDF)
20	Multi-commodity flows and metric embeddings	Notes not available
21	Convex hulls	Notes not available
22	Convex hulls and fixed dimension LP	(PDF)
23	Voronoi 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