Part 2 of Princeton’s Algorithms course on the Coursera platform officially ended last week but I haven’t had time to write about it until today. I gushed about the first part of the course in a post last year and this is just the follow-up. It was originally meant to be offered at the end of 2012 (and the lecture videos have dates indicating that they were indeed filmed last year) but due to apparent problems with finalizing the exercises and assignments, the course was only opened at the end of March of this year. My thoughts:
- I thought that Algorithms 1 was the best educational experience I’ve ever had and part 2 only goes on to confirm it. It is amazing in all respects. Based on discussions on the online forums with other students, it is my understanding that no other course available on the Coursera platform currently can match its wealth of teaching materials. It has lecture videos, PDF copies of the slides used in the lectures, extensive exercises, very interesting programming assignments, the code on the booksite provides a vast amount of examples to look at and its fiendish difficult interview questions will challenge you for weeks after the end of the course.
- As to be expected part 2 is markedly more difficult than part 1. I’m pretty sure that the graph structures we learn in the first weeks of the course are more complex than anything else seen in part 1. I note that the official forums were pretty much devoid of dumb posts asking for help with elementary topics quite early on. There were some posts talking about the difficulty of the material early on and then everything was down to business. I surmise that the initial difficulty curve scared off plenty of people.
- Part 2 only has four programming assignments whereas part 1 had five but they are all much trickier. Many students had high praises for the week 2 assignment which involved implementing the seam carving algorithm invented in 2007 and now used in many graphics editing software. It’s not just a toy program either since our own implementations can be used as elementary clients to perform seam carving on our own photos. I also liked the WordNet project which uses graphs to capture the relationships between words in the English language and is apparently used as part of the core of many programs that need to understand English, including IBM’s Watson computer. The other two projects were implementing the Burrows-Wheeler data compression algorithm and using graphs in an unconventional way to figure out whether or not teams have been effectively eliminated in baseball (or any other sports) leagues.
- The latter stages of the course become increasingly theoretical. For example the professors provide an implementation of a linear programming solver but admit that it is only a toy solver and stress that serious users should look towards industrial-strength versions. This contrasts with previous work in the course in which the textbook implementations we study are suited for general use. The course ends with a discussion on reductions and a look at the classic P vs. NP problem in computer science.
- The exercises used share the same format as part 1 of the course. The main purpose seems to determine if a student can manually trace how an algorithm works on pencil and paper. But the final exam in part 2 is a surprise in that it has a strong focus on the theoretical. Several students posted in the forums to note that the final exam feels like it wouldn’t be out of place in Tim Roughgarden’s Design and Analysis of Algorithms course. This is great of course since theoretical questions like this really test whether or not you understand the algorithms in question in a deep and intuitive way but tests like this are much harder for me.
- While I could complete all of the assignments and exercises with a 100% score and I scored over 90% in the final exam, I feel that the difficulty of this course comes close to hitting my limits of what I can do. For example, for some algorithms, such as the fiendish Kosaraju-Sharir, while I can certainly follow the implementation and trace its results, I find that I can’t quite wrap my head around why it works and hence a deep, intuitive understanding of it. Similarly, for the data compression assignment, I can implement it and get it to work perfectly and why it works the way it does feels like magic to me.
So yeah, I greatly enjoyed the time and effort I spent on this course. My next Coursera course won’t be starting until mid-June or so which means I have some free time on hand until then.