Computer Science · Subject 12

Computer Science

Turing machines, trees and the code you write, on button-ups, ties and socks.

This week in Computer Science,

The spring clock change made university staff likelier to click a phishing link, a language model quietly silences a code scanner’s warnings, a chip naps on nanowatts, and generalized Kalah turns out to be PSPACE-complete.

Get it by email

Download MP3

Behind this page the view dives into a laptop as you scroll, one picture after another, like the film Powers of Ten: the laptop closed on a desk (the picture 68 cm across), the laptop opened (32 cm), its processor package (6 cm), the silicon die (1.8 cm), one processor core (3 mm), rows of logic cells under an electron microscope (4 micrometers), the lowest layers of copper wiring (600 nanometers) and, at the bottom, one gate-all-around transistor: three stacked silicon sheets with the gate wrapped all the way around each (100 nanometers). From the desk to the transistor is a zoom of about 6.8 million times. Each picture holds the next one at its center, and a scale bar follows the zoom. The pictures are illustrations.

Welcome in

For anyone who counts from zero

You know the whiteboard, the marker that is always nearly dry, and the tree you drew on it that needed one more rotation before anyone would hire you. You have typed 0.1 + 0.2 into a console and watched it answer 0.30000000000000004, and you have explained why to someone who did not want to know. You remember the first program that surprised you: a recursion that solved a puzzle you could not, or a search that found an answer on its own.

Start with everything

FULL STACK, Bone
FULL STACKRegular price $65 Sale price $58.50Shop now

Colorway
Bone

Whole-field medallions · repeats every 18 in

Short-sleeve button-up · XS–4XL

FULL STACK

The whole field, on one shirt.

Computer Science brought together in one design, printed edge to edge: 25 medallions from the field’s designs, with the equations from across the subject. Related images are spread across the pattern so no two neighbors repeat.

  • Print scaleThe pattern repeats every 18 inches, with seamless edges.
  • StylesPhotoreal on bone, engraving or blueprint.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

STACK OVERFLOWING, Paper
STACK OVERFLOWINGRegular price $65 Sale price $58.50Shop now

Colorway

Contour map · repeats every 18 in

Short-sleeve button-up · XS–4XL

STACK OVERFLOWING

A topographic portrait of the field.

Recognizable forms from Computer Science rise as contour landscapes. Lines follow the outlines and continue across the ground between them, with names fitted along the contours.

  • Print scaleThe pattern repeats every 18 inches, with seamless edges.
  • The paletteTwo colorways, shown at the same print scale.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

Socks mix and match across every field: three pairs for $69, and two ship free in the U.S.

Crew socks · One size

Crew socks

A field of your own, from cuff to toe.

  • The pattern
  • The previewA studio mockup; photos of the finished pair are on the way.
Shop now · Regular price $26 Sale price $23.40

Leave your email and we’ll write the day this pair is ready.

Necktie · 3.5 in wide

Subject ties

A formal introduction to your field.

  • The color
  • The previewStudio render of the tie. Zoom shows the print up close.
Shop now · Regular price $36 Sale price $32.40

Leave your email and we’ll write the day this tie is ready.

More designs to explore

Short-sleeve button-up · XS–4XL

HALT

Five machines, and exactly when each one stops (one never does).

In 1936 Alan Turing reduced computation to a strip of tape, a head that reads and writes one cell at a time and a finite table of states, and proved that no program can decide, for every program, whether it will ever stop. Tibor Radó turned that into a game in 1962: of all the machines with a given number of states that halt on a blank tape, which runs longest? The four-state champion runs for exactly 107 steps and leaves 13 marks, and Allen Brady proved in 1983 that none does better. Five states took until 2024, when an online collaboration proved that the champion halts after 47,176,870 steps and had the proof checked by machine.

