Advanced Algorithms · People

Important People in Advanced Algorithms

The 43 people behind the algorithms and ideas in the nine chapters of the course: from Karatsuba multiplication and Huffman coding to Bellman's dynamic programming, Cook's theorem on NP-completeness, the branch-and-bound method, competitive analysis, and parallel computing.

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.

Leonardo Fibonacci

c. 1170 – c. 1250 · Italian · Pisa

Liber Abaci · 1202

With Liber Abaci (1202) he introduced the Hindu-Arabic numerals to Europe; the rabbit problem in the book produces 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 for memoization.

recurrence relationoverlapping subproblems

Pierre de Fermat

d. 1665 · French · Toulouse

Fermat's little theorem · 1640

In a 1640 letter to Frénicle de Bessy he stated the result now known as the little theorem: if n is prime and 1 < a < n, then aⁿ⁻¹ ≡ 1 (mod n). Euler gave the first published proof in 1736. The Fermat primality test checks this congruence for randomly chosen bases; if it fails, the number is certainly composite. The converse does not always hold: Carmichael numbers such as 561 = 3 · 11 · 17 satisfy the congruence for every base coprime to them. Robert Carmichael published 561 in 1910. The Miller–Rabin test closes this gap with a square-root property.

Fermat testCarmichael numbersmodular arithmetic

Leonhard Euler

1707–1783 · Swiss · St. Petersburg, Berlin

Bridges of Königsberg · 1736

In 1736 he proved that no walk crosses each of the seven bridges of Königsberg 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. An 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 appears 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; Karatsuba's method applies a similar idea to large integers.

arithmetic seriesloop counting

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

Ronald A. Fisher and Frank Yates

1890–1962 · 1902–1994 · British · Rothamsted

Fisher–Yates shuffle · 1938

In the 1938 book Statistical Tables for Biological, Agricultural and Medical Research they described how to generate a random permutation of a list by hand, with the help of a table of random numbers. Richard Durstenfeld adapted the method to computers in 1964, giving the O(n) swap-based version that Knuth popularized. Fisher is one of the founders of experimental design and of modern statistics.

Fisher–Yates shuffleuniformly distributed permutation

John von Neumann

1903–1957 · Hungarian-born American · Princeton IAS

Merge sort · 1945

In 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. With Stanisław Ulam he contributed to the development of the Monte Carlo method, and today's computer architecture bears his name.

divide and conquerstable sortingMonte Carlo

Stanisław Ulam

1909–1984 · Polish-born · USA, Los Alamos

Monte Carlo method · 1946–1949

In 1946 at Los Alamos, starting from the idea of estimating the chance of winning a game of solitaire by running random trials, he proposed the Monte Carlo method; together with von Neumann he applied it to neutron diffusion calculations on the ENIAC. The first paper to carry the method's name appeared in 1949, with Nicholas Metropolis. Estimating π with random points is the simplest example used in the course.

Monte Carlorandom sampling

George B. Dantzig

1914–2005 · American · RAND, Stanford

Simplex method · 1947

In 1947 he developed the simplex method for solving linear programs; in branch-and-bound algorithms, the bound at each node is most often computed from such an LP relaxation. In 1954, with Fulkerson and Johnson, he solved a 49-city traveling salesman problem (TSP) to optimality using cutting planes. The story that, as a student, he mistook two unsolved statistics problems for homework and solved them is also famous.

linear programmingsimplexTSP

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 one of the foundations of digital circuit design.

entropycompression bound

Derrick H. Lehmer

1905–1991 · American · UC Berkeley

Lehmer generator (1949) · the term “backtrack”

In 1949 he introduced the pseudo-random number method now known as the Lehmer generator, a multiplicative linear congruential generator x(k+1) = a · x(k) mod m. In the 1950s he used the term “backtrack” for a search that extends a partial solution and steps back when it reaches a dead end; today this approach is known as backtracking. He also did pioneering work on primality tests and calculating machines in number theory.

