Know Your History: The Origin of Algorithms

An algorithm is a precise, step-by-step recipe for solving a problem. A data structure is a way of arranging information so that a recipe can use it quickly, like the difference between a pile of loose papers and a filing cabinet. This course teaches the classic recipes and arrangements, and each one was invented because someone ran into a wall: not enough memory, not enough time, or too much data. Knowing the wall makes the idea much easier to remember.

Imagine a printed phone book with one million names in alphabetical order. You could start at page one and read every entry until you find the name, which takes up to a million looks. You could open the book in the middle, see whether your name comes before or after that point, throw away the half you do not need, and repeat. Or, if the book came with a magic formula that turned any name into a page number, you could jump straight to the right page. Same book, same person searching, very different effort.

• -Reading every entry is a linear search: simple, but the work grows in step with the data.
• -Halving the book each time is binary search. It needs the names in order, and rewards you with about 20 looks for a million names.
• -The magic formula is a hash function, and a book organized around it is a hash table: roughly one look however big it gets.

None of this needed a faster computer. Choosing a better recipe made a 50,000-fold difference on its own, since a million looks became twenty. That is why computer scientists describe the cost of an algorithm with Big-O notation, which says how the amount of work grows as the data grows. You will learn it properly in a later chapter. For now, "a million looks versus twenty" is the whole idea.

In 1956 Edsger Dijkstra worked out how to find the shortest route between two cities on a map, famously in about twenty minutes at a café, without pencil and paper. It is still how mapping software thinks about routes. In the 1960s Donald Knuth began The Art of Computer Programming and gave the field a way to compare algorithms by counting how the work grows with the input, the idea behind Big-O. The hash table, the magic formula from the phone book, also took shape in this period, with IBM engineer Hans Peter Luhn describing the idea in the 1950s.

Computers have a small amount of fast memory and a large amount of slow memory. A cache keeps the data you are likely to need again in the fast part. When the cache is full, which entry do you throw out? IBM researchers studied this question in the 1960s and 70s. A simple rule called LRU, Least Recently Used, drops whatever has gone longest without being touched. It works well because data used recently tends to be used again soon. Its cousin LFU, Least Frequently Used, drops the entry used least often. Both are everywhere today, from CPUs to browsers to databases such as Redis.

Sometimes remembering everything costs too much memory. In 1970 Burton Bloom invented the Bloom filter, a compact structure that answers "have I seen this before?" using a small fraction of the memory a full list would need. The trade-off is that it can sometimes say yes when the answer is no, a false alarm, but it never says no when the answer is yes. Think of a doorman with a rough guest list: he may let a stranger in by mistake, but he never turns away a real guest.

As networks grew, servers needed a way to say "not so fast". A token bucket gives each client a bucket that refills at a steady rate. Every request spends a token, and when the bucket is empty the request waits or is rejected. A sliding window instead counts the requests from the last few seconds. These rate limiters stop one noisy client from starving everyone else.

Two people who have never met need to talk privately across a network that anyone can listen to. In 1976 Whitfield Diffie and Martin Hellman showed how two strangers can agree on a shared secret in the open. In 1977 the RSA algorithm gave us public-key encryption, with one key you can publish and one you keep. Cryptographic hash functions such as SHA turn any data into a short fingerprint that is practically impossible to fake. Together these ideas protect every HTTPS connection.

Once programs ran on many machines, a new question appeared: how do machines that can crash, and whose clocks disagree, agree on what happened and in what order? Vector clocks, from the late 1980s, track which event could have caused which. Paxos, by Leslie Lamport, and later Raft let a group of machines agree on one sequence of decisions even when some of them fail. They keep databases and cluster managers consistent.

You will build most of these yourself. Caches and consistent hashing come in the caching tier of the Forge Lab, rate limiters in the concurrency tier, RSA and hashing in the security tier, and vector clocks and quorums in the distributed systems tier.

The Forge Chronicles below tell these stories at greater length, with the papers, the napkin sketches and the mathematical insights behind them. Open any chapter that caught your interest. None of it is needed to continue, but it gives every later algorithm a story to attach to.