CS1.406 Advanced Algorithms (Spring 2022)

---

Announcements

• Teaching assistants: Dixit Kumar Garg and S Shodasakshari Vidya
• Schedule: Monday and Thursday, 11:30 – 12:55
• Classroom: SH-2 (2nd floor, C-1 Vindhya)

Problem sets

• Problem set 1 (Due: 12.01.2022)
• Problem set 2 (Due: 05.02.2022)
• Problem set 3 (Due: 07.03.2022)
• Review Problem set

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. Balls and Bins, Tail inequalities (contd.)

   • Class notes
   • References: Chapter 3 of [1].

5. Concentration bounds, Chernoff bound, Error reduction, Set balancing

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

6. Martingales, Azuma’s inequality, Bounded difference inequalities.

   • Class notes
   • References: [Kamath, Motwani, Palem and Spirakis ‘94], Section 4.3 of [1], and Chapter 12 of [2].

7. Martingales (contd.), Balls and Bins, Chromatic number of a random graph

   • Class notes
   • References: Section 4.3 of [1], [Shamir and Spencer ‘87], Upfal’s slides, Sinclair’s lecture notes, and Chapter 12 of [2].

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

9. Randomized routing (contd.), Maximum Satisfiability

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

10. MAXCUT, Derandomization with conditional probabilities

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

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

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

13. MVV (contd.), Maximal Independent Set

    • Class notes
    • References: Section 12.3 of [1].

14. Maximal Independent Set (contd.)

    • Class notes
    • References: Section 12.3 of [1].

15. Hashing: Universal Hashing, Perfect Hashing

    • Class notes
    • References: Section 8.4 of [1], and Section 13.3 of [2].

16. Hashing: Universal Hashing, Perfect Hashing (contd.)

    • Class notes
    • References: Section 8.4 of [1], and Section 13.3 of [2].

17. Approximate counting: DNFs

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

18. Random walks and Markov chains

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

19. Markov Chains – 2SAT

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

20. Markov Chains – 3SAT

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

21. Karatsuba’s integer multiplication, Discrete Fourier Transform, Fast Fourier Transform.

    • Class notes
    • References: Sections 1.1 – 1.3 and 2.2 of [6].

22. DFT in Mod-m rings, Chinese Remaindering Theorem, Schonhage-Strassen integer multiplication.

    • Class notes
    • References: Sections 2.3 and 2.7 of [6].

23. Fermat’s little theorem, Fermat’s test, Miller-Rabin primality test, RSA encryption and Fingerprinting.

    • Class notes
    • References: Section 14.6, and sections 7.4 – 7.6 of [1].

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.
4. V. Shoup (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press.
5. J. von zur Gathen and J. Gerhard (2003), Modern Computer Algebra, Cambridge University Press.
6. R. Brent and P. Zimmerman (2010), Modern Computer Arithmetic, Web draft.

Similar courses

See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).