The other machines here stop on schedule too. A finite automaton with three states, the remainders 0, 1 and 2, reads a binary number once, left to right, and knows at the end whether three divides it; Rabin and Scott formalized the model in 1959. Backtracking on the eight queens, a puzzle Max Bezzel posed in 1848, finds its first answer after 113 placements and all 92 after 2,056. Édouard Lucas’s Towers of Hanoi of 1883 take 255 moves for eight disks, and the recursion hides a binary counter. And one machine never stops: the glider gun Bill Gosper’s group found in 1970 for Conway’s Game of Life sends out a glider every 30 generations, forever.

  • The Eight QueensEight ivory queens on an ebony and boxwood board, none attacking another: the first of the 92 solutions backtracking finds.
  • The Finite AutomatonThree brass rings for the remainders 0, 1 and 2, joined by gold and silver arrows: a machine that tests for division by three.
  • The Glider GunGosper’s glider gun in lit glass tiles at generation 120: the gun across the top and four gliders streaming away diagonally.
  • The Turing MachineA brass and paper-tape Turing machine at the moment it halts: thirteen marks, one gap under the head, a red lamp lit.
  • The Towers of HanoiWalnut and brass Towers of Hanoi at move 85 of 255, the eight disks dealt out in threes, ivory and vermilion alternating.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

Short-sleeve button-up · XS–4XL

WORST CASE

Guarantees that hold even when the input is out to get you.

An algorithm is judged by its worst case, and the growth curves every algorithms course draws say why: constant, logarithmic, linear, n log n, quadratic, exponential and factorial. Paul Bachmann introduced the O symbol in 1894, Edmund Landau spread it, and Donald Knuth brought Omega and Theta into computer science in 1976. The worst case for a plain binary search tree is sorted input: insert the keys 1 to 20 in order and it becomes a list twenty levels deep. A red–black tree, the coloring Guibas and Sedgewick introduced in 1978, comes through it six levels deep, with three black nodes on every path; the same structure sits under Java’s TreeMap and the Linux scheduler.

Other guarantees come from fixed wiring, from coin flips and from counting. Ken Batcher’s odd–even merge network of 1968 sorts any eight values with 19 comparators in six parallel layers, whatever the data, and no network does better on either count. William Pugh’s skip list of 1990 flips a coin for each key instead of rebalancing and still finds any key in expected logarithmic time; Redis sorted sets are skip lists. And in 1951 David Huffman, offered a term paper instead of Robert Fano’s final exam, found the optimal prefix code. Built from the letters of The Zen of Python, it needs 4.139 bits a letter against an entropy of 4.117.

  • The Red–Black TreeTwenty glass spheres on brass rods, black obsidian and ruby red: the red–black tree left by inserting 1 to 20 in order.
  • The Huffman TreeA Calder-style mobile of 24 vermilion balls, one for each letter of The Zen of Python, the commonest hung highest.
  • Orders of GrowthSeven neon tubes, green to red, for constant, log n, n, n log n, n², 2ⁿ and n!, crossing near the corner.
  • The Sorting NetworkBatcher’s network for eight inputs in brass and steel: eight rods and 19 comparator bridges in six layers.
  • The Skip ListSixteen brass towers of one to four stories strung with express wires, one search path glowing its way to the 13th.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

Short-sleeve button-up · XS–4XL

FIVE NINES

Deadlock, dead disks and flipped bits: 5 minutes 16 seconds of downtime a year.

Five nines means a system is up 99.999% of the time, about five minutes and sixteen seconds of downtime a year, and getting there means planning for everything that fails. Software can fail by waiting. Edsger Dijkstra set the problem in 1965 as an exam question about computers sharing tape drives, and Tony Hoare retold it as five philosophers around a table with a fork between each pair. If each picks up the left fork first they can all do so at once and then wait forever: checking every interleaving finds 82 reachable states and exactly one deadlock. Let one philosopher reach right first and the circle of waiting, one of Coffman’s four conditions for deadlock, is broken.

Hardware fails by flipping bits and dying. At Bell Labs in the late 1940s Richard Hamming lost weekend jobs to a relay computer that stopped at every error, asked why a machine that could find an error could not fix it, and in 1950 published the answer: three parity bits that locate any single flipped bit among seven. RAID 5, one of the levels Patterson, Gibson and Katz named at Berkeley in 1988, rebuilds any lost disk as the XOR of the survivors. Consistent hashing, published by Karger and colleagues at MIT in 1997, lets a server leave and moves only its own keys. And none of it works if the cable is crimped wrong.

  • The Dining PhilosophersFive plates of spaghetti around a walnut table seen from above, every fork on the same side of its plate: deadlock.
  • The T568B PinoutA clear network plug crimped in T568B order: white-orange, orange, white-green, blue, white-blue, green, white-brown, brown.
  • The Hamming CodeThree overlapping disks of stained glass with seven lamps, four of them lit: the (7,4) codeword for 1011, even in every circle.
  • Consistent HashingA steel hash ring with four large glass beads for shards and 24 small ones for keys, each tinted by the next shard clockwise.
  • RAID 5Four drive frames of glass blocks, a mirror-silver parity block stepping one disk over on every stripe.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

