CS1.406 Advanced Algorithms (Spring 2023)

---

Announcements

• Teaching assistants: Amul Agarwal, Kunal Jain, Nithish Raja
• Schedule: Tuesday and Friday, 15:35 – 17:00
• Classroom: H103

Lectures

1. Introduction to Randomized algorithms, RandQS

   • Class notes (Includes the list of tentative topics)
   • References: Chapter 1 of [1], Chapter 1 & Section 2.4 of [2]

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

   • Class notes
   • References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].

3. Coupon collector’s problem, Markov Inequality, Chebyshev’s inequality

   • Class notes
   • References: Section 3.6 of [1] and Chapter 3 of [2].

4. Minimum Spanning Trees, Boruvka’s algorithm

   • References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner

5. Karger-Klein-Tarjan Randomized Minimum Spanning Tree

   • References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner, Original paper of Karger-Klein-Tarjan.

6. Karger-Klein-Tarjan Randomized Minimum Spanning Tree (contd.)

   • References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner, Original paper of Karger-Klein-Tarjan.

7. Introduction to Matroids

   • References: Extra material from Jeff Erickson’s book, NPTEL video of Prof. Shashank Mehta.

8. Matroids (contd.)

   • References: Extra material from Jeff Erickson’s book, NPTEL video of Prof. Shashank Mehta.

9. 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].

10. DeMillo-Lipton-Schwartz–Zippel lemma, The isolation lemma and Mulmuley, Vazirani, and Vazirani algorithm for matching

    • Class notes
    • References: Section 12.4 of [1], Section Moshkovitz’s alternate proof of DLSZ lemma, and Mulmuley-Vazirani-Vazirani ‘87

11. Concentration bounds

    • Class notes
    • References: Chapter 4 of [2].

12. Chernoff bound, Error reduction, Set balancing

    • Class notes
    • References: Chapter 4 of [2].

13. Randomized routing

    • Class notes
    • References: Section 4.2 of [1], Section 4.5.1 of [2], Lovett’s course notes from UCSD, and J R Lee’s course notes from UWash.

14. Randomized routing (contd.), Maximum Satisfiability

    • Class notes
    • References: Section 5.2 of [1], and Section 6.2.2 of [2].

15. MAXCUT, Derandomization with conditional probabilities

    • Class notes
    • References: Section 6.2 and 6.3 of [2].

16. Introduction to Quantum Algorithms (guest lecture by Kannan Srinathan)

17. Shor’s integer factoring (guest lecture by Kannan Srinathan)

18. Approximate counting: DNFs

    • Class notes
    • References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].

19. Random walks and Markov chains

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

20. Markov Chains – 2SAT

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

21. Markov Chains – 3SAT

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

22. Goemans-Williamson algorithm for MAXCUT

    • References: Original paper of Goemans and Williamson.

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).