What is this course about?
Randomness is one of the most powerful tools in algorithm design. This course explores how probabilistic techniques can simplify algorithms, break worst-case barriers, and yield elegant solutions to otherwise intractable problems. Students will gain proficiency in probabilistic analysis, tail inequalities, hashing, load balancing. We will learn how to use these tools for the analysis of randomized algorithms for problems in graphs, linear algebra and optimization.
Tentative list of topics:
Introduction to randomized algorithms.
Useful tail inequalities for probabilistic analysis: Markov, Chebyshev, Chernoff, Martingale, and variants.
Hashing and Fingerprinting.
Rest TBD, based on class (and instructor's) interest.
Tentative Grading
Assignments (20%)
Roughly 4 assignments worth 5% each.
The submission deadline will be announced along with the assignment. Late submissions will not be allowed.
You may discuss with your peers, but you MUST write the solutions on your own.
Exams (50%)
Quiz-1 (15%)
Quiz-2 (15%)
End Sem (20%)
Final Project (25%)
You can do a project on a topic of your liking, as long as it is relevant to the spirit of the course.
Project deadlines will be announced as the course progresses.
Class Participation (5%)
Textbooks
We will largely follow these two textbooks:
Probability and Computing by Mitzenmacher and Upfal
Randomized Algorithms by Motwani and Raghavan
Other References
There are many excellent courses online on this topic.