CSL866: Randomized Algorithms

II semester: 2007-08

Sandeep Sen and Amitabha Bagchi

Class Timings: Tu, W, F: 10AM to 10:55.
Room: 204 Bharti Building.

In class exam on Tuesday, 4th March 2008.


The objective of this class is to train students in the use of randomization in the design of efficient algorithms for a range of problems and also to teach them how to use to probability-based techniques to analyze the complexity of certain classes of algorithms.


Moments and deviations; Chernoff bounds; Occupancy problems; The probabilistic method; Markov chains and random walks; Martingales; Randomized Rounding; Hashing; Randomized data structures and geometric algorithms; Approximation algorithms and approximate counting; Randomized graph algorithms; Online algorithms.

Exams and homework assignments

Texts and notes

Students are not required to buy any text book.


Sandeep Sen
Amitabha Bagchi