Short-sleeve button-up · XS–4XL

LEGACY CODE

Everything you run descends from these.

Programs began as holes. Joseph-Marie Jacquard’s loom, patented in 1804, lifted its warp threads on hooks, each left in play or pushed aside by a needle that met either a hole or solid pasteboard in the card, one card for each row of the weave. Charles Babbage owned a silk portrait of Jacquard woven from some 24,000 of them and planned to feed his Analytical Engine the same way. His Difference Engine No. 2, designed between 1847 and 1849 to tabulate polynomials to 31 digits by addition alone, was never built in his lifetime; the Science Museum in London built its calculating section between 1985 and 1991, and it worked. Herman Hollerith’s cards counted the 1890 United States census.

IBM’s 80-column card of 1928 carried programs for half a century, and anyone who uses a terminal still lives in its 80 columns; this one holds a single line of FORTRAN, 10 GO TO 10, an infinite loop in twelve holes. From the mid-1950s to the mid-1970s most memory was ferrite rings the size of a pinhead, one per bit, switched by coincident currents. Reading destroyed the bit, and a memory image is still called a core dump. And IEEE 754, the floating-point standard of 1985 shaped by William Kahan, still cannot hold a tenth exactly: in single precision 0.1 is stored as 0x3DCCCCCD, too large by 1.5 × 10⁻⁹.

  • Magnetic-Core MemoryA 16 × 16 plane of ferrite cores threaded with copper, each ring tilted against its neighbors in a fine herringbone.
  • 0.1 in Floating PointA brass console register of 32 jewel lamps holding 0.1 in single precision, 0x3DCCCCCD: the repeating 1100, rounded up at the end.
  • The Jacquard LoomEight laced Jacquard cards above the silk ribbon they wove, a gold diamond lattice, each card one row of it, hole for hole.
  • The Punched CardA blank manila 80-column card with twelve rectangular holes: the FORTRAN line 10 GO TO 10, an infinite loop.
  • Difference Engine No. 2Babbage’s Difference Engine No. 2 in bronze and iron: eight columns of 31 figure wheels, carry levers climbing in a helix.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

Short-sleeve button-up · XS–4XL

HELLO, TRIANGLE

Every picture on every screen, from one triangle to the light in a room.

Every picture on every screen starts as arithmetic. The first program in almost every graphics tutorial draws one triangle with a pure red, a pure green and a pure blue corner, and the rasterizer gives each pixel three barycentric weights and blends the corners with them; at the center all three weights are a third, which makes a dim gray, not white. Curves are interpolation too. Paul de Casteljau at Citroën in 1959 and Pierre Bézier at Renault in the 1960s needed smooth curves that engineers could steer by moving a few points, and repeated interpolation gave them. The same curves shape font outlines and pen tools.

Images are stored the way they are drawn, as weighted sums. Nasir Ahmed, T. Natarajan and K. R. Rao published the discrete cosine transform in 1974, and in 1992 it became the core of JPEG, which rewrites each 8 × 8 block as a sum of 64 cosine patterns and spends its bits on the coarse ones. Light is harder. Turner Whitted’s ray tracer of 1980 followed rays back from the eye and spawned new ones at every surface, for shadows, reflection and refraction. And in 1984 a Cornell group tested their radiosity method on a simple box with colored walls; built and measured, and later given the red and green walls and two white blocks shown here, the Cornell box became the scene renderers are tested on.

  • The Cornell BoxThe Cornell box as a real room: red wall left, green wall right, one ceiling light, and two white blocks tinted by the walls.
  • Barycentric InterpolationThe hello-world triangle in glowing glass: red, green and blue corners, olive, teal and purple edges, and a dim gray center.
  • The DCT BasisJPEG’s 64 cosine patterns as glazed tiles, from the flat gray tile at top left to the finest checkerboard at bottom right.
  • The Bézier CurveDe Casteljau’s construction as a brass drafting instrument: rods, rods between rods, and one bead riding a golden S-curve.
  • Recursive Ray TracingWhitted’s 1980 scene made real: a glass sphere and a chrome sphere over red and yellow checks, the glass turning them upside down.
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

