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.