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: SH2 (2nd floor, C1 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

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

Balls and Bins, Tail inequalities (contd.)
 Class notes
 References: Chapter 3 of [1].

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

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

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

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

MVV (contd.), Maximal Independent Set
 Class notes
 References: Section 12.3 of [1].

Maximal Independent Set (contd.)
 Class notes
 References: Section 12.3 of [1].

Hashing: Universal Hashing, Perfect Hashing
 Class notes
 References: Section 8.4 of [1], and Section 13.3 of [2].

Hashing: Universal Hashing, Perfect Hashing (contd.)
 Class notes
 References: Section 8.4 of [1], and Section 13.3 of [2].

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

Karatsuba’s integer multiplication, Discrete Fourier Transform, Fast Fourier Transform.
 Class notes
 References: Sections 1.1 – 1.3 and 2.2 of [6].

DFT in Modm rings, Chinese Remaindering Theorem, SchonhageStrassen integer multiplication.
 Class notes
 References: Sections 2.3 and 2.7 of [6].

Fermat’s little theorem, Fermat’s test, MillerRabin primality test, RSA encryption and Fingerprinting.
 Class notes
 References: Section 14.6, and sections 7.4 – 7.6 of [1].
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.
 V. Shoup (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press.
 J. von zur Gathen and J. Gerhard (2003), Modern Computer Algebra, Cambridge University Press.
 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).