Stack Overflow

I answer algorithm questions on Stack Overflow. Here is my profile.

Strawberry Fields

Strawberry Fields is a combinatorial optimization problem posed by ITA Software. I started working on it because I thought it was neat that, for the natural LP relaxation, the column generation subproblem is the two-dimensional maximum subarray problem examined by Jon Bentley in Programming Pearls. It turns out that Kadane’s algorithm for the maximum subarray problem cannot handle the side constraints introduced by branch and price, but the solver that I built for Strawberry Fields is still four orders of magnitude faster on the sample instances than a commercial integer program solver with no problem-specific tuning.

Since ITA Software has stopped using Strawberry Fields as a recruiting puzzle, here is my source code (tbz), to which I reserve all rights.

PlanetLab

When I was a PhD student at Princeton, I worked on PlanetLab, a globally distributed cloud computing service for networking research. I implemented from scratch version 4 of Node Manager, which runs on each server and handles requests to provision virtual machines, and I maintained the backend of Sirius, a service that accepts reservations for system resources. I also wrote tutorial documentation for both Sirius and the programmatic interface to PlanetLab Central, the default service for managing collections of virtual machines.

Dodge

Dodge is a simple Flash game by Lewpen Kinross-Skeels. It’s difficult to play on a touchpad, and that was my excuse for not beating my friends’ scores until I wrote a program to do this (Vimeo).

Facebook puzzles

Facebook used to maintain a small collection of programming puzzles. I wrote an unofficial guide that was linked to by Slashdot.

Project Euler

Project Euler is a growing collection of mathematics/programming problems. I solved the first 250 and briefly was ranked #1.

Operating Systems

I wrote specifications for projects two and three of Princeton’s COS 318 (Operating Systems).

Snake lemma

The snake lemma is a basic result in a branch of mathematics called homological algebra. I wrote a program to find a proof by diagram chasing.

Graph polynomials

For my research, I wrote Java applets that, given a rooted graph where edges (Java) or vertices (Java) are deleted independently with probability 1 - p, compute the expected number of non-root vertices in the connected component containing the root.

“Dahlia”

“Dahlia”, my entry in Keith Enevoldsen’s Logo 15-Word Challenge, is my oldest surviving program. It won the “Pure Logo” prize.

repeat 8 [rt 45 repeat 6 [repeat 90 [fd 2 rt 2] rt 90]]

repeat 8 [rt 45 repeat 6 [repeat 90 [fd 2 rt 2] rt 90]]