Machines and algorithms
L1: foundations
COMPFrom a gate to a running program. A NAND gate is enough to build every circuit, an adder made of gates does subtraction too, and the Little Man Computer puts that adder beside a hundred mailboxes: the program sits in the same memory as its numbers, and the machine runs whatever its program counter lands on.
L2: school
COMPEvery structure here answers one question fast and pays for it somewhere else. A Bloom filter keeps no keys at all and can still say definitely not; a trie answers the prefix questions a hash table cannot; a heap always knows its smallest key and little else. The last page asks which page to throw out of memory, where the best answer needs the future.
L3: undergraduate
COMPA stopwatch measures your laptop. Counting operations measures the algorithm. Two tools built on that one habit.
L3: undergraduate
COMPAn algorithm is right for a reason that can be stated, and wrong for one a small test can find. Each page sets a correct version beside a plausible wrong one: fourteen of the sixteen ways to write binary search fail, greedy change-giving loses on old British coins and never on US cents, Kruskal and Prim agree for a reason, and a code that corrects one flipped bit makes two flips worse.
Security
L1: foundations
COMPEach cipher here hides the letters and leaves something else showing. A substitution leaves the letter counts, a keyword cipher leaves them in columns, and a one-time pad used twice leaves the spaces. Only a random key as long as the message shows nothing at all, and then the hard part becomes getting that key to the other side, which the last two pages do in public.
L3: undergraduate
COMPTwo halves of the same problem, in the order a studio meets them. First, a key has leaked and the licence must keep working for everyone else — which turns out to cost a header that does not grow with the size of the system at all. Then the harder half: knowing whose key it was, from a copy that several subscribers built together specifically so that it names nobody.
Signals and information
L2: school
COMPA video encoder is not one algorithm but eight stages in a fixed order, and the order is not arbitrary: each stage exists because the one before it made its job possible. This tool models one of them. The chain below links to the other seven.
L3: undergraduate
COMPTwo tools that open up a large language model at the moment it chooses a word. The second literally runs on the first: the candidates it ranks are entries from the vocabulary the first one builds.
L3: undergraduate
COMPA signal is a sum of spinning arrows, and every practical way of reading them off costs something the textbook formula leaves out. A finite window smears a tone that does not fit it across every bin; a shorter window buys time and pays in pitch; an average is a filter with a shape of its own; and the last page is the reason any of it is affordable.
L3: undergraduate
COMPFour encoders you could run on paper, ordered by what each one can see that the last one could not. The fourth compresses nothing whatsoever, and it is the reason the first one works on text.
Proof, counting and games
L2: school
MATHThe birthday problem looks like a party trick and is actually the standard tool for reasoning about collisions. The second step is where computer scientists meet it again, under a different name.
Switching off a thousand devices can cost less than switching off one
A disc cannot ask who is playing it, so a revocation has to be broadcast to everybody at once. The scheme every Blu-ray uses prices that broadcast by how the broken devices are arranged in the key tree, and the size of the audience does not appear in the bound at all.
Half of written Japanese is 158 characters. The next 45% costs a thousand more.
Word frequencies follow the same lopsided law in every language anyone has checked. It makes the first stage of learning feel miraculous and the last stage feel impossible, and both feelings are the same curve.
Why sorting cannot get faster
Sorting a hundred items takes at least 525 comparisons and no future algorithm will improve on it. The proof does not examine any algorithm at all: it counts how many arrangements exist and how much a yes-or-no question can possibly tell you.
Why a language model struggles to count the letters in a word
It never sees the letters. Text is split into tokens before the model reads anything, and a great many puzzling failures follow directly from where the splits land.
No compressor can shrink every file, and the proof takes one paragraph
Lossless compression works by exploiting predictability, so a file with none of it cannot be made smaller at all. The proof is counting: nine things will not fit into eight boxes.
