Program Gallery

As with our proof gallery, programming often feels like art. Whereas mathematics is the art of argument, programming is more like architecture: it is the art of form and function, in the sense that the beauty of a program lies in its clarity and conciseness, and it’s ability to perform its function correctly and efficiently. Perhaps in contrast to a mathematical proof, there is sometimes a degree of absoluteness in the best way to do something, and when there is not there is a delicate balance between the different levels of optimization. One can use additional space, time, or preprocessing to achieve better results in the other two categories. Here we present a collection of short programs which illustrate these ideas, and are aesthetically pleasing. We will try to stay away from problems which are too domain-specific, instead favoring generalized algorithms (perhaps operating on dummy data, like integers) which can be applied to more specific problems.

Lists and Sequences

In-place uniform shuffle
Dynamic time warping for sequence comparison

Hash Tables

Caching (and memoization)

Data Analysis

Principal Component Analysis (Dimensionality Reduction)

Randomized Algorithms

Miller-Rabin Primality Test
Simulating a Fair Coin with a Biased Coin
Simulating a Biased Coin with a Fair Coin

Streaming Algorithms

Streaming median
Reservoir Sampling
Finding the majority element of a stream
Hashing to estimate the size of a stream

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s