A few years ago a man won the Spanish national lottery with a ticket that ended in the number 48. Proud of his ‘accomplishment’, he revealed the theory that brought him the riches. ‘I dreamed of the number 7 for seven straight nights,’ he said, ‘and 7 times 7 is 48.’  The Drunkard's Walk (Leonard Mlodinow)
There is uncertainty in all bends of life. Some try to avoid it, some try to outsmart it, and some, very brave, try to befriend randomness. One aspect we will learn in this course is how to take advantage of uncertainty in solving computational problems relevant to Computer Science. The other aspect focuses on our shortcoming in computational resources, tools and inability to easily handle huge data. While trying to find solution to a problem, we desire to find exactly what is wanted... yet in reality, we may be allowed to slightly deviate from the given conditions for practical reasons. This course studies algorithms which, by design, may not be correct 100% of the time, or run within the stipulated resource always, but definitely do so in an overwhelmingly large number of cases.
Credits: 4
Prerequisites : Undergraduate algorithms, Discrete mathematics, Familiarity with probability
Post Condition (on student capability after successfully completing the course) :
 Be able to analyse events of probability (in computational problems)
 Be able to analyse an algorithm using probability
 Be able to design a randomised algorithm with provable bounds
 Understand different random processes occurring in problems
 Understand sources and usages of randomness for solving problems
Specifically

The
student is able to understand the advantages and disadvantages of
using probabilistic techniques to design and analyze algorithms.
 The
student is able to design randomized data structures like hash
tables, and algorithms of different types like Monte Carlo, Las
Vegas, onesided error, twosided error,zeroerror.
 The
student is able to use concentration bounds such as Markov,
Chebysev, Chernoff, etc. to prove bounds on probabilities and
expectation associated with randomized algorithms.
 The
student is able to apply the probabilistic method for establishing
the existence of properties in combinatorial structures.
 The
student is able to analyse randomized processes like random walk and
Markov chains.

Instructor : Debajyoti Bera (dbera _at_ iiitd.ac.in)
Office : B204, Academic Building, IIITDelhi
Office Hours : 1 hour after class
Discussions & Announcements: http://piazza.com/iiitd.ac.in/winter2016/cse523 
The course will be split into three main logical sections  learning tools from probability theory, designing algorithms which are probabilistic and using probability for analysis.
