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.
Pre-requisites :
  • 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

Lectures

Browse lecture notes,
and other course
materials.

Schedule

Answer to questions like: When?


Resources

What books to follow and where to find more information?

Announcements

See what's new since you
last visited.



Policy

What to do and what not to do?

Contact

Send us an email or give us a call - we're here to help!


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