CS5330: Randomized Algorithms, Spring 2020.

Instructors: Arnab Bhattacharyya
Teaching Assistant: Bao Ergute.

This public-facing webpage does not contain the lecture notes and problems sets that were distributed in the class.

Course Description
Randomization is ubiquitous in computer science now. In this module, we cover topics in the following broad areas:

Basic probability
Concentration of measure
Hashing
Randomized data structures
Randomized approximation algorithms
Random walks on graphs
Approximate counting and sampling
Online algorithms

Teaching Modes

Lecture from 6:30 pm to 8:30 pm at I3-0344. There will be 2-3 breaks, so the actual lecture time will be about 90 minutes.
Tutorial from 8:30 pm to 9:30 pm at I3-0344. We will discuss the take-home problems assigned from two weeks ago, as well as other burning questions.
Consultation hour with TA (Bao Ergute) at Database Lab 1 on Fridays, 6:30 pm to 8:30 pm.
Consultation by appointment with Prof. Arnab. I am also available after lecture and tutorial.

References

Probability and Computing. Mitzenmacher and Upfal. 2nd Edition, 2017. Highly recommended that you get it.
Additional reference: Randomized Algorithms. Motwani and Raghavan. 1995. A good reference but not really necessary.
Many lecture notes scattered around the web.