CS6170 Randomized Algorithms

July - Nov 2022

Coordinates

  • Where: CS24 CS34
  • When: G slot - Mon (12-12.50), Wed (17-17.50), Thu (10-10.50), Fri (9-9.50)

TAs

Sampriti (cs18d200@smail) and Keshav (cs21s040@smail)

Objectives

Randomization and probabilistic methods are ubiquitous in Computer Science. Randomization often provides simple, elegant algorithms that perform well in practice. Furthermore, there are problems for which we do not know any efficient algorithm that does not use randomness. This course will introduce methods to design and analyze randomized algorithms in a variety of settings.

Contents

We will study the application of randomization and probabilistic methods in a variety of settings. The following is a brief outline of the contents of the course. The emphasis on the various topics, and their order will be determined later. - Basic probabilistic techniques - random variables, expectation, variance, tail bounds with applications. - Balls and bins, balanced allocations and applications - Online algorithms - Markov chains, random walks and applications - Sampling and estimation - Monte Carlo methods - VC dimension and PAC learning, algebraic techniques (if time permits)

References

  • [MU]: Probability and Computing - Mitzenmacher and Upfal.
  • [MR]: Randomized Algorithms - Motwani and Raghavan.
  • [DP]: Concentration of Measure for the analysis of Randomized Algorithms - Dubhashi and Panconesi.

There are lots of lecture notes and resources available online that we will refer to occasionally.

Grading policy (tentative)

  • Problem sets: 40% (best 4/5)
  • Scribing: 5%
  • Mid-sem: 25%
  • End-sem: 30%

Important dates (tentative)

  • Problem sets: Aug 12, Sep 2, Sep 16, Oct 7, Oct 21 (the deadline will be around 10 days after the problem sets are released)
  • Mid-sem: Sep 14
  • End-sem: Nov 10

Course Materials