HALT
The Eight Queens
1st of 92, after 113 placements
Max Bezzel posed the puzzle in 1848 and Nauck published all 92 solutions in 1850. It became the standard example of backtracking: place a queen in each file, try the ranks from the bottom, retreat when a file has no safe square. The first answer comes after 113 placements: a1, b5, c8, d6, e3, f7, g2, h4.
HALT
The Finite Automaton
accepts binary multiples of 3
A finite automaton reads its input once, remembering only which of finitely many states it is in. Reading a binary number from the top bit doubles the value and adds the new bit, so three states, the remainders mod 3, suffice. Tested on every number to 200,000, it is never wrong, and no smaller machine exists.
HALT
The Glider Gun
period 30, gliders at c/4
Conway’s Game of Life has two rules: a dead cell with exactly three live neighbors comes alive, and a live cell survives with two or three. Conway offered fifty dollars for a pattern that grows without limit, and Gosper’s group won in 1970 with this gun: 36 cells throwing off a glider every 30 generations. At generation 120: 56 cells.
HALT
The Turing Machine
busy beaver: 107 steps, 13 ones
Tibor Radó asked in 1962 which halting machine with n states runs longest from a blank tape: the busy beaver, uncomputable in general. The four-state champion runs exactly 107 steps and leaves 13 marks; Allen Brady proved in 1983 that none does better. Simulated, it stops with the head over the only gap in its block of marks, as here.
HALT
The Towers of Hanoi
move 85 of 255
Lucas sold the puzzle in 1883 with a legend of priests moving 64 disks. Moving n disks takes 2ⁿ − 1 moves, 255 for eight. The optimal solution hides a binary counter, and when odd and even disks are colored differently, no disk lands on its own color. After move 85, a third of the way, the disks sit in threes.
WORST CASE
The Red–Black Tree
keys 1–20 in order, 3 black per path
Insert the keys 1 to 20 in order into a binary search tree and it becomes a list twenty levels deep. Guibas and Sedgewick’s coloring of 1978 prevents it: the root is black, no red node has a red child, and every path passes the same number of black nodes. Insertion gives six levels, five red nodes and 14 rotations.
WORST CASE
The Huffman Tree
The Zen of Python: 4.14 bits a letter
In 1951 David Huffman, a graduate student in Fano’s class at MIT, showed that building a code from the bottom, always joining the two lightest pieces, is optimal. The weights here are the 677 letters of The Zen of Python: 2,802 bits, 4.139 a letter, against an entropy of 4.117 and a 17% saving on a fixed five-bit code.
WORST CASE
Orders of Growth
1 < log n < n < n log n < n² < 2ⁿ < n!
The seven curves every algorithms course draws, here to scale. Their order is only settled on the right: 2ⁿ and n² meet at 2 and again at 4, where 2ⁿ pulls ahead for good, and n! starts below 2ⁿ and passes it near 3.46. The constants hide in the O, and crossings like these are why they matter.
WORST CASE
The Sorting Network
19 comparators, depth 6
A sorting network compares fixed pairs of positions in a fixed order, whatever the data, which is exactly what hardware likes. Batcher’s odd–even merge sort of 1968 sorts eight inputs with 19 comparators in six layers, and no network beats either number. This one sorts all 40,320 orderings of eight values; remove any one comparator and it fails.
WORST CASE
The Skip List
16 keys, the 13th found in 8 moves
Pugh’s skip list of 1990 keeps every key in a sorted linked list, and each key flips coins to decide how many express lanes it joins. A search runs along the highest lane until it would overshoot, then drops down. Here 8, 4 and 2 keys reached levels 2, 3 and 4, as expected, and the 13th takes 8 moves.
FIVE NINES
The Dining Philosophers
5 forks, 1 cycle: deadlock
Dijkstra set the problem in 1965; Hoare gave it five philosophers and spaghetti. If every philosopher takes the left fork first, all can do so at once, then each waits forever for a fork a neighbor holds. A check of every interleaving finds 82 states and one deadlock, this one. Let one diner reach right first: 70 states, no deadlock.
FIVE NINES
The T568B Pinout
pins 3 and 6: the split pair
The TIA/EIA-568 standard of 1991 fixed two ways to wire an eight-contact plug. In T568B the green pair is split around the blue pair, which sits in the center where telephone jacks put their single line. 10BASE-T and 100BASE-TX use only pins 1, 2, 3 and 6. Wire A at one end and B at the other for a crossover.
FIVE NINES
The Hamming Code
1011 → 0110011
Hamming, tired of losing jobs to a relay computer that stopped at every error, published this code in 1950. Four data bits go in the overlaps of three circles and three parity bits in the outer regions, each making its circle even. The data 1011 becomes 0110011, and any single flipped bit leaves exactly the circles that contain it odd.
FIVE NINES
Consistent Hashing
each key goes to the next shard clockwise
Send each key to server h(k) mod n, and going from four servers to three moves 18 of these 24 keys. Consistent hashing, published by Karger and colleagues in 1997, puts servers and keys on one circle and gives each key to the first server clockwise. Placed by MD5, the four shards here hold 4, 5, 7 and 8 keys.
FIVE NINES
RAID 5
lose any one disk, rebuild it by XOR
Patterson, Gibson and Katz argued at Berkeley in 1988 that arrays of cheap disks could beat expensive ones. RAID 5 stores the XOR of each stripe’s data as parity, and because XOR undoes itself, any one lost disk is the XOR of the rest. The parity moves one disk over each stripe, so no single drive takes every parity write.
LEGACY CODE
Magnetic-Core Memory
256 bits, one ferrite ring each
From the mid-1950s to the mid-1970s most memory was ferrite rings, one per bit, magnetized one way or the other; Forrester’s group put it into MIT’s Whirlwind in 1953. Half the switching current on a row wire and half on a column wire flips only the core where they cross. Reads were destructive, so each was followed by a rewrite.
LEGACY CODE
0.1 in Floating Point
0x3DCCCCCD = 0.100000001490116…
One tenth has no finite binary expansion: it is 1.6 × 2⁻⁴, and 1.6 in binary repeats 1001 forever. IEEE 754 single precision keeps 23 fraction bits, and the next three, 110, round the last byte up to 1101. The stored value is 0x3DCCCCCD, exactly 0.100000001490116119384765625. In double precision the same effect makes 0.1 + 0.2 print 0.30000000000000004.
LEGACY CODE
The Jacquard Loom
one card per row, 1804
One card per row of weaving, laced into a chain, made the pattern a program: change the cards and the same loom weaves a different cloth. Ada Lovelace wrote in 1843 that Babbage’s Analytical Engine would weave algebraical patterns as the loom wove flowers and leaves. These eight cards, sixteen hooks wide, weave a diamond lattice, hole for hole.
LEGACY CODE
The Punched Card
10 GO TO 10
IBM’s 80-column card of 1928 held one character per column in twelve rows: a digit is one punch, a letter two. FORTRAN, from 1957, read labels from columns 1 to 5 and statements from column 7, so this card, label 10 and GO TO 10, is an infinite loop. Dijkstra’s letter Go To Statement Considered Harmful came eleven years later.
LEGACY CODE
Difference Engine No. 2
7th differences, 31 digits
Any polynomial can be tabulated by addition alone, because its differences of high enough order are constant. Babbage designed Difference Engine No. 2 between 1847 and 1849 for seventh-degree polynomials to 31 digits, with eight columns of figure wheels. It was never built in his lifetime; the Science Museum built the calculating section from his drawings between 1985 and 1991.
HELLO, TRIANGLE
The Cornell Box
Goral et al., SIGGRAPH 1984
In 1984 Goral, Torrance, Greenberg and Battaile at Cornell presented radiosity, light bouncing between diffuse surfaces, and tested it on a box, later built and measured so that renders could be checked against photographs. Red wall left, green right, two white blocks turned about 17° opposite ways. The test is color bleeding, which only global illumination reproduces.
HELLO, TRIANGLE
Barycentric Interpolation
The first program in almost every graphics tutorial: one triangle with red, green and blue corners. The rasterizer weights each pixel by the areas of the three small triangles it makes with the corners, so edge midpoints are half-and-half mixtures, olive, teal and purple, and the center is a third of each: 85 of 255 per channel, a dim gray.
HELLO, TRIANGLE
The DCT Basis
64 patterns for one 8 × 8 block
Ahmed, Natarajan and Rao published the discrete cosine transform in 1974; in 1992 it became the core of JPEG. Each 8 × 8 block is rewritten as a weighted sum of these 64 patterns. Natural images put most of their energy at the top left, so the rest can be quantized coarsely or dropped. A bad JPEG shows these tiles.
HELLO, TRIANGLE
The Bézier Curve
de Casteljau at t = 1/3
De Casteljau’s construction is repeated interpolation: cut each side of the control polygon at the same fraction t, join the cuts, cut again, and after three rounds the last point lies on the curve. Doing it for every t from 0 to 1 traces the cubic. Computed at t = 1/3 in exact fractions, it matches the Bernstein polynomial exactly.
HELLO, TRIANGLE
Recursive Ray Tracing
after Whitted, 1980
In 1980 Whitted at Bell Labs followed rays back from the eye and, at every surface, spawned new ones toward the lights, in the mirror direction and through the glass, recursively. His glass and mirrored spheres over red and yellow checks set the look of ray tracing. Traced six bounces deep, the glass sphere here inverts the checks behind it.