How Probability & Randomness is Part of Computation
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.
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.
Credits: 4

Opened to 3rd year, 4th year UG and PG.
Part of Theory stream for BTech.
Part of Theory core for MTech.

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

You must be logged in to add gadgets that are only visible to you