Sampling from a Stream

Selecting a random element from an array of length n is easy: simply generate a random integer i, with 0 <= i < n, and use the array element at that index position. But what if the length of the array is not known beforehand, or is, in fact, infinite (i.e. a stream)? And what if we don’t just want a single element, but a set of m samples, without replacement?

Random Shuffles

Shuffling a collection of items is a surprisingly frequent task in programming: essentially, it comes up whenever a known input must be processed in random order. What is more, there is a delightful, three-line algorithm to accomplish this task correctly, in-place, and in optimal time. Unfortunately, this simple three-line solution seems to be insufficiently known, leading to various, less-than-optimal ad-hoc alternatives being used in practice — but that is entirely unnecessary!

Nelder-Mead Simplex Optimization

The Nelder-Mead-Algorithm (also known as the “Simplex Algorithm” or even as the “Amoeba Algorithm”) is an algorithm for the minimization of non-linear functions in several variables. In contrast to other non-linear minimization methods, it does not require gradient information. This makes it less efficient, but also less prone to divergence problems. In contrast to other methods, it is not necessary for the minimum to be bracketed by the initial guess: the algorithm performs a limited “global” search. (It may still converge to a local, rather than the global extremum, of course.) Finally, the algorithm is fairly simple to implement as a stand-alone routine, which makes it a natural choice for multi-dimensional minimization if function evaluations are not prohibitively expensive.

The Diamond-Square Algorithm for Terrain Generation

The Diamond-Square Algorithm for Terrain Generation

The Diamond-Square Algorithm is the natural first stop for generating artificial landscapes. The algorithm itself is beautifully simple (more details below, and on its Wikipedia page). But a casual implementation ended up not working at all, prompting me to look for an existing implementation to learn from. However, most implementations I found looked hideously complicated (or just hideous), not necessarily correct, and/or used out-of-date programming languages and styles. It therefore seemed like a good idea to create a clean, simple “reference” implementation of this algorithm, using a contemporary and widely known programming language and style.