CS1.406 Advanced Algorithms (Spring 2024)


Announcements

  • Teaching assistants: Nithish Raja, Vidit Jain
  • Schedule: Tuesday and Friday, 14:00 – 15:30
  • Classroom: H104

Topics

  1. Introduction to Polynomial Identity Testing, Univariate Interpolation, Verifying Matrix Multiplication

    • Class notes
    • References: Section 7.2 & 7.3 of [1], and Section 1.1 & 1.3 of [2].
  2. DeMillo-Lipton-Schwartz–Zippel lemma, The isolation lemma and Mulmuley, Vazirani, and Vazirani algorithm for matching

  3. Randomized routing

  4. MaxSAT, MaxCUT, Derandomization with conditional probabilities

  5. Min-Cut, and Las Vegas & Monte carlo

    • Class notes
    • References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].
  6. Approximate Counting & Approximate Sampling

    • Class notes
    • References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].
  7. Random walks and Markov chains

    • Class notes
    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].
  8. Markov Chains – 2SAT

    • Class notes
    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].
  9. Markov Chains – 3SAT

    • Class notes
    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].
  10. Concentration bounds

  11. Chernoff bound, Error reduction, Set balancing

References

  1. R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
  2. M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
  3. N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.

Similar courses

  1. Previous offering of the course - Spring 2022
  2. See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).