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.

Credits: 4
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
 Instructor : Debajyoti Bera (dbera _at_ iiitd.ac.in)
 Office : B204, Academic Building, IIIT-Delhi
 
Office Hours : 1 hour after class, on Tuesday and Friday
 
Course Mailing List : search for cse523 in Google Groups


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.