Udacity’s Algorithms: Crunching Social Networks is a neat course, but does focus heavily on graphs, as the title suggests. I was therefore looking for a more thorough treatment of algorithms, and Tim Roughgarden’s Coursera course Algorithms: Design and Analysis, Part 1 provided exactly that. I originally intended to write a review after finishing part 2, but there was so much content in the first part already that I dropped that idea.
Algorithms: Design and Analysis consisted of, as Prof. Roughgarden put it, “a selection of greatest hits of computer science.” It’s material any programmer or computer scientist should be familiar with. It is relevant whenever you work with algorithms and data structures, and also satisfying to study.
Here is the entire curriculum:
I. INTRODUCTION (Week 1)
II. ASYMPTOTIC ANALYSIS (Week 1)
III. DIVIDE & CONQUER ALGORITHMS (Week 1)
IV. THE MASTER METHOD (Week 2)
V. QUICKSORT – ALGORITHM (Week 2)
VI. QUICKSORT – ANALYSIS (Week 2)
VII. PROBABILITY REVIEW (Weeks 2-3)
VIII. LINEAR-TIME SELECTION (Week 3)
IX. GRAPHS AND THE CONTRACTION ALGORITHM (Week 3)
X. GRAPH SEARCH AND CONNECTIVITY (Week 4)
XI. DIJKSTRA’S SHORTEST-PATH ALGORITHM (Week 5)
XII. HEAPS (Week 5)
XIII. BALANCED BINARY SEARCH TREES (Week 5)
XIV. HASHING: THE BASICS (Week 6)
XV. UNIVERSAL HASHING (Week 6)
XV. BLOOM FILTERS (Week 6)
I particularly enjoyed the lectures on the master method, since they cleared up a few things for me. Some time ago I was working with matrix multiplication. From linear algebra I knew that this should lead to cubic runtime. However, my impression was that the algorithm ran faster than that, so I did some research and found out about Strassen’s algorithm. This one was covered in the lectures as well. What I viewed as mysterious back then was not only how Strassen came up with it in the first place — those strokes of genius are rarely explained — but also how one could make a statement as precise as that the algorithm was in O(n ^ 2.8074). Well, thanks to the master method I know now.
All the topics listed above you can find in your typical algorithms textbook. What you don’t get when working through a textbook, however, is the fabulous presentation of the material. The lectures are full of proofs and serious discussions, but Prof. Roughgarden knows how to keep your attention with a dry remark, or by quickly traversing language levels. In one second he’s speak of the raison d’être of an algorithm, and in the next he advises you “to bust out the Pythagorean Theorem” for one part of a proof. At that point I did rewind the video because I thought there was no way he could have said that.
The lectures overall were surprisingly entertaining. This was particularly the case whenever Prof. Roughgarden was discussing implications of analyses or the “big picture”. Here is a good example, taken from a brief lecture that discussed the necessity of knowing your data structures and their respective features well:
Level 1 was, according to Prof. Roughgarden, “cocktail party conversation competence, but of course I am only talking of the nerdiest of cocktail parties”. The sense of humor may not be to your liking, but if it is, you’ll be in for a treat. I don’t think I ever enjoyed listening to a lecturer in a technical subject that much.
Let’s talk some more about the presentation. I have gone through courses, both online and on-campus, that presented the material as if it had been received from God in its final form, with hardly any motivation or explanation, and instead just a litany of formulae and definitions. Prof. Roughgarden eventually also ends up with lengthy equations and formal definitions, but he develops the material as he goes along, not unlike Salman Kahn does it in his mathematics videos at Khan Academy. Here is a slide from one of the lectures on Dijkstra’s algorithm to illustrate this:
The many colors give a hint at the stages this drawing went through, but if this is too hectic for you, you can download the lecture slides as PDFs as well. Even typed versions were provided. Occasionally, there were optional PDFs with lengthy formal proofs for those with a greater interest in theory.
If you now said that this sounds as if the presentation was a bit whimsical, then I would agree with you. However, this does not mean that Algorithms: Design and Analysis wasn’t a thorough course. The problem sets and programming assignments required you to have a solid grasp on the material from the lectures. In particular the programming assignments required a good understanding of not only your programming language of choice but also of the algorithms and their supporting data structures. The difference between a good and a poor implementation could easily amount to several orders of magnitude. In one case, you get the answer almost instantly, and in the other your program might run for hours if not an entire day. Just imagine using repeated linear search over an array when the problem called for a hash table instead!
Overall, the programming assignments were a highlight of the course. Here’s a complete list, arranged by weeks:
- Counting inversions
- Karger’s algorithm
- Computing strongly connected components
- Dijkstra’s algorithm
- 2 sum problem & Median maintenance
The first problem piggybacks on mergesort. The others were normally as straight-forward as they sound. However, the files that had to be processed were often quite large, which required some care when implementing the algorithms. Weeks 3 and 4 were the most challenging and also the most interesting problems. How well you’ll fare with the assignments may also depend on the language you chose. The grader only checks the numerical answer. How you get there is entirely your problem. You can chose any language you want, but some may be better suited than others.
The theory questions normally related to the homework in some way. I found it therefore helpful to only tackle them after I had successfully submitted the programming assignments. For some questions it may help to consult the optional text books. Prof. Roughgarden gives references for four textbooks, one of which is available for free online. The books were Cormen et al., Introduction to Algorithms, Dasgupta et al., Algorithms, Kleinberg and Tardos, Algorithm Design, and Sedgewick and Wayne, Algorithms. I found the free resource, Dasgupta, to be sufficient for the course.
In this offering, the problem sets and programming assignment counted 30 % each for the final grade, and the final exam made up the remaining 40 %. The final exam was fair, but not necessarily easy. However, it felt somewhat superfluous since the problem sets covered the material already, and some of the questions in the problem sets were more challenging. But partly this could have been because some topics were new for me back then, and when encountering them again in the final exam I was familiar with them already.
While I tremendously enjoyed the course, there were some problems, too, and most are related to the forums. Algorithms: Design and Analysis is not an introductory course. If you’ve gone through a solid CS101 course, and a survey course in data structures, maybe like Stanford’s free CS106A and CS106B, you should be well-prepared. If you lack this knowledge, then do yourself the favor and work on the basics first. However, quite a few people seemed to not have read the course description, according to which this course is appropriate for junior or senior level CS students. As a consequence, I mostly avoided the forums in the beginning because they were filled to the brim with basic or superfluous questions, and often with poor grammar and vocabulary. I couldn’t help but wonder why it almost always were people using Java who didn’t have a proper grasp of programming, the course content, and the English language. As the course progressed, fewer and fewer of those people were left, which increased the value the forums provided substantially.
Weak forum moderation is by far my biggest gripe with MOOCs. I think a sub-forum for beginners would have been a good idea. Forum moderators could then simply move all distracting threads there. An even better idea would have been some kind of entrance exam that checked basic competency. There certainly were some good discussions in the forum. Yet, the signal to noise ratio was at times as bad as on any “social media” site. In other words: the few good contributions were drowned by a myriad of barely legible or superfluous “me too” posts because people were too lazy to check whether a similar issue had been discussed already.
Speaking of the course material, one negative aspect was that no test cases for the programming assignments were provided. However, the text files we were given were normally so large that a manual check was not feasible. This was where the forum shined as some people posted test cases to work with. This was a good alternative to testing your algorithm on a 70mb text file. I’m sure many would have appreciated if the course staff had provided a number of test cases as this would have ensured a smoother experience.
Further, there was an issue that some people managed to implement algorithms that were able to process the small test cases, but which choked on larger files. When I took an algorithms course at university, we were given two or three input files per assignment. To pass the assignment it was sufficient if your algorithm could process the smallest input size. This was a fair approach since you showed that you could implement the algorithm. On the other hand, in Algorithms: Design and Analysis, your only choice was to correctly process the often very large input file. Therefore, I think that people were unfairly being punished for implementing an inefficient but principally correct algorithm. They are no better off than somebody who didn’t manage to implement the algorithm at all. But shouldn’t the former group at least have had a chance to earn partial credit?
While there were some minor issues with this course, I nonetheless think that Algorithms: Design and Analysis, Part 1 was great. Especially for an autodidact it’s probably a better solution to go through this course than any of the standard textbooks on your own. I highly recommend it, and I’m eagerly waiting for part 2.