So the Algorithms 1 class by Professors Robert Sedgewick and Kevin Wayne of Princeton on the Coursera platform just ended. I just made my second of three attempts on the final exam, scoring 18.31 / 20.00. I may yet make another attempt next week as everything officially closes only on 30 September 2012. It’s been an amazing experience and I learned way more than I expected. Some thoughts:

• I found that I’m pretty strong on practical programming. I could complete all of the programming assignments with not much trouble, and ended up spending a fair amount of time on the forums helping others out with their programs too. I only struggled somewhat when implementing the optional extra optimizations that the professors suggested which are not graded. This mostly involved doing the same thing with half the memory or less, or cutting running time down drastically. For example, the toughest timing trial of the collinear points assignment gave you a maximum of 10 seconds to solve the problem. My first attempt came in at just under 7 seconds, and after much agonizing I got it down to just under 3 seconds. The very best students were able to get it down to just under 2 seconds.
• However I am terrible on the theory. I blame that on a lack of solid grounding in mathematics. I really suck at calculating things like the order of growth of running time for different algorithms or the minimum and maximum heights of different tree-like data structures. This calls for a good grasp of discrete mathematics. I’m also bad at internalizing geometrical principles, so assignments like collinear points gave me more trouble than the supposedly more sophisticated A* algorithm we used to solve the 15-puzzle. I’m currently signed up for Sedgewick’s Analytic Combinatorics class which runs next year but I’ll probably flunk that one.
• This class really thought me how beautiful some algorithms are and how you can achieve so much in just a few lines of code. At heart, they’re all about pure logic so it’s possible to even describe them to people with no programming knowledge whatsoever. I also think I finally managed to get the hang of recursive functions while doing the Kd-Tree assignment. I’ve always had trouble visualizing them before.
• I also learned how very limited even the powerful computers we have available to us today are. As a science-fiction fan, I’ve always taken it for granted that one day, perhaps sooner than we expect, we’ll be able to simulate sentient minds and even whole worlds inside computers. Unfortunately, even the lowly 15-puzzle is enough to make modern computers struggle. It’s pretty humbling. As Sedgewick likes to emphasize, while we can always look forward to ever faster computers in the future, it is even more certain that the size of the problems we need to solve in the future will grow faster than our computers will become more powerful. As we can’t rely on ever more powerful computers to do the work, we must instead design ever more clever algorithms.

Anyway, Algorithms II starts up in November so I’ll be back at it pretty soon. In the meantime, I should have a little extra free time.

I’ve been remiss in writing for this blog because I’ve been busy with the courses I’ve been taking on Coursera.org. Currently I’m taking both Introduction to Finance and Algorithms. The Algorithms class is particularly challenging for me and involves significant work because there’s a programming assignment each week. It’s taught by Robert Sedgewick of Princeton, who is something of an authority in the subject. Interestingly, Sedgewick’s own doctoral thesis advisor was Donald Knuth, who is of course a legend in computer programming circles.

Anyway, just for fun, here’s a logical puzzle from a recent assignment for you to ponder over. I’ve converted it into a puzzle to make it more accessible, no actual programming necessary, but the essential logic of the problem remains the same.

Let’s say that you’re working at a booth of some sort and you have only one task. A client will come up to your booth and announce a number. Call this number k. This number represents how many items you will need to hand back to the client at the end of each task. The client then starts handing you items, let’s say they are beach balls, each of which are uniquely identifiable, one at a time. The client never tells you how many balls there are in total. He or she just starts handing them to you, one by one.

At some point, the client will announce that he or she has finished handing over balls. Now your job is to return k balls, selected with uniform randomness from the balls you were just given, back to the client. Sounds easy right? But here’s the constraint. Your booth can only store k balls at maximum. That is to say, you can only hold as many balls at a time as the number of balls you need to return to the client at the end of the task. You may choose to keep or discard any ball but once you choose to discard a ball it is gone forever and you can’t ever get it back.

So how do you ensure that you can select k number of items with uniform randomness, out of a pool of potentially many more items, while being restricted to only holding k items at a time?

Every month I read tons of articles online and save the science ones for my monthly features. I happen to have found too many cool articles this month and since some of these aren’t science-article, I thought I’d throw in an assorted links posts for them. Here goes:

•  Google gets involved in a lot of odd projects that on the face of it have little to do with their primary online search business. Well, this one may just be the oddest of them all. This article from The New York Times talks about how a Google laboratory cobbled together a machine-learning neural network from 16,000 processors and set it to the task of watching cat videos on YouTube. Result: a neural network that is really, really good at recognizing cats no matter what their size, shape or color and no matter what the cats are doing. Cue jokes about why Skynet wants to kill all humans.
• The next article is notably mostly because of how well it lends itself to jokes. It’s America’s hottest new export and it’s man-made! Talk about gross national product! Erect a new future today! America is in good hands! Follow the link to this The Daily article to find out what it is.
• Okay, so everyone know the Japanese are crazy about giant mecha but this post on the Anime News Network shows just how crazy that can be. Some quarters in the Japanese government are looking into the feasibility of building piloted walking combat robots and two members of the Liberal Democratic Party claim that they working to include realization of a Gundam Development Project into their manifesto.
• This last one isn’t a joke and will likely be of interest only to Malaysians. The listing of Felda Global Ventures Holdings Bhd. (FGVH), effectively the third largest oil palm company in the world, has hit headlines due to being the second biggest IPO this year, after Facebook. This investor’s report from a Netherlands-based analyst makes for an eye-opening read since it goes far beyond FGVH’s financials into the history of the Felda project, its links with key government officials and why the settlers are so opposed to the IPO. It basically tells global investors to stay away because it’s a gigantic scam due to poor expected returns and undisclosed political risks and further argues that investing in it would be unethical as the IPO directly undermines Malaysia’s fledgling democracy.