Information

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

Specifically

  1. The student is able to understand the advantages and disadvantages of using probabilistic techniques to design and analyze algorithms.
  2. The student is able to design randomized data structures like hash tables, and algorithms of different types like Monte Carlo, Las Vegas, one-sided error, two-sided error,zero-error.
  3. 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.
  4. The student is able to apply the probabilistic method for establishing the existence of properties in combinatorial structures.
  5. 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, IIIT-Delhi
 
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.