Important People in Algorithms
The 46 people behind the algorithms and ideas in the eleven chapters of the course: from Euclid's algorithm and the Turing machine to Dijkstra and Kruskal, from network flow to KMP and data compression.
Each card gives the person's years, country and institution, best-known contribution and a short summary; the links lead to the slides where that contribution is covered. The cards can be filtered by chapter, searched, and sorted by year of contribution or by surname.
Euclid
GCD algorithm · Elements
In the Elements he described how to find the greatest common divisor of two numbers by repeated subtraction; today we write the same method with division and remainder. Euclid's algorithm, based on the identity gcd(a, b) = gcd(b, a mod b), is one of the oldest algorithms still in use. Because the larger number at least halves every two steps, the number of steps is bounded by O(log min(a, b)).
Al-Khwarizmi
Arithmetic with Hindu-Arabic numerals · algebra
A mathematician working at the House of Wisdom in Baghdad. His book on calculating with Hindu-Arabic numerals reached Europe in a Latin translation (Algoritmi de numero Indorum). The word “algorithm” comes from the Latinized form of his name, and the word “algebra” from the title of his work al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr wa-l-muqābala. He is the emblem of the idea of solving problems in clear, repeatable steps.
Leonardo Fibonacci
Liber Abaci · 1202
With Liber Abaci (1202) he introduced Hindu-Arabic numerals to Europe; the book's rabbit problem generates the sequence 1, 1, 2, 3, 5, 8, …. Solving the recurrence F(n) = F(n − 1) + F(n − 2) by plain recursion takes exponential time, because the same subproblems are computed again and again. This example is the best-known starting point for dynamic programming and the memoization technique.
Leonhard Euler
Bridges of Königsberg · 1736
In 1736 he proved that no walk crosses each of Königsberg's seven bridges exactly once; treating the land masses as vertices and the bridges as edges is regarded as the beginning of graph theory. He showed that such a walk requires the number of odd-degree vertices to be 0 or 2. The Euler tour, which uses every edge once, is also a step of Christofides' algorithm.
Carl Friedrich Gauss
Arithmetic series · 1 + 2 + … + n
According to a well-known story from his school years, he added the numbers from 1 to 100 in an instant by pairing terms from the two ends, arriving at n(n + 1)/2. This sum shows up every time nested loops are counted as O(n²). The trick of multiplying two complex numbers with three real multiplications instead of four is also attributed to him; the Karatsuba method applies a similar idea to large integers.
Gabriel Lamé
Number of steps of Euclid's algorithm · 1844
In 1844 he proved that the number of divisions Euclid's algorithm performs cannot exceed five times the number of decimal digits of the smaller number. He used Fibonacci numbers in the proof: the smallest input that needs a given number of divisions is a pair of consecutive Fibonacci numbers, because every quotient in these inputs is 1 and the numbers shrink as slowly as possible. The theorem is regarded as one of the earliest studies of an algorithm's worst case and is the precise form of the O(log min(a, b)) bound.
Arthur Cayley
Cayley's formula · 1889
In 1889 he published the formula showing that the complete graph on n vertices has exactly nⁿ⁻² spanning trees; Carl Wilhelm Borchardt had found the same number with a determinant in 1860. The number grows very fast: there are 16 spanning trees on 4 vertices and 100 million on 10. Finding the cheapest spanning tree by trying every tree is therefore impractical; greedy algorithms such as Kruskal's and Prim's reach the same result in polynomial time. Cayley is also one of the founders of matrix algebra and of the abstract notion of a group.
Otakar Borůvka
First MST algorithm · 1926
In 1926 he published the first minimum spanning tree (MST) algorithm, in order to build Moravia's electrical network at the lowest cost. In each round every component picks the lightest edge leaving it; since the number of components at least halves each round, O(log V) rounds suffice. Because the choices within a round are independent of one another, the method also suits parallel and distributed settings.
Alan Turing
Turing machine · 1936
In his 1936 paper “On Computable Numbers” he formalized the notion of an algorithm with the Turing machine and showed that no algorithm can solve the halting problem. Together with the result Alonzo Church obtained the same year with the lambda calculus, this definition is accepted as the meaning of “effectively computable” (the Church–Turing thesis). The classes P and NP are likewise defined with a time-bounded form of the same model.
John von Neumann
Merge sort · 1945
In the programs he wrote for the EDVAC in 1945 he described merge sort; Knuth counts this program among the first sorting programs written for a computer. A classic example of the divide-and-conquer approach, the method runs in O(n log n) time even in the worst case and is stable. He helped develop the Monte Carlo method together with Stanisław Ulam, and today's computer architecture bears his name.
Claude Shannon
Information theory · 1948
With his 1948 paper “A Mathematical Theory of Communication” he founded information theory and defined entropy as the lower bound on the average number of bits per symbol in lossless compression. The average length of a Huffman code exceeds the entropy by at most 1 bit. His 1937 master's thesis, which applied Boolean algebra to switching circuits, is also among the foundations of digital circuit design.
Richard Hamming
Hamming distance · 1950
In his 1950 paper “Error Detecting and Error Correcting Codes,” published in the Bell System Technical Journal, he introduced error-correcting codes and the measure now called Hamming distance. The Hamming distance is the number of positions at which two strings of equal length differ, and it is computed in O(n) time with a single scan; for example, the distance between “karolin” and “kathrin” is 3. It is undefined for strings of different lengths; in that case the Levenshtein distance, which also allows insertions and deletions, is used. He received the Turing Award in 1968.
Stephen C. Kleene
Regular expressions · 1951
In a 1951 RAND report (published in 1956) he defined regular expressions and showed that they describe exactly the languages recognized by finite automata (Kleene's theorem). The * operation, meaning “zero or more repetitions,” is called the Kleene star after him. Together with recursive function theory, he is one of the founders of computability theory.
David A. Huffman
Huffman coding · 1952
As a graduate student at MIT, he solved the problem of finding the shortest prefix code as a term paper that replaced the final exam in Robert Fano's course, and published the result in 1952. The greedy method of repeatedly merging the two least frequent nodes minimizes the expected number of bits per character and beats his professor's Shannon–Fano method. Huffman coding is today a stage of formats such as DEFLATE and JPEG.
Hans Peter Luhn
Distributing keys into buckets · 1953
In 1953 at IBM he proposed speeding up search by distributing keys into “buckets” with a function; this is one of the earliest known examples of hash tables and chaining. The Luhn check-digit algorithm, still used to validate credit card numbers, and keyword-in-context (KWIC) indexing are also his.
Richard Bellman
Dynamic programming · 1950s
In the 1950s at the RAND Corporation he coined the name “dynamic programming” for multistage decision problems and stated the principle of optimality: every part of an optimal solution is itself optimal for its own subproblem. In 1958 he published the single-source shortest path method that allows negative edge weights (Bellman-Ford). The phrase “curse of dimensionality” is also his.
Gene Amdahl
Linear probing (1954) · Amdahl's law (1967)
In 1954, in an assembler written for the IBM 701 together with Elaine McGraw and Arthur Samuel, he used linear probing, which moves to the next empty cell when a collision occurs. He was one of the chief architects of the IBM System/360. In a conference talk in 1967 he argued that the sequential part of a program limits parallel speedup; this observation is known as Amdahl's law.
L. R. Ford Jr. ve D. R. Fulkerson
Maximum flow · 1956
In 1956 at the RAND Corporation they published the Ford-Fulkerson method, which increases the flow until the residual network has no augmenting path, together with the max-flow min-cut theorem. In the same years Ford also gave the shortest path method that relaxes edges repeatedly, which is why that algorithm is called Bellman-Ford. Their 1962 book Flows in Networks made network flow a field of its own.
Joseph Kruskal
Kruskal's algorithm · 1956
In a short 1956 paper he gave the MST algorithm that examines the edges in order of weight and adds those that do not form a cycle; the same paper also describes the reverse-delete method. Today the cycle check is done with the union-find structure, and the algorithm runs in O(E log E) time. He also holds an important place in statistics through contributions such as multidimensional scaling.
Edward F. Moore
Shortest path through a maze (BFS) · 1957
At Bell Labs he described breadth-first search (BFS) for finding the shortest path through a maze (“The Shortest Path Through a Maze,” presented in 1957, published in 1959). The work shows that shortest paths in unweighted graphs can be found layer by layer; because of the method he gave for the weighted case, Bellman-Ford is sometimes called Bellman–Ford–Moore. The Moore machine type of finite state machine also bears his name.
Robert C. Prim
Prim's algorithm · 1957
In 1957 at Bell Labs he published the minimum spanning tree algorithm that starts from one vertex and grows the tree at each step by the lightest edge leaving it. Vojtěch Jarník had found the same method in 1930 and Dijkstra rediscovered it in 1959, which is why it is also called the Jarník–Prim algorithm. With a priority queue it runs in O(E log V) time, and its structure is very similar to Dijkstra's algorithm.
Donald L. Shell
Shell sort · 1959
In the method he published in 1959, the elements are first passed through insertion sort at wide gaps and then at progressively narrower gaps. Distant inversions are thereby fixed early, and the O(n²) behavior of insertion sort improves greatly in practice. The complexity depends on the gap sequence and remains an open question for some sequences.
Edsger W. Dijkstra
Shortest paths · 1959
By his own account he designed the shortest path algorithm in about twenty minutes in Amsterdam in 1956 and published it in 1959; the same paper independently gives Prim's method for the minimum spanning tree. Finalizing the vertex with the smallest tentative distance and relaxing its edges gives the correct result for non-negative weights and takes O((V + E) log V) time with a priority queue. He is also known for structured programming and semaphores, and received the Turing Award in 1972.
Michael O. Rabin
Miller–Rabin (1980) · Rabin-Karp (1987)
In 1959, together with Dana Scott, he defined nondeterministic finite automata; this work earned the 1976 Turing Award. In 1980 he turned Gary Miller's primality test (1976) into an unconditional probabilistic test: in the Miller–Rabin test a composite number passes a round with probability at most 1/4. With Karp he published the Rabin-Karp string matching algorithm, which uses a rolling hash, in 1987; he is one of the pioneers of using randomness deliberately in algorithm design.
C. A. R. (Tony) Hoare
Quicksort · 1959–1961
He designed quicksort in 1959–1960 as a visiting student at Moscow State University; the algorithm was published in 1961. Partitioning around a pivot and sorting the two sides recursively takes O(n log n) on average and O(n²) with bad pivots. In the same year he published the Find method for the k-th smallest element (today's QuickSelect); he founded Hoare logic for program correctness and received the Turing Award in 1980.
Edward Fredkin
Trie · 1960
In 1960 he published the idea of storing strings in a tree that shares common prefixes and named the structure “trie,” from the middle of the word “retrieval”; René de la Briandais had described the same structure a year earlier (1959). Fredkin is also known for reversible computing and the Fredkin gate, and he directed Project MAC at MIT.
Robert W. Floyd
Floyd-Warshall · 1962
In 1962 he published the algorithm that finds shortest paths between all pairs (all-pairs shortest paths) in O(V³) time; this dynamic program, which adds intermediate vertices one at a time, is known today as Floyd-Warshall. In 1964 he gave the method that builds a heap in O(n) time, and the “tortoise and hare” method for detecting cycles in lists is also attributed to him. He received the Turing Award in 1978 for his pioneering work in program verification.
Stephen Warshall
Transitive closure · 1962
In his 1962 paper “A Theorem on Boolean Matrices” he published the method that computes the transitive closure of a relation on a Boolean matrix in O(V³) time: if there is a path from i to k and from k to j, then there is also a path from i to j. Because Floyd's shortest path algorithm of the same year uses the same triple loop, the two are cited together. Bernard Roy had published a similar result in 1959.
Arthur B. Kahn
Topological sorting · 1962
In his 1962 paper “Topological Sorting of Large Networks” he gave the algorithm that finds the topological order of a directed acyclic graph by repeatedly removing vertices of in-degree zero. Vertices with in-degree 0 are placed in a queue; each vertex taken from the queue is written to the order and the in-degree of its successors is decreased by one, and a vertex whose in-degree drops to zero joins the queue. The algorithm runs in O(V + E) time. If not all vertices can be removed, the graph has a cycle, so the same method also performs cycle detection.
J. W. J. Williams
Heap sort · 1964
In 1964 he published heap sort, and the binary heap structure it rests on, in Communications of the ACM under the title “Algorithm 232: Heapsort.” Turning the array into a max-heap and repeatedly moving the root to the end requires O(n log n) time in the worst case and O(1) extra memory. In the same year Robert Floyd gave the improvement that builds the heap in O(n) time.
Jack Edmonds
Blossom algorithm (1965) · Edmonds-Karp (1972)
In his 1965 paper “Paths, Trees, and Flowers” he gave the blossom algorithm, which finds a maximum matching in general graphs in polynomial time, and argued that “efficient algorithm” should mean polynomial-time algorithm. In 1972, with Karp, he showed that the Ford-Fulkerson method runs in O(V·E²) time when augmenting paths are chosen by BFS. In 1971 he showed that the greedy algorithm is optimal exactly on matroids.
Vladimir Levenshtein
Levenshtein distance · 1965
In 1965 he defined the minimum number of insertions, deletions and substitutions needed to turn one string into another; the measure bears his name. His aim was error-correcting codes; the measure is used today in spell checking, in comparing DNA sequences and in approximate search. Computing the distance by dynamic programming in O(m·n) time (Wagner–Fischer, 1974) is the table method used in the course.
Donald E. Knuth
The Art of Computer Programming · 1968–
With the multivolume The Art of Computer Programming he turned algorithm analysis into a discipline; he popularized computing operation counts exactly and average-case analysis. In 1976 he proposed the present-day meanings of the O, Ω and Θ notations. With Morris and Pratt he published the KMP string matching algorithm (1977), developed the TeX typesetting system, and received the Turing Award in 1974.
Peter Hart, Nils Nilsson ve Bertram Raphael
A* algorithm · 1968
They published the A* algorithm in 1968 for the path planning of the Shakey robot at SRI. Raphael proposed adding the cost so far to Nilsson's heuristic search; Hart brought in the notions of admissible and consistent heuristics. A*, which proceeds by the value f = g + h, finds the shortest path with an admissible heuristic and often expands far fewer vertices than Dijkstra's algorithm.
Yefim Dinitz
Dinic's algorithm · 1970
In 1969 in Moscow he designed the maximum flow algorithm that proceeds by finding blocking flows in a level graph, and published it in 1970. In the West it became known as “Dinic's algorithm” through Shimon Even's presentation. The algorithm runs in O(V²·E) time; on unit-capacity networks and in bipartite matching it is much faster.
James H. Morris ve Vaughan Pratt
Knuth-Morris-Pratt · 1970/1977
In 1970 Morris found a matching method that never moves backward in the text by exploiting the pattern's own prefixes, and published it with Pratt in a technical report; a few weeks later Knuth reached the same algorithm independently, from automata theory. The three published the paper “Fast Pattern Matching in Strings” together in 1977. Thanks to the LPS table, the text pointer never moves backward and the search takes O(n + m) time.
Robert E. Tarjan
Strongly connected components · 1972
In 1972 he published the algorithm that finds the strongly connected components of a directed graph in linear time with a single DFS. In 1975 he proved that the union-find structure with path compression and union by rank takes nearly constant amortized time, and made amortized analysis systematic. With Sleator he developed splay trees and the analysis of online list update (1985), and with Goldberg the push–relabel method (1988); he shared the 1986 Turing Award with Hopcroft.
Richard M. Karp
21 NP-complete problems · 1972
In 1972, starting from SAT, he showed through polynomial-time reductions that 21 problems, among them clique, vertex cover, Hamiltonian cycle and knapsack, are NP-complete, revealing how widespread NP-completeness is. He developed the Edmonds-Karp algorithm with Edmonds (1972), the bipartite matching algorithm with Hopcroft (1973), and the Rabin-Karp string matching algorithm with Rabin (1987). He received the Turing Award in 1985.
John Hopcroft
Hopcroft–Karp matching · 1973
With Tarjan he showed how powerful depth-first search (DFS) is in graph algorithms; together they solved planarity testing in linear time. In 1973, with Karp, he published the algorithm that finds a maximum matching in a bipartite graph in O(E√V) time. The book on automata and formal languages he wrote with Ullman was a standard reference for many years; he shared the 1986 Turing Award with Tarjan.
Alfred V. Aho ve Margaret J. Corasick
Aho–Corasick algorithm · 1975
In their 1975 paper “Efficient String Matching: An Aid to Bibliographic Search,” published in Communications of the ACM, they gave the algorithm that searches for many patterns in a text in a single pass. The patterns are placed in a trie; each node gets a failure link pointing to the longest proper suffix to fall back to when a match breaks. The search time is linear in the text length, the total length of the patterns and the number of matches found. The algorithm is the basis of Unix's fgrep command. Aho is also among the authors of the AWK language and of the compiler books known as the “Dragon Book”; he shared the 2020 Turing Award with Jeffrey Ullman.
Robert S. Boyer ve J Strother Moore
Boyer-Moore · 1977
In 1977 they published the algorithm that compares the pattern from right to left and makes large jumps in the text with the bad character and good suffix rules; with long patterns most text characters are never examined. In 1980 Horspool gave a simpler version that uses only the bad character rule. The two also developed the Boyer–Moore theorem prover (an ancestor of ACL2) and the majority vote algorithm.
Abraham Lempel ve Jacob Ziv
LZ77 · LZ78
At the Technion they published LZ77 in 1977, which refers back to earlier repetitions within a sliding window, and LZ78 in 1978, which collects the phrases seen so far in a dictionary. In 1984 Terry Welch simplified LZ78 to obtain LZW; the GIF format uses LZW, while DEFLATE, used by ZIP and PNG, combines LZ77 with Huffman coding. These methods are the basis of “universal” compression, which needs no probability table in advance.
S. Rao Kosaraju
Kosaraju's algorithm · 1978
In 1978 he proposed the method that finds the strongly connected components of a directed graph with two DFS passes but did not publish it; Micha Sharir found the same algorithm independently and published it in 1981. The first DFS produces the finishing order of the vertices. The second DFS runs on the graph with its edges reversed and starts its searches in decreasing order of finishing times; each tree of this DFS is a strongly connected component. With adjacency lists the time is O(V + E). It is easier to understand than Tarjan's single-DFS method, but traverses the graph twice.
Jon Bentley
Divide-and-conquer recurrences · 1980
With Haken and Saxe he published in 1980 a general method for solving divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n); the master theorem became widespread through this work. With Yao he gave in 1976 a nearly optimal method for unbounded search, which is the basis of exponential search. He introduced the k-d tree in 1975 and brought efficient programming to a wide audience with his Programming Pearls columns.
Udi Manber ve Gene Myers
Suffix array · 1990
In 1990 (journal version 1993) they introduced the suffix array, which uses far less memory than the suffix tree, and gave the method that sorts the suffixes in O(n log n) time by doubling the prefix length in each round. Myers later contributed to the development of BLAST and to the sequencing of the human genome; Manber worked on search technologies at Yahoo!, Amazon and Google.
Michael Burrows ve David Wheeler
Burrows–Wheeler transform · 1994
Burrows and Wheeler published the transform Wheeler had found in 1983 as research report 124 of the DEC Systems Research Center in 1994. The last column of the sorted rotations of a string gathers similar characters together and is reversible; the bzip2 compressor and FM-index-based DNA alignment tools rely on this transform. Earlier, at Cambridge, Wheeler had developed one of the first forms of the subroutine call for the EDSAC.
No names match the search and filter.
Dates and contributions are based on the original publications and encyclopedic sources. “Living” marks people who are alive and whose year of birth is not given in published sources. For people whose years of life could not be found in reliable sources, only the year of the contribution and the journal of publication are given.