Sunday, July 18, 2010
New Camera!
I am now the proud owner of a Panasonic Lumix DMC-ZS7. Today I took some photos with it around the Google campus. One of my favorite features of the camera is that it tags pictures with GPS coordinates. Picasa Web Albums automatically creates a Google Map with the photo locations.
Sunday, July 11, 2010
Demon's Souls
Today I finally beat Demon's Souls. I am pretty proud of this accomplishment given how ridiculously hard the game is. It is the best PS3 game I have played.
Tuesday, June 22, 2010
RoboCup 2010
I am currently in Singapore attending RoboCup 2010. UBC Thunderbots is competing in the small size league. We played four games and did not advance to the semi-finals. We lost three games and won one game. The Thunderbots website has lots of pictures, videos, and a blog. I will be in Singapore for one week.
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 =)
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
siarco
I just released an open source version of the arithmetic coder I discussed in my previous post. The project is hosted at http://code.google.com/p/siarco/.
Sunday, May 16, 2010
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 =)
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
Googleplex
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.
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.
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.
Saturday, April 10, 2010
Imagine Cup
Surprisingly, we advanced to round 2 of Imagine Cup. Here is the demo we submitted. 150 teams out of 700 advanced. Only 6 teams advance to the finals. We are debating whether finishing the game is worth the time investment given we have such a low probability of making it to the finals :D
Friday, April 02, 2010
Tuesday, March 30, 2010
Googleplex
I just accepted the internship offer from Google. I will be headed to the Googleplex this summer. Numenta replied saying that they will not be giving me an offer. I will be doing a 14 week internship at Google. When I finish the internship in August I plan on visiting my parents in Sri Lanka for a few weeks before returning to UBC.
Monday, March 22, 2010
Summer Internship
Today I got internship offers from both Google and Facebook. I am just waiting to hear back from Numenta before I make a decision of which to accept. On Friday I visited Numenta for a full day of interviews. Jeff Hawkins and I were on the same flight to San Francisco. We shared a taxi from UBC to the airport and he even gave me a ride to my hotel after the flight! It was a great opportunity to talk with him about HTM.
Monday, March 15, 2010
Sunday, March 14, 2010
Contests and Interviews
There is a new programming contest on Al Zimmermann's webpage: http://www.azspcs.net/Contest/MagicWater. I am currently ranked 8th out of 56. The contest lasts months, so there is no way I will maintain this high rank :D. On the son of darts contest I currently have a score of 90.00 and a rank of 59 out of 384.
Three friends and I are entering the Game Design category of Imagine Cup. Today we submitted a game demo. It is a simple text adventure game using Silverlight. The game also works in Linux using Moonlight. I wrote the text parser for the game. Our team was speculating that we probably put the fewest man-hours into making the game out of all the competitors (so I will be surprised if we advance to future rounds). If we make it to the finals we get a free trip to Poland.
I am currently in the interview process with Google, Facebook, IMO, and Numenta for a summer internship. Later this week I will be flying down to California for a full day interview at Numenta. Coincidentally, Numenta's founder Jeff Hawkins is giving a talk at UBC this week. I have scheduled a meeting with him when he gets here!
Three friends and I are entering the Game Design category of Imagine Cup. Today we submitted a game demo. It is a simple text adventure game using Silverlight. The game also works in Linux using Moonlight. I wrote the text parser for the game. Our team was speculating that we probably put the fewest man-hours into making the game out of all the competitors (so I will be surprised if we advance to future rounds). If we make it to the finals we get a free trip to Poland.
I am currently in the interview process with Google, Facebook, IMO, and Numenta for a summer internship. Later this week I will be flying down to California for a full day interview at Numenta. Coincidentally, Numenta's founder Jeff Hawkins is giving a talk at UBC this week. I have scheduled a meeting with him when he gets here!
Saturday, March 06, 2010
Son of Darts
I spent the entire day working on Son of Darts. I am now in 71st place out of 379. My current submissions use a variety of searches including stochastic local search, backtracking, greedy, and various heuristics. Out of the 19 Canadian competitors I have the highest score :D
Wednesday, February 17, 2010
Contests
UBC has a two week break due to the Vancouver Olympics. I have been using the time to work on various programming projects. I have become involved in a number of contests:
-RoboCup: A robot soccer contest. I am working on the AI for the robots. We recently sent in qualification materials. If we qualify, we get to compete at RoboCup 2010 in Singapore this summer. Last year we went to Austria for the contest.
-ImagineCup: Our team is planning to compete in the game design category. We haven't done much implementation yet, but we plan on creating a text adventure game (plus some simple graphics). If we make it to the finals we get to go to Poland this summer.
-Son of Darts: I just started this contest a couple of days ago. I am currently ranked 145th out of 368 competitors. I am using stochastic local search to optimize the solutions.
-BattleCode: A fun AI programming contest. Last year our team did pretty well.
This break I am also planning on submitting a paper about PPM to a NLP workshop. I also need to study for a big midterm happening in two weeks. It is going to be a busy break!
-RoboCup: A robot soccer contest. I am working on the AI for the robots. We recently sent in qualification materials. If we qualify, we get to compete at RoboCup 2010 in Singapore this summer. Last year we went to Austria for the contest.
-ImagineCup: Our team is planning to compete in the game design category. We haven't done much implementation yet, but we plan on creating a text adventure game (plus some simple graphics). If we make it to the finals we get to go to Poland this summer.
-Son of Darts: I just started this contest a couple of days ago. I am currently ranked 145th out of 368 competitors. I am using stochastic local search to optimize the solutions.
-BattleCode: A fun AI programming contest. Last year our team did pretty well.
This break I am also planning on submitting a paper about PPM to a NLP workshop. I also need to study for a big midterm happening in two weeks. It is going to be a busy break!
Saturday, February 06, 2010
Harbin Trip
Over the last week I have been in China attending the ACM ICPC World Finals. The trip was really fun. I got invited to come even though I am not a competitor since I might be part of the UBC team next year. Six people from UBC came (one coach, three competitors and another guest). Harbin is in the northern part of China so was extremely cold. The temperature was usually between -10 to -30 Celsius. I have posted pictures of my trip here. There were a lot of activities organized by ACM so there wasn't much time to explore Harbin ourselves. Harbin is famous for ice and snow sculptures. There were sculptures lining the streets all over the city.
UBC did well at the finals. They got 18th place. I think UBC's record is 13th place. Here is the final scoreboard. There were three North American teams which did better: Stanford, Cornell, and Carnegie Mellon. These teams only did better on time and did not solve more problems than UBC. All three members of this year's team are not eligible to compete again next year. Based on the performance of the second and third UBC teams, it is extremely unlikely we will be nearly as good next year.
UBC did well at the finals. They got 18th place. I think UBC's record is 13th place. Here is the final scoreboard. There were three North American teams which did better: Stanford, Cornell, and Carnegie Mellon. These teams only did better on time and did not solve more problems than UBC. All three members of this year's team are not eligible to compete again next year. Based on the performance of the second and third UBC teams, it is extremely unlikely we will be nearly as good next year.
Subscribe to:
Posts (Atom)