Advanced Algorithms

This course is jointly offered by Dr. Nithin Varma and myself. I plan to cover techniques in randomized algorithms initially, and then Nithin will cover sublinear algorithms.

Assumed background

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

References

There is no single textbook for the course. We will post references for each topic when they are covered. Some topics will be covered from the following book:

[MU] Proability and Computing Randomized Algorithms and Probabilistic Analysis - Michael Mitzenmacher and Eli Upfal
Top

Evaluation

There will be a mid-semester exam, and an end-semester exam. Apart from this, we will have a reading project and an oral exam. Top

Problem sets

Problem set 1

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. [P] Sept 22: Introduction, basic probability recap, verifying univariate polynomial identities, a randomized algorithm for max-cut (Ref: Sections 1.1, 1.2, 6.2 of [MU])
  2. [P] Sept 24: Conditional expectation, derandomization of max-cut by conditional expectation (Section 6.3 of [MU]), introduction to Karger's min-cut algorithm
  3. [P] Sept 29: Karger's min-cut algorithm continued, Faster min-cut by Karger and Stein (Ref)
  4. [P] Oct 1: Coupon Collector's problem, Markov and Chebyshev's inequalities, brief overview of randomized complexity classes, Monte Carlo vs Las Vegas algorithms (Section 2.4, 3.2, 3.3 of [MU])
  5. [P] Oct 6: Polynomial identity testing and its application to bipartite matchings (Ref: 1 and 2)
  6. [P] Oct 8: Finding a bipartite matching in RNC (Ref as in the previous class)
  7. [P] Oct 13: RNC algorithm for finding a perfect matching in bipartite graphs, proof of isolation lemma, introduction to network reliability, #P-completeness, FPRAS (Ref)