Randomized Algorithms and Probabilistic Techniques in Computer Science
About the course:
The influence of probability theory in algorithm design and analysis has been profound in the last two decades or so. This course will focus on probabilistic techniques that arise in algorithms, in particular, randomized algorithms and probabilistic analysis of algorithms. Randomized algorithms are typically faster, simpler, and easier to implement compared to purely deterministic algorithms. The course will introduce various probabilistic tools and techniques that help us in the design of randomized algorithms and their analysis.
Algorithmic examples from various areas ranging from fundamental algorithms and data structures (such as sorting, fingerprinting, hashing), to network/graph algorithms, communication networks, distributed/parallel computing, approximation algorithms etc., will be used to illustrate and understand the techniques.
The background required is only basic discrete math and (mostly) discrete probability, at the level of standard undergraduate courses.
See also the related course: Probabilistic Methods in Algorithm Design and Analysis
Textbooks:
We will cover material mainly from the following texts in addition to other sources.
1. Probability and Computing by Mitzenmacher and Upfal. (Main Text)
2. Randomized Algorithms by Motwani and Raghavan. (Most of the book available online from Google Books.)
3. The Probabilistic Method by Alon and Spencer (Entire book accessible online via NTU library.)
4. Introduction to Probability by Grinstead and Snell (available free)
Lecture Notes:
Introduction to Probability and Randomization I
Introduction to Probability and Randomization II