pseudo-random numbersbacktracking

David A. Huffman

1925–1999 · American · MIT, UC Santa Cruz

Huffman coding · 1952

As a graduate student at MIT, in Robert Fano's course, he solved the problem of finding the shortest prefix code as a term paper that took the place of the final exam, and published the result in 1952. The greedy method that repeatedly merges the two nodes of lowest frequency minimizes the expected number of bits per character and surpasses his professor's Shannon–Fano method. Huffman coding is a stage of formats such as DEFLATE and JPEG today.

Huffman codingprefix codegreedy choice

Richard Bellman

1920–1984 · American · RAND Corporation

Dynamic programming · 1950s

In the 1950s at the RAND Corporation he introduced the name “dynamic programming” and the principle of optimality for multistage decision problems: 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 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 1967 conference talk he argued that the sequential part of a program limits parallel speedup; this observation is known as Amdahl's law.

linear probingspeedupAmdahl's law

Michael O. Rabin

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

Miller–Rabin (1980) · Rabin-Karp (1987)

In 1959, with Dana Scott, he defined nondeterministic finite automata; this work earned him 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 one 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 among the pioneers of deliberately using randomness in algorithm design.

primality testrolling hashfinite automata

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. The same year he published the Find method for the k-th smallest element (today's QuickSelect); he also founded Hoare logic for program correctness and received the Turing Award in 1980.

quicksortpartitioningQuickSelect

Anatoly Karatsuba

1937–2008 · Soviet · Moscow

Karatsuba multiplication · 1960/1962

In 1960, while Kolmogorov's seminar was discussing the conjecture that multiplying two n-digit numbers requires Ω(n²) operations, he found within a week a method that uses three subproducts and runs in O(n^1.585) time; he was 23 at the time. Kolmogorov had the result published in 1962 under the names Karatsuba and Ofman. It is one of the first examples showing that divide and conquer can break an assumed lower bound.

Karatsuba multiplicationdivide and conquer

Ailsa Land and Alison Doig

1927–2021 · b. 1929 · British · London School of Economics

Branch and bound · 1960

In their 1960 Econometrica paper, written at the London School of Economics, they proposed the branch-and-bound method for solving integer linear programs: the solution space is split into branches, and a bound is computed for each branch with an LP relaxation. Branches whose bound is worse than the best known solution are pruned. This idea is still at the core of today's integer programming solvers; Doig later worked at the University of Melbourne under the name Alison Harcourt.

branch and boundLP relaxation

Michael Held and Richard M. Karp

Karp: b. 1935 · Journal of the SIAM, 1962

Dynamic programming for the traveling salesman · 1962

In their 1962 paper “A Dynamic Programming Approach to Sequencing Problems” they solved the traveling salesman problem with dynamic programming. A state consists of a set and a vertex: dp[S][i] is the shortest path that leaves the start, visits all cities in the set S, and ends at i. The algorithm runs in O(n² · 2ⁿ) time and O(n · 2ⁿ) memory; it is far faster than trying all n! tours one by one, but still exponential. Richard Bellman published the same method independently in the same year.

Held–Karptraveling salesmansubset DP

John D. C. Little, Katta G. Murty, Dura W. Sweeney, and Caroline Karel

Little: 1928–2024 · American · MIT

Branch and bound for the traveling salesman · 1963

In their paper “An Algorithm for the Traveling Salesman Problem,” published in Operations Research in 1963, they gave a branch-and-bound algorithm for the traveling salesman problem; the name “branch and bound” appears for the first time in this paper. The lower bound comes from a reduced cost matrix: the smallest entry is subtracted from every row and every column, and the sum of the subtracted values is a lower bound on the cost of every tour. The method does not require symmetry; it also works for asymmetric problems where d[i][j] ≠ d[j][i]. Little is also known for Little's law (1961) in queueing theory.

branch and boundreduced cost matrixtraveling salesman

Jack Edmonds

b. 1934 · American-born · Canada, Waterloo

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 a 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

Solomon W. Golomb

1932–2016 · American · University of Southern California

Backtrack Programming · 1965

“Backtrack Programming,” his 1965 Journal of the ACM paper with Leonard Baumert, is among the first works to describe backtracking systematically as a general search method; it shows with examples how pruning shrinks the search tree. His definition of polyominoes in 1953 inspired computer searches for puzzles and tiling problems. Golomb coding is also his contribution.

backtrackingpruning

Ronald Graham

1935–2020 · American · Bell Labs, UC San Diego

List scheduling (1966) · Graham scan (1972)

In 1966 he proved that for list scheduling, which gives each job to the first machine to become free, the makespan is at most (2 − 1/m) times the optimum; this is one of the first examples of an approximation ratio. In 1969 he showed that the LPT rule, which sorts jobs from longest to shortest, has ratio 4/3 − 1/(3m). In 1972 he published the Graham scan, which finds the convex hull of points in the plane in O(n log n) time.

list schedulingapproximation ratioconvex hull

László Bélády

1928–2021 · Hungarian-born · USA, IBM

OPT (MIN) · Belady's anomaly

In 1966 at IBM he defined the offline algorithm that evicts the page that will be needed furthest in the future and causes the fewest page faults (MIN, today OPT); online policies are compared with this ideal. With Nelson and Shedler he showed that under FIFO the number of page faults can increase when the number of frames increases (Belady's anomaly). He had emigrated to the United States in 1961.

pagingeviction policy

Michael J. Flynn

1934–2025 · American · Stanford

Flynn's taxonomy · 1966

In the paper “Very High-Speed Computing Systems,” published in the Proceedings of the IEEE in 1966, he divided computers into four classes by the number of instruction and data streams they process at the same time: SISD (single instruction, single data), SIMD (single instruction, multiple data), MISD (multiple instruction, single data), and MIMD (multiple instruction, multiple data). The classic single-core processor is SISD, vector units are SIMD, and multicore processors and clusters are MIMD. The taxonomy became the common language for describing parallel machines.

SIMDMIMDparallel architecture

Andrew Viterbi

b. 1935 · Italian-born · USA, UCLA, Qualcomm

Viterbi algorithm · 1967

In 1967 he proposed a dynamic programming algorithm for decoding convolutional codes that keeps, at each step, the best path reaching each state. This method, which finds the most likely sequence of states in hidden Markov models, is used in mobile and satellite communication, speech recognition, and bioinformatics. In 1985 he co-founded Qualcomm with Irwin Jacobs.

dynamic programmingmost likely path

Volker Strassen

b. 1936 · German · Zürich, Konstanz

Strassen's algorithm · 1969

In his 1969 paper “Gaussian Elimination is not Optimal” he split matrices into four blocks and multiplied them with seven block multiplications instead of eight, obtaining matrix multiplication in O(n^2.81) time; this was the first result showing that matrices can be multiplied faster than n³. In 1971, with Schönhage, he developed fast multiplication of very large integers, and in 1977, with Solovay, a probabilistic primality test.

Strassen's algorithmmatrix multiplication

Stephen Cook

b. 1939 · American-Canadian · University of Toronto

Cook's theorem · 1971

In his 1971 paper “The Complexity of Theorem-Proving Procedures” he showed that every problem in NP reduces to SAT in polynomial time, that is, that SAT is NP-complete. This result stated the P = NP question formally and began the theory of NP-completeness. He received the Turing Award in 1982.

NP-completeSATP = NP?

Richard M. Karp

b. 1935 · American · Berkeley

21 NP-complete problems · 1972

In 1972, starting from SAT, he showed by polynomial-time reductions that 21 problems, including 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

Leonid Levin

b. 1948 · Soviet-American · Boston University

Cook–Levin theorem · 1973

In the USSR, independently of Cook, he developed the notion of “universal problems” for search problems and published it in 1973; this is why the theorem is called the Cook–Levin theorem. For these problems he also gave a nearly optimal “universal search” algorithm. He later emigrated to the United States and has worked at Boston University since 1980.

NP-completereduction

Richard P. Brent

b. 1946 · Australian · Australian National University

Brent's theorem · 1974

In his 1974 paper “The Parallel Evaluation of General Arithmetic Expressions,” published in the Journal of the ACM, he bounded how long a computation written for many processors takes on fewer processors. In the language of work and depth, the result is Tₚ ≤ W/p + D, where W is the total work, D the depth, and p the number of processors. Read together with the lower bounds Tₚ ≥ W/p and Tₚ ≥ D, it shows that the time on p processors is at most twice the best possible. Brent is also known for Brent's method in numerical root finding (1973).

Brent's theoremworkdepth

Nicos Christofides

1942–2019 · Cypriot-British · Imperial College London

Christofides' algorithm · 1976

In 1976 he gave the algorithm that, for the TSP satisfying the triangle inequality (metric TSP), finds a tour at most 3/2 times as long as the best tour: build an MST, add a minimum perfect matching on the odd-degree vertices, and traverse the Euler tour with shortcuts. This ratio was the best known guarantee for metric TSP until 2020. Anatoliy Serdyukov reached the same result in the USSR at almost the same time.

traveling salesman problemapproximation ratio

Joseph B. (Jay) Kadane

b. 1941 · American · Carnegie Mellon

Maximum subarray · 1977

Michael Shamos described the maximum subarray problem, which Ulf Grenander had posed in 1977 for image analysis, at a seminar at Carnegie Mellon. Kadane, a statistician attending the seminar, found the O(n) algorithm that solves it in a single scan: V(i) = max(a[i], V(i−1) + a[i]) is the sum of the best subarray ending at i, and the answer is the largest of these values. The story and the algorithm became widely known through Jon Bentley's 1984 Programming Pearls column. Kadane is known for his work in Bayesian statistics.

Kadane's algorithmmaximum subarrayO(n)

Michael Garey and David S. Johnson

b. 1945 · 1945–2016 · American · Bell Labs

Computers and Intractability · 1979

Their book Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), written at Bell Labs, became the basic reference that lists hundreds of NP-complete problems and teaches reduction techniques. In 1974 Johnson carried out one of the first systematic analyses of approximation algorithms for problems such as bin packing and set cover. The view that proving a problem NP-complete justifies turning to approximation algorithms or heuristic search became established through this work.

NP-completenessapproximation algorithm

Leslie Valiant

b. 1949 · Hungarian-born · United Kingdom; USA, Harvard

#P · PAC · BSP · 2010 Turing Award

In 1979 he defined the class #P for counting problems and showed that computing the permanent is #P-complete. He proposed the PAC learning model, one of the theoretical foundations of machine learning, in 1984, and the bulk synchronous parallel (BSP) bridging model for parallel computation in 1990. He worked with Vazirani on randomized reductions and received the Turing Award in 2010.

#Pparallel modelrandomized reduction

Daniel Sleator

b. 1953 · American · Carnegie Mellon

Competitive analysis · 1985

In the 1985 paper “Amortized Efficiency of List Update and Paging Rules,” written with Tarjan, he proposed comparing an online algorithm with the best offline algorithm, which knows the future; they showed that the move-to-front (MTF) rule is 2-competitive and LRU is k-competitive. The name “competitive analysis” was coined in the 1988 paper by Karlin, Manasse, Rudolph, and Sleator. With Tarjan he also developed splay trees and link-cut trees.

competitive analysismove-to-frontpaging

Jeffrey S. Vitter

b. 1955 · American · Brown University

Reservoir sampling · 1985

In his 1985 paper “Random Sampling with a Reservoir” he analyzed methods that keep a uniform random sample of k items from a data stream of unknown length in a single pass; he named the basic method Algorithm R and developed the faster Algorithm Z. He earned his doctorate under Knuth; he is also among the pioneers of external-memory algorithms and data compression.

reservoir samplingdata stream

W. Daniel Hillis and Guy L. Steele Jr.

b. 1956 · b. 1954 · American · Thinking Machines

Parallel prefix sum · 1986

In their 1986 paper “Data Parallel Algorithms,” published in Communications of the ACM, they described data-parallel algorithms for the Connection Machine, which has thousands of processors. In the prefix sum, for d = 1, 2, 4, …, every position i ≥ d performs x[i] ← x[i − d] + x[i] at the same time, and the computation finishes in ⌈log n⌉ rounds. Because the total work is O(n log n), the method is not work-efficient; Blelloch's method does O(n) work at O(log n) depth. Hillis designed the Connection Machine; Steele is one of the designers of the Scheme language and a co-author of the Java language specification.

prefix sumdata parallelismwork efficiency

John L. Gustafson

b. 1955 · American · Communications of the ACM 31(5), 1988

Gustafson's law · 1988

In the 1988 article “Reevaluating Amdahl's Law,” written with Edwin Barsis, he questioned the assumption behind Amdahl's law. Amdahl keeps the problem size fixed, so the sequential part limits the speedup to 1/(1 − f). In practice, as the number of processors grows, larger problems are usually solved; if the problem grows with p, the scaled speedup is S = (1 − f) + f · p, which grows almost linearly with the number of processors. The same year he received the first Gordon Bell Prize.

Gustafson's lawscaled speedupAmdahl's law

Charles E. Leiserson

b. 1953 · American · MIT

Cilk · work stealing · CLRS

Introduction to Algorithms, which he wrote with Cormen, Rivest, and Stein (first edition 1990), is one of the most widely used algorithms textbooks in the world and one of the main references of this course. The Cilk language he developed at MIT uses a work-stealing scheduler with proven efficiency, in which an idle processor takes work from another processor's queue; Java's fork/join framework is based on the same idea. He also has a large share in the spread of work/span analysis.

work stealingwork / span

Guy Blelloch

present · American · Carnegie Mellon

Prefix sum (scan) · NESL

In his 1990 work “Prefix Sums and Their Applications” he treated the prefix sum (scan) as a basic building block of parallel algorithms; the up-sweep/down-sweep method that runs with O(n) work and O(log n) depth is named after him. He developed NESL, a parallel programming language based on the work–depth cost model. At Carnegie Mellon he works on parallel graph processing libraries.

prefix sumwork / span

David Karger

b. 1967 · American · Stanford, MIT

Randomized minimum cut · 1993

As a doctoral student at Stanford he published, in 1993, a minimum cut algorithm that contracts randomly chosen edges until two vertices remain. A single run finds a minimum cut with probability at least 2/(n(n − 1)); with enough repetitions the error probability becomes as small as desired. The Karger–Stein version, developed with Stein, made the method much faster.

minimum cutMonte Carlo algorithm

Vijay V. Vazirani

present · Indian-born · USA, Georgia Tech, UC Irvine

Approximation Algorithms · 2001

His book Approximation Algorithms (2001) is the standard textbook that presents approximation algorithms through shared techniques such as LP relaxation and the primal–dual scheme. With Micali he gave one of the fastest known algorithms for maximum matching in general graphs (1980). With Valiant he showed in 1986 that unique-solution SAT is also hard under randomized reductions (the Valiant–Vazirani theorem).

approximation algorithmLP relaxation

Years and contributions are based on the original publications and encyclopedic sources. “Present” marks living people whose birth year is not given in published sources. Because Fermat's birth year is disputed in the sources, only his year of death is given; for people whose life dates could not be found in reliable sources, only the year of the contribution and the journal in which it appeared are given.