Thursday, May 20, 2010

TopCoder Open

Today I discovered that TopCoder is hosting an interesting marathon match over the next month. The problem is pretty simple:

Input: list of edges
Output: vertex locations
Goal: minimize number of edge intersections

There is an online scoreboard which shows your ranking after each submission. I was in last place after my first submission. My second submission was quite an improvement and put me in second place =)

Monday, May 17, 2010


I just released an open source version of the arithmetic coder I discussed in my previous post. The project is hosted at

Sunday, May 16, 2010

Nice Weather


Arithmetic Coding

This week I wrote a program to perform arithmetic coding. Arithmetic coding is useful for data compression. This summer I plan to release an open source lossless data compression algorithm which uses the coder.

The program to do the arithmetic coding is only around 150 lines of Java code. For a while I had a really annoying bug related to precision errors with floating point numbers. The vast majority of the time I spent developing the program was trying to fix this bug. Today I finally figured out a great solution to the precision problem which has almost no computational overhead and is theoretically guaranteed to always be correct.

Wikipedia claims "every programmatic implementation of arithmetic encoding has a different compression ratio and performance." I find this statement surprising because I think I can construct a proof showing that my program encodes the input with exactly the minimal number of bits. If the number of bits is not divisible by 8, my program uses a few extra bits in order to store the resulting bytes to disk. As far as I know it is impossible for another arithmetic coder to achieve a better compression ratio. I tried testing the program on several files and it achieved a compression ratio extremely close to the theoretical cross entropy limit.

In terms of performance my algorithm also has nice properties. The time and space complexity are both linear in terms of the number of input characters (which is optimal). The code only performs basic arithmetic operations on primitive data types, so it should also be very efficient. The code works with any input alphabet size. I plan to convert the program to optimized C code and compare its performance to other arithmetic coders. Since I am already confident that its compression ratio can not be beaten, if it turns out to be faster than other arithmetic coders as well, then my algorithm could be an important contribution =)

Sunday, May 09, 2010


I really enjoyed my first week at Google. So far I have mostly been doing training. The food at the Googleplex is amazing. I will be eating breakfast, lunch, and dinner there, so I will only have to cook for myself on weekends. I have been trying to go to a different café for every meal. My apartment is about a 30 minute bike ride from the campus, so that exercise might help counteract the abundance of free food. Google gave me a nice bike to use over the summer.

Yesterday I bought a new monitor so that I can play my PS3. I also bought a game called Demon's Souls. I tried getting Demon's Souls at three different places in Vancouver but they were all sold out. In Mountain View I tried checking Best Buy and Toys Я Us but they were also sold out. Finally, I found a copy at Game Stop (which turned out to be their last copy). The ridiculous thing is that this game was released over half a year ago. The gameplay is incredibly addicting (and incredibly difficult). It is the best PS3 game I have played.

Suitcase Computer

I recently discovered that traveling with a desktop computer in a suitcase is a bad idea. When I was packing for my trip to Mountain View I spontaneously decided to bring my desktop computer since I had lots of extra room in my suitcases. I have traveled with a desktop computer before without any problems.

The first annoyance was that both my suitcases were way over the weight limit, so I was charged expensive overweight fees. I would have been under the weight limit without the computer. When I arrived in Mountain View and started unpacking the computer, I noticed a horrible rattling sound when I moved it. A rattling sound indicating loose components in the case.

The CPU heatsink had somehow become detached and was bouncing around inside the case the entire trip. Today I bought some thermal grease and reattached the heatsink. When I tried to boot the computer it started making beeping sounds and immediately shutdown. It is most likely the motherboard which was damaged. I wish I had just left the computer in Vancouver.