Prerequisite

It is expected that the student has done a basic course on data structures and algorithms. It is also expected that the student also has elementary knowledge of discrete probability theory (12th class level).

Lectures

There is a lot of animation in these slides in order to enhance the understanding of the lectures. Therefore, these slides should be viewed using only Office 2010.

Lecture 1: Introduction to and motivation for Randomized Algorithms

Lecture 2: Randomized algo for Approximate median and Elementary Probability Introduction to and motivation for Randomized Algorithms

Lecture 3: Two important problems involving Balls into Bin and Randomized Quick Sort; random Variable and expectation

Lecture 4:Linearity of Expectation with applications

Lecture 5:Algebraic Techniques

Lecture 6:An insight into design of any randomized algorithm,Pattern matching algorithm, union theorem

Lecture 7: Application of Union theorem: Maximum load in bin, concentration of randomized quick sort

Lecture 8:Markov's Inequality and Chernoff's Bound

Lecture 9:Random Sampling - part 1 (Estimating some parameter using randomization)

Lecture 10:Random sampling - part II (algorithm for BPWM)

Lecture 11: Hashing - I

Lecture 12: Hashing - II

Lecture 13: Partitioning a random experiment into stages - 1

Lecture 14: Partitioning a random experiment into stages - II

Lecture 15: Randomized Incremental Construction - I

Lecture 16: Randomized Incremental Construction - II

Lecture 17: Miscellaneous application of Backward Analysis

Lecture 18: Approximate Distance Oracles and Min-Cut (part 1))

Lecture 19: Randomized Monte Carlo algorithm for Min-Cut

Lecture 20:Probabilistic Method - (part 1)

Lecture 21: Random walk and electric networks

Lecture 22: Method of bounded difference

Lecture 23:Probabilistic Method - (part 2)