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. There will be weekly homeworks, a final project, and a final exam.
There will be a few talks by guest lecturers. Planned lecturers include Prof. Richard Karp (Turing Award winner and one of the poineers of randomized algorithms and probabilistic analysis) and Prof. Aravind Srinivasan (Professor at Maryland, and an active researcher in this area).
Schedule:
First class: Aug. 12, Friday, 10.30am at SPMS TR1
Tue: 1.30pm-3.30pm, SPMS TR1
Fri: 10.30am-12.30pm, SPMS TR1
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) (On reserve at the Lee Wee Nam Library.)
2. Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi (Secondary Text). (Entire book accessible online via NTU library.)
3. Randomized Algorithms by Motwani and Raghavan. (Most of the book available online from Google Books.)
4. The Probabilistic Method by Alon and Spencer (Entire book accessible online via NTU library.)
5. Introduction to Probability by Grinstead and Snell (available free)
Lecture Notes:
Introduction to Probability and Randomization I
Introduction to Probability and Randomization II
Deviation Bounds: Markov, Chebyshev
Chernoff Bounds and their Applications
Randomized Algorithms for Distributed Agreement: Guest Lecture by Peter Robinson