Topics in Algorithms
The goal of the course is to introduce some advanced techniques in design and analysis of algorithms. A basic course in algorithms introduces students to fundamental problems like spanning trees, shortest paths, network flows and cuts. In this course, we will see faster algorithms and more variants of these problems (e.g. minimum cost flows, multicommodity flows,
Steiner trees, minimum cost arborescnences etc.)
and some approximation and randomized algorithms for some of them. This will also give an introduction to techniques like amortized analysis, use of linear and semidefinite programs, metric embeddings etc.
Prerequisites
A basic course in algorithms, discrete maths, and mathematical maturity.
Evaluation
There will be a midsem and endsem, apart from assignments. We will decide on presentations depending on the final strength of the class.
References
There is no single book. I will use various lecture notes and books, and post them here for each lecture. Some topics will be covered from the following books/notes:
- [VV] Approximation Algorithms by Vijay V. Vazirani
- [WS] The Design of Approximation Algorithms by David P. Williamson, David B. Shmoys
- [MG] Understanding and Using Linear Programming by
Jiří Matoušek and
Bernd Gärtner (Springer)
- [AG] Notes by Anupam Gupta from CMU
Problem set
Lectures
Material covered so far in each lecture:
- Jan 6: Introduction, recap of Prim's and Kruskal's minimum spanning tree algorithms (Ref: Any algorithms book that you used in your basic algorithms course e.g. [CLRS])
- Jan 10: Fibonacci heaps (these notes or Algorithms book by Dexter Kozen)
- Jan 15: Borůvka's algorithm, Fredman-Tarjan's O(mlog*n) algorithm (Chapter 1 of [AG], also see this)
- Jan 17: Randomized linear-time algorithm for MST (Karger-Klein-Tarjan algorithm) (Chapter 1 of [AG])
- Jan 22: Steiner trees: NP-hardness (ref), 2-approximation (Section 3.1 of [VV])
Jan 24: No class due to Tesselate
- Jan 29: Minimum-cost arborescence: Edmond's algorithm (Chapter 2 of [AG]), a (very brief) introduction to matroids and greedy algorithms (Ref)
- Jan 31: Introduction to LP duality, weak duality, strong duality (without proof), primal-dual algorithm for minimum spanning trees (See this and this for the primal-dual MST algorithm, [MG] for linear programs, duality, complementary slackness)
- Feb 5: Tree packing and Tutte-Nash-Williams theorem (only statement), LP for the fractional version and its dual (mincut LP) (reference)
Feb 7: No class