CSL857: Randomized Algorithms

II semester: 2012-13

Amitabha Bagchi

Class Timings: Tue Fri 2PM to 330PM.
Room: II 332.


Randomization has been a major tool in the design of algorithms for some time now, and consequently the study of randomized algorithms has developed in many directions. In this course we will not attempt to comprehensively cover all the different directions, focussing instead on beginning by putting our knowledge of probability theory on a more rigorous foundation, then moving on to study Markov Chains with a view to understanding the phenomenon of rapid mixing and its implications for algorithms. Finally we will study the probabilistic method from an algorithmic point of view. The focus of this course will be to build a deep understanding of the topics covered and evaluation will be through homework assignments and exams.

Textbooks and notes

Lecture Schedule

The material to be covered in this course is divided into 12 units of 3 hours each. The source of the material is mentioned along with each unit. Apart from these there are some additional units that will be covered at times apart from regular lecture hours if there is interest. The first 6 units are listed below for now. More will be added later.


You will need to download the tex class file mts-hw.cls and keep it in the directory where you latex the homework file.


Amitabha Bagchi