Advanced Algorithms
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 |
Assignments
Problems Sets from 2008
The problem sets are due in the sessions listed in the table.
|
LEC # |
ASSIGNMENTS |
|
5 |
Problem set 1 (PDF) |
|
8 |
Problem set 2 (PDF) |
|
11 |
Problem set 3 (PDF) |
|
16 |
Problem set 4 (PDF) |
|
21 |
Problem set 5 (PDF) |
|
26 |
Problem set 6 (PDF) |
Problems Sets with Solution from 2001
|
LEC # |
ASSIGNMENTS |
SOLUTIONS |
|
3 |
Problem set 1 (PDF) |
|
|
8 |
Problem set 2 (PDF) |
|
|
11 |
Problem set 3 (PDF) |
|
|
16 |
Problem set 4 (PDF) |
(PDF) |
|
22 |
Problem set 5 (PDF) |
|
|
23 |
Problem set 6 (PDF) |
(PDF) |
Study Materials
Lecture notes from previous years are included below. While they do not follow the current schedule, these are still good resources for the course.
|
LEC # |
TOPICS |
LECTURE NOTES |
|
1 |
Introduction |
No notes for Lecture 1 |
|
2 |
Linear programming (LP): basic notions, simplex method |
(PDF) (Courtesy of Alice Oh. Used with permission.) |
|
3 |
LP: Farkas Lemma, duality |
(PDF) (Courtesy of Abhinav Kumar and Nodari Sitchinava. Used with permission.) |
|
4 |
LP: complexity issues, ellipsoid method |
(PDF) (Courtesy of Reina Riemann. Used with permission.) |
|
5 |
LP: ellipsoid method |
(PDF) (Courtesy of Dennis Quan. Used with permission.) |
|
6 |
LP: optimization vs. separation, interior-point algorithm |
(PDF) (Courtesy of Bin Song and Hanson Zhou. Used with permission.) |
|
7 |
LP: optimality conditions, interior-point algorithm (analysis) |
(PDF) (Courtesy of Nick Hanssens and Nicholas Matsakis. Used with permission.) |
|
8 |
LP: interior-point algorithm wrap up Network flows (NF) |
(PDF) (Courtesy of Jelena Spasojevic. Used with permission.) |
|
9 |
NF: Min-cost circulation problem (MCCP) |
(PDF) (Courtesy of Jasper Lin. Used with permission.) |
|
10 |
NF: cycle cancelling algs for MCCP |
(PDF) (Courtesy of Ashish Koul. Used with permission.) |
|
11 |
NF: Goldberg-Tarjan alg for MCCP and analysis |
(PDF) (Courtesy of Mohammad Hajiaghayi and Vahab Mirrokni. Used with permission.) |
|
12 |
NF: cancel-and-tighten Data structures (DS): Binary search trees |
(PDF) (Courtesy of David Woodruff and Xiaowen Xin. Used with permission.) |
|
13 |
DS: Splay trees, amortized analysis, dynamic tree |
(PDF) (Courtesy of Naveen Sunkavally. Used with permission.) |
|
14 |
DS: dynamic tree operations |
(PDF) (Courtesy of Sanmay Das. Used with permission.) |
|
15 |
DS: analysis of dynamic trees NF: use of dynamic trees for cancel-and-tighten |
(PDF) (Courtesy of Timothy Danford. Used with permission.) |
|
16 |
Approximation algorithms (AA): hardness, inapproximability, analysis of approximation algorithms |
(PDF) (Courtesy of Nicole Immorlica and Mana Taghdiri. Used with permission.) |
|
17 |
AA: vertex cover (rounding, primal-dual), generalized Steiner tree |
(PDF) (Courtesy of Matt Peters and Steven Richman. Used with permission.) |
|
18 |
AA: primal-dual alg for generalized Steiner tree |
(PDF) (Courtesy of Johnny Chen and Ahmed Ismail. Used with permission.) |
|
19 |
AA: derandomization |
(PDF) (Courtesy of Shalini Agarwal and Shane Swenson. Used with permission.) |
|
20 |
AA: MAXCUT, SDP-based 0.878-approximation algorithm |
(PDF 1.2 MB) (Courtesy of William Theis and David Liben-Nowell. Used with permission.) |
|
21 |
AA: polynomial approximation schemes, scheduling problem: P||Cmax |
(PDF) |
|
22 |
AA: approximation Scheme for Euclidean TSP |
(PDF - 1.2 MB)* (Courtesy of Salil Vadhan (Thomas D. Cabot Associate Professor of Computer Science). Used with permission.) |
|
23 |
AA: multicommodity flows and cuts and embeddings of metrics |
(PDF - 7.2 MB)** |
* There were no scribe notes for this lecture for the Fall 2001 term. The notes from a previous term cover the same topic and are linked here.
** There were no scribe notes for this lecture for the Fall 2001 term. Section 8 of the notes from a previous term cover the same topic and are linked here.
Linear Programming (PDF - 5.1 MB)
Network Flows (PDF - 3.1 MB)
Approximation Algorithms (PDF - 7.2 MB)
The lecture notes below were provided by students who took the class in an earlier term:
- A Simple Mincut Algorithm (PDF) (Courtesy of Roberto De Prisco (Associate Professor at the University of Salerno, Italy). Used with permission.)
- Euclidean TSP Approximation Scheme (PDF - 1.2 MB) (Courtesy of Salil Vadhan (Thomas D. Cabot Associate Professor of Computer Science). Used with permission.)
- Lattices (PDF - 2.2 MB) (Courtesy of David Wilson. Used with permission.)