The Algorithms That Are Still Running

Euclid described this method for finding the greatest common divisor of two integers in his Elements around 300 BC, making it among the oldest algorithms still in common use today.

Attributed to the third-century BC mathematician Eratosthenes of Cyrene, this method finds every prime up to a limit by marking off the multiples of each prime in turn, starting from 2.

The foundational idea appears in Isaac Newton's own writings from 1669 to 1671, but Joseph Raphson developed the iterative formula used today, repeatedly following a function's tangent line to a closer estimate of its root.

David Huffman devised this method in 1951 as a doctoral student at MIT, building a binary tree from the bottom up so the most frequent symbols get the shortest codes; it is still a standard building block inside ZIP, JPEG and MP3 files.

Joseph Kruskal's 1956 method finds a minimum spanning tree by sorting every edge by weight and adding each one in turn as long as it does not close a cycle, tracked efficiently with a disjoint-set structure.

Named for Richard Bellman and Lester Ford Jr., this algorithm relaxes every edge in a graph repeatedly; it runs slower than Dijkstra's algorithm but is the one to reach for when a graph can have negative edge weights, since it can also detect a negative-weight cycle.

Robert Floyd's 1962 dynamic-programming method computes the shortest path between every pair of vertices in a weighted graph at once, running in cubic time regardless of how many edges the graph has.

Popularized in its modern form in 1965 by James Cooley and John Tukey, though the underlying idea traces back to an unpublished 1805 method by Carl Friedrich Gauss, this transform cut the cost of reading a signal's frequency content from a squared cost down to n log n.

Peter Hart, Nils Nilsson and Bertram Raphael published this pathfinding algorithm in 1968; it combines the cost already traveled with an estimate of the remaining distance, guaranteeing the shortest path whenever that estimate never overstates the true remaining distance.

Larry Page and Sergey Brin developed this algorithm at Stanford in 1996 and published it in 1998, the same year they founded Google; it ranks web pages by treating each hyperlink as a vote of confidence, so a page's importance depends on both the quantity and the quality of the pages linking to it.