Short-sleeve button-up · XS–4XL

EQUATION STRIPE

From the Turing machine to RSA, every line labeled.

Computer science keeps its results in a line each: a recurrence, a bound, a reduction, a rule. The Equation Stripe sets forty-five of them in rows, each introduced by its name in capitals, so BUSY BEAVER, MASTER THEOREM and RSA ENCRYPTION read at a glance. Together they make a working computer scientist’s commonplace book: what can be computed and how fast, how data is structured, sorted and searched, how information is coded, compressed and protected, and how pictures are drawn. Each is something a computer scientist has met on a whiteboard, in an exam or in an interview.

Twenty-seven rows carry the science of the collection’s five picture designs, all twenty-five of their elements, from the Turing machine to Whitted’s ray tracer. The other eighteen are results nobody forgets once learned: P and NP, the Cook–Levin and PCP theorems, the master theorem, Karatsuba, quicksort and the sorting lower bound, edge relaxation, PageRank, the Bloom filter, Kullback–Leibler, channel capacity, source coding, the Hamming bound, beta reduction, the Y combinator, Bayes’ theorem and RSA.

  • Turing Machineδ(q,a) = (q',a',d)
  • Busy BeaverS(4) = 107, Σ(4) = 13
  • Finite Automatonqk+1 = (2qk + bk) mod 3, q0 = 0, F = {0}
  • Game of Lifest+1 = [nt = 3] ∨ ([st = 1] ∧ [nt = 2])
  • Eight Queensqi ≠ qj, |qi − qj| ≠ |i − j| (i ≠ j)
  • Red–Black Treen ≥ 2bh − 1, h ≤ 2log2(n + 1)
Shop now · Regular price $65 Sale price $58.50

Leave your email and we’ll write the day it’s ready.

