Monthly Archives: May 2013

Personal Life

End of Algorithms 2 class

Leave a comment

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.

Science

Recent Interesting Science Articles (April 2013)

Leave a comment

Late this month due to an extended stay in Kuala Lumpur for the Malaysian general elections. Here are the three articles I’ve managed to glean from around the web in April.

  • This article from the Pacific Standard magazine covers a paper whose authors examined the obituaries of over 1,000 famous people published in The New York Times to determine if there are any patterns in them. They found that the famous people who died earliest were athletes, performers and non-performers who worked in creative fields. The famous people who died later were politicians, businessmen and military officers. The tentative conclusion is that people who work in sports and the performing arts incur psychological and physical costs that curtail their lifespan.
  • Here’s a link to a paper claiming that vervet monkeys were able to solve a multiplayer coordination “game” in which a captive monkey was trained to open a container holding a large amount of food, but only if the dominant monkeys of a wild troop stayed outside of an imaginary circle away from the food. The wild monkeys were able to infer the correct behavior by observing the trained monkey and receiving feedback from the trained monkey without the intervention of humans.
  • The Economist has an article talking about the tells that give players away when playing say a game of poker. Most people instinctively believe that the key to not giving away information about the hand you’re holding to other players is in keeping a straight face. As it turns out, experiments show that observers achieve a much higher success rate at correctly predicting the quality of a hand of cards held by another person not by looking at the player’s face but by looking at the player’s hands. This is sure to be a result that will revolutionize poker playing strategies.