Coursera - Design and Analysis of Algorithms Course by Tim Roughgarden

I learnt Data Structures and Algorithms in my third year of engineering and scored a modest B, so when I took Prof Roughgarden's Algorithms class just to revise the concepts for the upcoming placements in college. I expected it to be a walkover as generally all the courses I took in Coursera were simpler than BITS in classroom learning.


As soon as I saw the first week's lectures an imaginary Yoda came and told me.. "Fool were you, to have expected less from this course!!!". Yup, I got to know that I will have to slog for this course because the first programming assignment almost made me go bonkers.

The lectures were pretty well documented and very elaborate. Professor Tim Roughgarden knew the lay of the land and explained concepts like teaching ABC to children. In fact, sometimes it interested me so much that I would work out the small examples mentioned in the lectures by taking help from the Internet.

Spread across 6 weeks, the lectures were pretty well organized except maybe the hashing part which was unnecessarily broken into 2 weeks where it could have finished in a single week. Also there were Optional videos which dealt with advanced topics not in the syllabus.

Week 1 included Merge Sort basics and Introduction to the most important topic of complexity. All notations - big oh, theta and other notations were explained along with examples. The programming assignment was about counting inversions which was code specific and would work only using the professor's algorithm; any other implementation would yield different answers. But it was really good practice and I generated about 40 different test cases while verifying my solution.

Week 2 introduced a brand new concept to me - The Master Method. This made me heave a huge sigh of relief as complexity analysis and calculation always scared me. The programming assignment had 3 questions with different selection of Pivots for the Quick Sort values. Took some help from Issam Laradji to solve this as the 3rd part 'Pivot of medians' was difficult to understand.

Week 3 was graphs and randomized/ deterministic selections. The introduction to graphs was pretty brief and thankfully computing min-cut for the programming assignment using Karger's min-cut algorithm wasn't that tough.

Week 4 dealt with BFS, DFS and their numerous applications. Though the concepts are pretty easy, the programming assignment on SCC was so hard that even after the 5 th try I felt like I couldn't get the correct answer. Thankfully god showed me some mercy and on the last try I got the correct answer…

Week 5 included multiple topics like Hashing, Heaps ... but the maximum stress was on the Dijkstra's Algorithm. This was my favourite programming assignment though it took me 3 of the 6 tries to get it right.

Week 6 was the last week and based on Universal Hashing, Trees and Bloom Filters. I was greatly looking forward the programming assignment on trees but instead small applications of Heap - the 2-Sum algo and the median maintenance were given to be coded leaving me crestfallen.

Overall I believe that the course was a huge success as even though I had done Algorithms course as a part of my curriculum in BITS before, I can successfully say that I had learnt something new in this one.

Kudos to Professor Tim and all the active Forum folks who helped me clear my doubts!!!