TURING MACHINEδ(q,a) = (q',a',d)·BUSY BEAVERS(4) = 107, Σ(4) = 13·FINITE AUTOMATONqk+1 = (2qk + bk) mod 3, q0 = 0, F = {0}·GAME OF LIFEst+1 = [nt = 3] ∨ ([st = 1] ∧ [nt = 2])·EIGHT QUEENSqi ≠ qj, |qi − qj| ≠ |i − j| (i ≠ j)·RED–BLACK TREEn ≥ 2bh − 1, h ≤ 2log2(n + 1)·SORTING NETWORKC(2k) = (k2 − k + 4)2k−2 − 1, D(2k) = k(k + 1)/2·SKIP LISTP(h ≥ L) = 2−(L−1), E[search] = O(log n)·HUFFMAN CODE LENGTHℓ̄ = ∑ipiℓi = 4.139·SHANNON ENTROPYH = −∑ipilog2pi = 4.117·BIG-O NOTATIONf = O(g) ⇔ f(n) ≤ cg(n) ∀n ≥ n0 (some c, n0)·HAMMING CODEp1 = d1⊕d2⊕d4, p2 = d1⊕d3⊕d4, p3 = d2⊕d3⊕d4·CONSISTENT HASHINGshard(k) = argminh(s) ≥ h(k)h(s), E[moved] = K/n·RAID 5 PARITYP = D1⊕D2⊕D3, D2 = P⊕D1⊕D3·T568B PINOUTpairs: (1,2) (3,6) (4,5) (7,8)·CORE MEMORYI/2 < Isw ≤ I·IEEE 754 FLOATx = (−1)s(1.f)2×2e−127, 0.1 → 1.6×2−4·JACQUARD LOOMcardk[j] = 1 ⇔ warp j raised in row k·RENDERING EQUATIONLo(x,ωo) = Le + ∫ΩfrLi(ωi·n)dωi·BARYCENTRIC WEIGHTSc(p) = λ1c1 + λ2c2 + λ3c3, λi = Ai/A·DE CASTELJAUPi(r) = (1 − t)Pi(r−1) + tPi+1(r−1)·JPEG DCTFuv = (CuCv/4)∑x=07∑y=07fxycos((2x + 1)uπ/16)cos((2y + 1)vπ/16)·TOWER OF HANOIT(n) = 2T(n − 1) + 1 = 2n − 1, T(8) = 255·DINING PHILOSOPHERSP0 → P1 → P2 → P3 → P4 → P0·TURING MACHINEδ(q,a) = (q',a',d)·BUSY BEAVERS(4) = 107, Σ(4) = 13·FINITE AUTOMATONqk+1 = (2qk + bk) mod 3, q0 = 0, F = {0}·GAME OF LIFEst+1 = [nt = 3] ∨ ([st = 1] ∧ [nt = 2])·EIGHT QUEENSqi ≠ qj, |qi − qj| ≠ |i − j| (i ≠ j)·RED–BLACK TREEn ≥ 2bh − 1, h ≤ 2log2(n + 1)·SORTING NETWORKC(2k) = (k2 − k + 4)2k−2 − 1, D(2k) = k(k + 1)/2·SKIP LISTP(h ≥ L) = 2−(L−1), E[search] = O(log n)·HUFFMAN CODE LENGTHℓ̄ = ∑ipiℓi = 4.139·SHANNON ENTROPYH = −∑ipilog2pi = 4.117·BIG-O NOTATIONf = O(g) ⇔ f(n) ≤ cg(n) ∀n ≥ n0 (some c, n0)·HAMMING CODEp1 = d1⊕d2⊕d4, p2 = d1⊕d3⊕d4, p3 = d2⊕d3⊕d4·CONSISTENT HASHINGshard(k) = argminh(s) ≥ h(k)h(s), E[moved] = K/n·RAID 5 PARITYP = D1⊕D2⊕D3, D2 = P⊕D1⊕D3·T568B PINOUTpairs: (1,2) (3,6) (4,5) (7,8)·CORE MEMORYI/2 < Isw ≤ I·IEEE 754 FLOATx = (−1)s(1.f)2×2e−127, 0.1 → 1.6×2−4·JACQUARD LOOMcardk[j] = 1 ⇔ warp j raised in row k·RENDERING EQUATIONLo(x,ωo) = Le + ∫ΩfrLi(ωi·n)dωi·BARYCENTRIC WEIGHTSc(p) = λ1c1 + λ2c2 + λ3c3, λi = Ai/A·DE CASTELJAUPi(r) = (1 − t)Pi(r−1) + tPi+1(r−1)·JPEG DCTFuv = (CuCv/4)∑x=07∑y=07fxycos((2x + 1)uπ/16)cos((2y + 1)vπ/16)·TOWER OF HANOIT(n) = 2T(n − 1) + 1 = 2n − 1, T(8) = 255·DINING PHILOSOPHERSP0 → P1 → P2 → P3 → P4 → P0·

The science on the shirt

What you’re wearing

Every object on the shirts, and the science behind it.

The Eight Queens

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.

The Finite Automaton

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.

The Glider Gun

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.

The Turing Machine

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.

The Towers of Hanoi

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.

The Red–Black Tree

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.

The Huffman Tree

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.

Orders of Growth

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.

The Sorting Network

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.

The Skip List

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.

The Dining Philosophers

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.

The T568B Pinout

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.

The Hamming Code

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.

Consistent Hashing

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.

RAID 5

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.

Magnetic-Core Memory

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.

0.1 in Floating Point

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.

The Jacquard Loom

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.

The Punched Card

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.

Difference Engine No. 2

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.

The Cornell Box

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.

Barycentric Interpolation

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.

The DCT Basis

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.

The Bézier Curve

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.

Recursive Ray Tracing

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.

Shop Computer Science: Wear it to work

Made to order for you · free U.S. shipping on $46+ (shirts, ties and socks) · 10% off through 30 Nov

More Computer Science designs are on the way.

Leave your email and we’ll write the day they’re ready.