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

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]

MinCut, and Las Vegas & Monte carlo
 Class notes
 References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].

Coupon collector’s problem, Markov Inequality, Chebyshev’s inequality
 Class notes
 References: Section 3.6 of [1] and Chapter 3 of [2].

Minimum Spanning Trees, Boruvka’s algorithm
 References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner

KargerKleinTarjan Randomized Minimum Spanning Tree
 References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner, Original paper of KargerKleinTarjan.

KargerKleinTarjan Randomized Minimum Spanning Tree (contd.)
 References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner, Original paper of KargerKleinTarjan.

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

Matroids (contd.)
 References: Extra material from Jeff Erickson’s book, NPTEL video of Prof. Shashank Mehta.

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

DeMilloLiptonSchwartz–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 MulmuleyVaziraniVazirani ‘87

Concentration bounds
 Class notes
 References: Chapter 4 of [2].

Chernoff bound, Error reduction, Set balancing
 Class notes
 References: Chapter 4 of [2].

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.

Randomized routing (contd.), Maximum Satisfiability
 Class notes
 References: Section 5.2 of [1], and Section 6.2.2 of [2].

MAXCUT, Derandomization with conditional probabilities
 Class notes
 References: Section 6.2 and 6.3 of [2].

Introduction to Quantum Algorithms (guest lecture by Kannan Srinathan)

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

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

Random walks and Markov chains
 Class notes
 References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

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

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

GoemansWilliamson algorithm for MAXCUT
 References: Original paper of Goemans and Williamson.
References
 R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
 M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
 N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.
Similar courses
 Previous offering of the course  Spring 2022
 See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).