Algorithms · People

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

c. 300 BCE · Ancient Greek · Alexandria

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)).

GCDterminationlogarithmic number of steps

Al-Khwarizmi

c. 780 – c. 850 · Baghdad · House of Wisdom

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.

origin of the word “algorithm”step-by-step method

Leonardo Fibonacci

c. 1170 – c. 1250 · Italian · Pisa

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.

recurrence relationoverlapping subproblems

Leonhard Euler

1707–1783 · Swiss · St. Petersburg, Berlin

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.

graph theoryEuler tour

Carl Friedrich Gauss

1777–1855 · German · Göttingen

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.

arithmetic seriescounting loop iterations

Gabriel Lamé

1795–1870 · French · Paris

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.

Lamé's theoremEuclid's algorithmFibonacci numbers

Arthur Cayley

1821–1895 · British · Cambridge

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.

Cayley's formulanumber of spanning treescomplete graph

Otakar Borůvka

1899–1995 · Czech · Brno

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.

minimum spanning treecomponent

Alan Turing

1912–1954 · British · Cambridge, Manchester

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.

computabilityhalting problemChurch–Turing thesis

John von Neumann

1903–1957 · Hungarian-born American · Princeton IAS

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.

divide and conquerstable sortingMonte Carlo

Claude Shannon

1916–2001 · American · Bell Labs, MIT

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.

entropycompression limit

Richard Hamming

1915–1998 · American · Bell Labs

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.

Hamming distanceerror-correcting codestring similarity

Stephen C. Kleene

1909–1994 · American · University of Wisconsin

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.

regular expressionKleene star

David A. Huffman

1925–1999 · American · MIT, UC Santa Cruz

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.

Huffman codingprefix codegreedy choice

Hans Peter Luhn

1896–1964 · German-born American · IBM

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.

hash tablechaining

Richard Bellman

1920–1984 · American · RAND Corporation

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.

dynamic programmingoptimal substructureBellman-Ford

Gene Amdahl

1922–2015 · American · IBM

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.

linear probingspeedupAmdahl's law

L. R. Ford Jr. ve D. R. Fulkerson

1927–2017 · 1924–1976 · American · RAND Corporation

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.

Ford-Fulkersonaugmenting pathminimum cut

Joseph Kruskal

1928–2010 · American · Princeton, Bell Labs

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.

Kruskal's algorithmunion-findreverse-delete

Edward F. Moore

1925–2003 · American · Bell Labs

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.

BFSMoore machine

Robert C. Prim

1921–2021 · American · Bell Labs

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.

Prim's algorithmcut property

Donald L. Shell

1924–2015 · American · General Electric

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.

Shell sortinversion

Edsger W. Dijkstra

1930–2002 · Dutch · Amsterdam, Eindhoven; Austin, USA

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.

Dijkstra's algorithmrelaxationpriority queue

Michael O. Rabin

b. 1931 · Israeli · Hebrew University of Jerusalem; Harvard

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.

primality testrolling hashfinite automaton

C. A. R. (Tony) Hoare

1934–2026 · British · Oxford

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.

quicksortpartitioningQuickSelect

Edward Fredkin

1934–2023 · American · MIT, Carnegie Mellon

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.

trieprefix query

Robert W. Floyd

1936–2001 · American · Carnegie Mellon, Stanford

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.

all-pairs shortest pathsheap construction

Stephen Warshall

1935–2006 · American

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.

transitive closureadjacency matrix

Arthur B. Kahn

Communications of the ACM 5(11), 1962

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.

topological sortingin-degreeDAG

J. W. J. Williams

1930–2012 · British-Canadian

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.

heapin-place sorting

Jack Edmonds

b. 1934 · American-born · Waterloo, Canada

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.

Edmonds-Karppolynomial timematroid

Vladimir Levenshtein

1935–2017 · Soviet-Russian · Keldysh Institute of Applied Mathematics

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.

edit distanceDP table

Donald E. Knuth

b. 1938 · American · Stanford

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.

algorithm analysisasymptotic notationKMP

Peter Hart, Nils Nilsson ve Bertram Raphael

Nilsson: 1933–2019 · American · Stanford Research Institute (SRI)

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.

A* algorithmadmissible heuristic

Yefim Dinitz

living · Sovyet-Israeli · Ben-Gurion University

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.

level graphblocking flow

James H. Morris ve Vaughan Pratt

b. 1941 · b. 1944 · American · Berkeley, Stanford (Pratt born in Australia)

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.

KMPLPS tableprefix

Robert E. Tarjan

b. 1948 · American · Princeton

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.

DFSunion-findamortized analysis

Richard M. Karp

b. 1935 · American · Berkeley

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.

NP-completereductionRabin-Karp

John Hopcroft

b. 1939 · American · Cornell

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.

DFSbipartite matching

Alfred V. Aho ve Margaret J. Corasick

Aho: b. 1941 · Bell Labs

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.

multi-pattern searchfailure linktrie

Robert S. Boyer ve J Strother Moore

Boyer: b. 1946 · American · University of Texas at Austin

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.

bad character rulegood suffix rule

Abraham Lempel ve Jacob Ziv

1936–2023 · 1931–2023 · Israeli · Technion

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.

dictionary-based compressionLZW

S. Rao Kosaraju

living · Indian-born American · Johns Hopkins

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.

strongly connected componentstwo DFSreversed graph

Jon Bentley

b. 1953 · American · Carnegie Mellon, Bell Labs

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.

master theoremexponential search

Udi Manber ve Gene Myers

living · b. 1953 · American · University of Arizona

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.

suffix arrayprefix doubling

Michael Burrows ve David Wheeler

b. 1963 · 1927–2004 · British · Cambridge; DEC SRC, USA

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.

BWTcompression

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.