CS6170 Randomized Algorithms

Aug - Nov 2021

Coordinates

  • Where: Online
  • When: J slot - Mon (16.50-17.40), Wed (14-15.15), Thu (15.25-16.40)

TA

Sampriti Roy (cs18d200@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.
  • Markov chains, random walks and applications
  • Sampling and estimation - Monte Carlo methods
  • Balls and bins, balanced allocations and applications
  • VC dimension and PAC learning, online algorithms, 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%
  • Course reading: 20% (in groups of at most 3)
  • Mid-sem: 15%
  • End-sem + viva: 20%

Important dates (tentative)

  • Problem sets: Aug 13, Sep 10, Sep 24, Oct 15, Oct 29 (deadlines will be about 10 days after the dates given)
  • Mid-sem: Sep 23
  • End-sem: Nov 18

Course Materials

Announcements

  • Sep 9: Problem set 2 has been uploaded on Moodle. The deadline is Sep 22, 12 AM.
  • Aug 13: Problem set 1 has been uploaded on Moodle and sent on the course mailing list. The deadline is Aug 24, 12 AM.
  • Aug 11: The topics and references for the course project is now updated here. Please go over the papers briefly, and decide on the topic you want to read for the project. If you have some other topic/paper in mind, email me with the details. Form groups of size two or three, and update your preference on this sheet. Fill the sheet by Aug 25. More details regarding the project will be informed later.
  • Aug 6: Use the template given in these notes to start scribing. Make sure that you carefully go over the README file for scribes before you start. You should use the same login which you used to register on the course mailing list to access this file.
  • Aug 6: Sign up for scribing. You should use the same login which you used to register on the course mailing list to access this file.
  • Aug 5: If you are not yet in the course mailing list, please email me asap. Once your LDAP credentials are set-up, please register on the course moodle.
  • Aug 2: First lecture of the course.