Advanced Algorithms

I plan to cover some advanced techniques in algorithm design. The course will be divided into four modules - approximation algorithms, randomized algorithms, streaming and online algorithms.

Assumed background

Students taking this course should have done one course on programming, and one on design and analysis of algorithms. I also expect familiarity with basic concepts in probability. Top

References

There is no single textbook for the course. I will post references for each topic. Most of the references will be available online. Top

Evaluation

There will be two assignments, a mid-semester exam, an end-semester exam, and an oral exam. The weightage is 10% for each assignment, 30% for midsem, 40% for endsem, and 10% for the oral exam. Top

Practice Problems

Here are some practice problems based on the topics we covered so far. You are encouraged to first try them on your own. If you can not solve, take a hint from other students or from me. You can also look for online sources. If you find one, mail it to me. Top

Assignments

You are not supposed to discuss the assignments with anyone or refer to any source on the internet. Students found copying assignments from each other will get a fail grade. If you are stuck while solving the assignment, you are welcome to discuss with me. I will be glad to give hints so that you can proceed. Assignments submitted after the due date will not be accepted. Top

Lectures

  1. Jan 3: Introduction, 2-approximation for vertex cover, 2-approximation for metric TSP using minimum spanning trees (Ref: Sections 1.1 and 3.2 of VV)
  2. Jan 6: Christofides' 1.5-approximation algorithm for TSP, Scheduling on identical parallel machines (Ref: Sections 2.4, 2.3 of WS)
  3. Jan 10: Scheduling on identical parallel machines continued: 2-approximation, LPT rule and 3/2-approximation, 4/3-approximation using LPT rule (Ref: Section 2.3 of WS, and this for 3/2 approximation)
  4. Jan 13: Introduction to randomized algorithms, Karger's min-cut algorithm (Ref: this)
  5. Jan 17: Karger's min-cut algorithm continued, Improving the running time of Karger's min-cut (Ref: this), Introduction to online algorithms: Ski rental
  6. Jan 20: Randomized algorithms for weighted MAX-SAT: 1/2 approximation and 0.618 approximation (Ref: Sections 5.1, 5.2, 5.3 of WS)
  7. Jan 24: Set cover greedy algorithm, Knapsack problem dynamic programming algorithm (Ref: Section 2.1 of VV and Section 3.1 of WS)
  8. Jan 27: Knapsack problem FPTAS, Introduction to bin packing, hardness and inapproximability, 2-approximation by first-fit (Ref: Sections 3.1 and 3.3 of WS)
  9. Feb 6: Bin packing: Better than 4/3 inapproximability result for online algorithms, 4/3-approximation for first-fit decreasing (Ref: this)
  10. Feb 7: APTAS for Bin-packing (Ref: Section 3.3 of WS)
  11. Feb 10: APTAS for bin-packing continued, Introduction to LP, Weighted vertex-cover by LP-rounding (Ref: this)
  12. Feb 13: Uncapacitated facility location: 6-approximation (Ref: this)
  13. Feb 14: Uncapacitated facility location continued
  14. Feb 17: LP duality, primal-dual algorithm for weighted vertex cover (Ref: this, Section 11.4 of Kleinberg-Tardos)
  15. Feb 28: Feedback vertex set primal-dual algorithm (Ref: Section 7.2 of WS)
  16. Mar 3: Feedback vertex set primal-dual algorithm continued, Introduction to Hopcroft-Karp algorithm
  17. Mar 7: Hopcroft-Karp algorithm (Ref: this)
  18. Mar 10: Hopcroft-Karp algorithm continued, Weighted bipartite matching (Ref: this)
  19. Mar 14: Weighted bipartite matching - Primal-dual algorithm, Bipartite matching polytope (Ref: this)
  20. Mar 17: Non-bipartite matching: Edmond's blossom shrinking algorithm (Ref: this)
  21. Mar 21: (Lecture by Partha) Randomized parallel algorithm for bipartite matching
  22. Mar 24: Edmond's algorithm continued, Introduction to streaming algorithms: Majority (Ref: Chapter 1 of this)
  23. Mar 28: Streaming algorithms: Misra-Gries algorithm (Ref: Same as previous lecture), a lower bound on Most-frequent element problem (Ref: this)
  24. Mar 31: Estimating the number of distinct elements (Ref: this)
  25. Apr 4: Streaming algorithms for graph problems: Connectedness, bipartiteness, distance estimate (Ref: Lecture 13 of this)
  26. Apr 7: Matchings in streaming model (Ref: Section 15.2 of this)
  27. Apr 11: Lovász Local Lemma: Constructive proof and applications to hypergraph coloring and k-CNF SAT (Ref: this)
  28. Apr 18: Approximate counting: FPRAS for DNF counting (Ref: this)