Algorithms: Design and Analysis, Part 1

So the latest Coursera course I’ve been taking and have now completed is Stanford University’s version of its Algorithms class by professor Tim Roughgarden. Apparently enough people asked about the differences between this course and the one from Princeton University that the question has now been addressed in the FAQ sections of both courses: the Princeton class focuses on implementation and practical programming with students in their first and second university years as the target audience. This Stanford version focuses on the analysis of algorithms and is usually taken by students in their third and fourth years.

I always knew going on that with a weak maths background, this course was going to be hard for me. It also didn’t help that I find myself much more interested in practical applications of algorithms than in studying and devising proofs of an algorithm’s correctness or performance claims. As such I didn’t put as much effort into this as I did for the Princeton course. Some observations:

  • The programming homework emphasizes actual implementations, with some tweaks, of the algorithms being studied. It’s a language agnostic course so you’re free to use whatever language you want. The professor just explains everything in pseudo-code while the homework provides a data set and you just have to type in the answers you get from processing the data for evaluation. I cheated. Having already covered much of the same ground in the Princeton course, which does provide complete implementations of all algorithms in Java, I simply used the Princeton library, tweaking code only as necessary to get the correct answers. For the most part, this made the programming homework very easy for me.
  • Th quiz portion was correspondingly harder for me. I found that I usually had a decent intuitive grasp of what to shoot for, but in many cases, lacked the discipline to thoroughly walk through the entire reasoning process. Especially since many of proofs requires a solid understanding of probability. The same goes for the final examination, which honestly speaking is slightly easier than the regular quizzes, but is timed and allows only a single attempt. We were allowed two attempts for each of the quizzes. I scored 32 out of 40 in the final exam. I did not attempt any of the optional and ungraded challenge questions.
  • I have to say that Professor Roughgarden’s lecture videos and study materials are very basic compared to the Princeton course. It’s just a talking head and slides, with no animations whatsoever. One major problem I had is that the audio frequently is not in sync with what is happening on the screen. For example, he would talk about something but when he refers to a mathematical formula or a snippet of code, it doesn’t show up on the whiteboard until a few seconds later, which certainly does not help comprehension. Also while he offers typed versions of the slides he uses as a download, he prefers the handwritten versions in the lecture videos, and his handwriting isn’t always perfectly legible.
  • I did appreciate the thoroughness with which he covers the proofs and I have to admit that I’m able to follow them much more closely than I did when professor Sedgewick went through them (which he didn’t always do in the Princeton courses. I still can’t say that it’s my favorite subject though.
  • As previously mentioned, the course does cover much of the same material so there was little here that I haven’t already seen before. I did appreciate learning about bloom filters. And after being frankly puzzled by the Kosaraju-Sharir algorithm in the Princeton course (easy to code, hard to intuitively understand) I really liked how professor Roughgarden’s explanations and the associated programming homework, allowed me to finally grasp it in my head.
  • I don’t believe that I ever saw any Community TAs in this course. By and large, as far as I could tell, the students did an excellent job of posing and answering questions themselves, with professor Roughgarden himself intervening only on rare occasions mostly related to technical problems with the course itself. I do find that the student body for this course appears more mature than that of the Princeton course, with few people posting frivolous questions or appearing to be completely clueless.
  • Certainly as the professor admits, the assessment system is currently the weakest part of the course. The course really needs a way to have students submit proofs and get them evaluated (which would have utterly defeated me I believe) but there’s simply no feasible way to scale anything like this. Also, the programming homework requires just an answer (usually just a string of numbers) without any of the performance and memory usage evaluations used in the Princeton course.

No surprise when I say that I prefer the Princeton course by a very large margin. But this is still an excellent, high quality course especially for those more interested in the analysis side of things. Incidentally I’ve been invited once again to serve as Community TA for the next offering of the Princeton course which should begin at the end of August.


Leave a Reply