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
Streaming median
Dynamic time warping for sequence comparison

Hash Tables

Caching (and memoization)

Data Analysis

Principal Component Analysis (Dimensionality Reduction)