Randomized Algorithms

November 27, 2010

Wow..  I have finally completed my First Semester at IIT Kanpur!  The course work was interesting and challenging and schedule was sometimes daunting, but all in all I have learned much more than I could have imagined.

The Randomized Algorithms course taken by Prof. Surendra Baswana was my favourite course this semester, where I can say I learned the most. I must admit that I was not good at probability theory to start with as I did not have a full course on probability during my graduation. So, I wanted to take this course to get comfortable with that. I can now say I have ended up with whole set of new tools that I can use in the future.

The course is really well structured and the style of teaching is amazing. At the same time, it is quite demanding and if you do not give enough time and attention to course every day, you may end up not understanding the future concepts at all. I did find it a bit difficult to cope up at the start (since I was not used to studying so much…  ) but in the long run I feel this will help me a lot.

  • Basics of probability theory and concepts like sample space, events, conditional probability, random variables, expectation etc were covered right from the scratch.
  • Tools like linearity of expectation, partition theorem, Markov Inequality, Chernoff Bound, Chebyshev Inequality, Method of Bounded Difference were taught thoroughly and we had to apply them on a host of practice and assignment problems.
  • Different randomized algorithms and their applications to different fascinating areas were taught. Techniques like random sampling, backward analysis, partitioning in stages, hashing, randomized pattern matching, probabilistic methods etc were covered.

The assignments and exams were tough and truly tested whether you have “internalized the concepts” (as Prof. Baswana likes to call it) or not. Though I was very weak in these areas (which showed up in the first mid-sems, I managed to do pretty well in end sem exam (though I did my share of silly mistakes as usual!).  All in all I would say I enjoyed the course a lot.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: