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:

Problem set and presentation topics

Lectures

Material covered so far in each lecture:
  1. 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])
  2. Jan 10: Fibonacci heaps (these notes or Algorithms book by Dexter Kozen)
  3. Jan 15: Borůvka's algorithm, Fredman-Tarjan's O(mlog*n) algorithm (Chapter 1 of [AG], also see this)
  4. Jan 17: Randomized linear-time algorithm for MST (Karger-Klein-Tarjan algorithm) (Chapter 1 of [AG])
  5. Jan 22: Steiner trees: NP-hardness (ref), 2-approximation (Section 3.1 of [VV])
    6. Jan 24: No class due to Tesselate
  6. Jan 29: Minimum-cost arborescence: Edmond's algorithm (Chapter 2 of [AG]), a (very brief) introduction to matroids and greedy algorithms (Ref)
  7. 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)
  8. Feb 5: Tree packing and Tutte-Nash-Williams theorem (only statement), LP for the fractional version and its dual (mincut LP) (reference)
    9. Feb 7: No class
  9. Feb 12: Proof of fractional version of Tutte-Nash-Williams theorem (Ref same as above), a very brief overview of ellipsoid algorithm, proof of complementary slackness
  10. Feb 14: Separation oracle for the dual LP, solving tree packing LP in polytime (Ref as above and this)
  11. Feb 19: Computing mincut using tree packings (Reference, also see these notes for ellipsoid method, apart from [MG])
  12. Feb 21: Student presentation 1 [Qusai]: Linear-time MST verification algorithm (Section 1.5 of these notes, also check these slides)
  13. Feb 26: Student presentation 2 [Shubh]: Continuation of the above
  14. Feb 28: Multiway cut: 2-approximation by isolating cuts, LP formulation and separation oracle, brief introduction to APX-hardness, integrality gap (Reference: roughly sections 15.1, 15.2 of these notes)

    15. Midsem week
  15. Mar 12: Multiway cut: CKR rounding (Reference)
  16. Mar 14: Multiway cut CKR rounding continued
  17. Mar 19: Maximum multicommodity flow: using ellipsoid method, Garg-K\"{o}nemann algorithm (Reference)
  18. Mar 21: Maximum multicommodity flow continued
  19. Mar 26: Steiner mincut via isolating cuts (randomized algorithm) (Reference)
  20. Mar 28: Steiner mincut continued
  21. Apr 2: Topic on popular demand: APX-hardness and PTAS reductions (Ref)
  22. Apr 4: Approximating distances in graphs: multiplicative spanners (Ref)
  23. Apr 5: Student presentation: Cactus representation of mincuts
  24. Apr 9: Student presentation: Proof of Tutte-Nash-Williams theorem
  25. Apr 11: Additive spanners (References: these and these notes)
  26. Apr 12: Student presentation: Separator Theorem for minor free graphs
  27. Apr 12: Student presentation: Two-commodity flows
  28. Apr 14: Student presentation: Two-commodity flows continued
  29. Apr 16: Low-stretch spanning trees (Chapter 4 of these notes)
  30. Apr 18: Student presentation: Polynomial-time algorithm for minimum k-cut for fixed k
  31. Apr 18: Student presentation: same as above
  32. Apr 19: Low-stretch spanning trees continued (See these notes)
  33. Apr 19: Student presentation: Gomory-Hu trees
  34. Apr 21: Student presentation: Oblivious routing
  35. Apr 21: Student presentation: Multi-commodity max-flow min-cut theorem statement, tightness, and application to balanced cuts