algorithms

Two different things can make a numerical answer inaccurate: the problem may amplify any input perturbation, or the algorithm may introduce its own. They are separate quantities, one belongs to the problem and one to the code, and only the second is fixable. This lesson separates them and shows what follows.

Every operation is correctly rounded, yet results can be wrong in the first digit. The reason is that subtracting nearly equal numbers is exact and still catastrophic: it does not create error, it promotes error that was already there. This lesson builds that mechanism and the summation techniques that recover the lost accuracy.

The count-min sketch estimates how often an item occurred using a fixed grid of counters, and it never underestimates. This lesson builds it, states the error bound that makes it usable, shows where it is useless, and ends on the property shared by all three structures that explains why they run distributed systems.

Counting distinct items exactly needs memory proportional to the count. HyperLogLog answers the same question in a fixed twelve kilobytes, for cardinalities into the billions, by measuring an improbable event rather than storing anything. This lesson builds that idea from the leading-zeros intuition up.

A Bloom filter answers set membership using a bit array and a handful of hash functions, with no items stored anywhere. This lesson builds it, derives the sizing formula that trades memory against false positives, explains exactly why deletion is impossible, and covers the variants that buy it back.

Answering set questions exactly costs memory proportional to the data, which fails once the data does not fit. Probabilistic data structures accept a quantified error in exchange for memory that stays constant. This lesson establishes what that trade buys, and why the shape of the error matters more than its size.

A schedule says how much to trade and when. It says nothing about how each slice is sent, and that choice determines much of the realised cost. This lesson covers the standard algorithm families and what each one's benchmark actually rewards, then the placement decisions underneath: passive against aggressive, displayed against hidden, and which venue.

Ray tracing takes the opposite loop: for each pixel, find the geometry it hits. That buys visibility queries from any point in any direction, which is what shadows and reflections need. It also costs a scene-wide data structure, and the quality of that structure decides whether the renderer is usable.

A machine with a fixed number of states can recognise a surprising amount, and then hits a wall that no amount of cleverness moves. This lesson builds the finite automaton, shows that regular expressions are the same thing in different notation, and proves by counting that balanced parentheses are out of reach.

A procedure for deciding between greedy, dynamic programming, and neither. Write the recurrence, count the states, attempt the greedy proof, and read the failure. Includes the instance where greedy is optimal and off by a third depending on one word in the problem statement.

A greedy algorithm is three lines of code and a proof. This lesson covers the proof techniques that make it an algorithm rather than a heuristic: the exchange argument, greedy-stays-ahead, Huffman's merge, and the matroid theorem that says exactly when greedy is guaranteed.

Writing a dynamic program is three decisions, not a recurrence to memorise. This lesson works through choosing the state, deriving the running time from it, fixing the evaluation order, recovering the answer rather than its value, and why an O(nW) knapsack is not polynomial.

Dynamic programming and greedy algorithms both rest on a structural property the problem either has or does not have. This lesson establishes it precisely, shows a problem that lacks it, and separates the three properties that decide which technique applies.

How to move along a curved space without solving differential equations: retractions as cheap approximations to geodesics, vector transport, and the Riemannian versions of gradient descent, conjugate gradients, and trust regions.

Why local training on non-identical data pulls clients apart, how averaging their updates produces a model that suits nobody, and the control-variate fix that corrects the drift.

Belief propagation, the cavity method, and approximate message passing: how physics-derived algorithms achieve the best performance any efficient method can, and how state evolution predicts their behaviour exactly before you run them.

Why statistical physics has anything to say about algorithms: planted models with known ground truth, the large-system limit where randomness stops fluctuating, and the Bayes-optimal benchmark that makes hardness measurable.

Maximizing a submodular function is NP-hard, yet the simplest possible algorithm gets provably close to optimal. This lesson presents the greedy algorithm, the celebrated (1 - 1/e) guarantee of Nemhauser, Wolsey, and Fisher, why that bound cannot be beaten, and the lazy trick that makes greedy fast at scale.

Many selection problems share one property: each new item helps less than the last. Formalized, that property is submodularity, and it is what makes otherwise intractable problems solvable with guarantees. This lesson defines it precisely, shows the everyday examples, and explains why it is called the discrete analog of convexity.

A trie stores keys in their spelling rather than hashing them, which buys the one query a hash table cannot answer: find everything starting with this. This lesson covers the trie, the memory problem that makes it impractical, and the radix compression that fixes it and routes the internet.

A heap is the structure for when you need the smallest item repeatedly but never need the whole set sorted. This lesson builds the binary heap as an array, derives why building one costs linear rather than n log n time, and shows the top-k pattern that makes it worth knowing.

A binary search tree is elegant until sorted input turns it into a linked list. This lesson explains how balance is enforced: the rotation as the one legal repair, what red-black and AVL trees each guarantee, and why databases use B-trees with hundreds of children instead.

A hash table promises constant-time lookup, and the promise holds only because of how it handles collisions. This lesson builds one from the array up: hashing, chaining versus open addressing, why load factor is the tuning dial, and how modern tables scan sixteen slots at once.

Three ideas carry almost all production vector search. This lesson covers HNSW as a navigable small-world graph with its M and ef parameters, IVF as coarse partitioning with nprobe, and the quantization schemes that cut memory by an order of magnitude, plus how they compose into the hybrid indexes real systems actually run.

Vector search exists because exact nearest neighbour search is intractable at scale and the curse of dimensionality defeats the classical index structures. This lesson covers distance metrics and when each is right, why brute force costs what it does, why k-d trees fail above a few dozen dimensions, and the recall-latency trade that every approximate index makes.

Shor, Grover, Hamiltonian simulation, HHL — the catalog of known quantum-algorithmic speedups, what 'speedup' precisely means in each case, and the structural reasons most problems do not gain exponential advantage.

A beginner-friendly tour of Big-O: what it measures, the common growth classes, and how to spot them in your own code.