invented in
Nobody was born knowing Dijkstra or hashing. Real people built each one to fix a real problem. Here they are, oldest first, each linked to its chapter's full story and sources.
Ancient Rome · print-era Europe
No single inventor — a convention that settled over centuries
Romans wrote numbers mostly by adding symbols, and they were not consistent: IIII for 4 is common, and the Colosseum's gate numbers mix IIII with XL.
the problem it solvedWriting any number with a handful of symbols — and, for software, converting both ways with one fixed table.
c. 300 BCE
Euclid of Alexandria (Elements, Book VII); the method is probably older
Euclid's Elements (c. 300 BCE), Book VII, Propositions 1–2, finds the "greatest common measure" of two numbers by repeatedly taking the smaller from the larger. Historians think Euclid collected the method rather than invented it. In 1844 Gabriel Lamé proved it never needs more than 5 × (digits of the smaller number) division steps, a result often called the start of computational complexity theory. Knuth calls it the oldest nontrivial algorithm that is still in use.
the problem it solvedFind the largest number that divides two numbers exactly — without listing all their divisors.
3rd century BCE (recorded in the 2nd century CE)
Eratosthenes of Cyrene (c. 276–194 BCE); recorded by Nicomachus of Gerasa
Eratosthenes became the third librarian at Alexandria around 240 BCE. His sieve reaches us through Nicomachus of Gerasa's Introduction to Arithmetic, an early 2nd-century CE book that credits him. Write the numbers down and strike out the multiples of each prime; what survives is prime. In modified forms it is still a working tool in number-theory research.
the problem it solvedList every prime up to n without testing each number separately.
c. 2nd century BCE (antecedent) · 1427 (general method)
Piṅgala (Chandaḥśāstra); Jamshīd al-Kāshī (Miftāḥ al-Ḥisāb)
Piṅgala's Chandaḥśāstra, a Sanskrit work on poetic metre, computes 2ⁿ — the number of n-syllable metres — recursively: if n can be halved, halve it and square the result; if not, subtract 1 and double. Jayant Shah calls this divide-and-conquer. A 2026 survey (Aydin et al.) agrees it rests on the same principle as binary exponentiation but notes Piṅgala used it only inside that counting problem; it credits al-Kāshī's Miftāḥ al-Ḥisāb (1427) with presenting square-and-multiply explicitly as a general method. Knuth's TAOCP calls the method "quite ancient".
the problem it solvedCompute a huge power — 2ⁿ metres, or aᵉ mod m with e in the billions — without multiplying e times.
2nd century BCE (Piṅgala) · 10th century CE (Halāyudha)
Piṅgala; his commentator Halāyudha; later Śrīdhara, al-Karajī, Jia Xian, Yang Hui and Blaise Pascal
Piṅgala's Chandaḥśāstra asks how many n-syllable metres have k short syllables — the binomial coefficients nCk — and scholars such as Jayant Shah and Amba Kulkarni read its terse sūtras as giving an algorithm for them. Halāyudha's 10th-century commentary reads Piṅgala's last sūtra as the Meru-prastāra ("mountain" arrangement): a triangle where each cell is the sum of the two above it. Historians differ on that reading — Albrecht Weber rejected it, and Jayant Shah agrees with Weber about Halāyudha but argues the construction can still be traced to Piṅgala. Śrīdhara (often dated c. 750 CE, though some historians place him later) gave the modern formula for nCk, and the same triangle appears with al-Karajī, Jia Xian and Yang Hui, and in Pascal's Traité du triangle arithmétique, published in 1665.
the problem it solvedCount arrangements — how many ways to choose r things from n — without listing them.
by the end of the 6th century CE
Indian mathematicians and scribes (no single inventor is known)
The decimal place-value system, where a digit's position decides its weight, grew up in India. A donation charter dated 594 CE already uses it, though some historians suspect that date was added later; the Gwalior inscription of 876 CE is the first example nobody disputes. The numerals then travelled through the Arab world — around 1030 al-Bīrūnī wrote that the Arabs used the best of the Indian figures — and on to Europe. Because each place is worth ten times the next, x % 10 is the units digit and x / 10 shifts every digit one place right.
the problem it solvedWrite any number with ten symbols, and do arithmetic column by column.
1356
Nārāyaṇa Paṇḍita (India); traced by Donald Knuth
In 1356 the Indian mathematician Nārāyaṇa Paṇḍita wrote Gaṇita Kaumudī, which gives rules for listing permutations one after another.
the problem it solvedStepping through every ordering of a list in sorted order, one step at a time, with no extra memory.
1356
Nārāyaṇa Paṇḍita (Gaṇita Kaumudī)
In 1356 the Indian mathematician Nārāyaṇa Paṇḍita wrote the Gaṇita Kaumudī.
the problem it solvedListing every arrangement exactly once, in a fixed order, so that none is missed or repeated.
1736
Leonhard Euler
The city of Königsberg had seven bridges over its river. Could you walk across every bridge exactly once?
the problem it solvedDeciding whether every connection can be walked exactly once, for any map, without trying every route.
1736; 1873
Leonhard Euler; Carl Hierholzer (reconstructed by Christian Wiener)
Euler's Königsberg paper (1736 — see the Graphs chapter) gave the degree rule for walking every bridge once, but did not prove the rule was enough.
the problem it solvedProving exactly when a walk that uses every edge once exists — and building one in time proportional to the number of edges.
1801
Carl Friedrich Gauss (Disquisitiones Arithmeticae); Pierre de Fermat and Leonhard Euler before him
Remainders are ancient, but Gauss turned them into a systematic arithmetic in Disquisitiones Arithmeticae (1801): numbers with the same remainder mod m behave the same under + and ×. Earlier, in a letter of 18 October 1640 to Frénicle de Bessy, Fermat stated that a^(p−1) leaves remainder 1 for a prime p that does not divide a; Euler published the first proof in 1736. That "little theorem" is why division works modulo a prime.
the problem it solvedCompute with numbers far too large to write down by keeping only their remainders — and still add, subtract, multiply (and, for a prime modulus, divide) correctly.
1848–1972
Max Bezzel & Franz Nauck (the puzzle); C. F. Gauss; Niklaus Wirth; Edsger W. Dijkstra
In 1848 chess composer Max Bezzel posed the eight queens puzzle in a Berlin chess magazine; in 1850 Franz Nauck published all 92 solutions.
the problem it solvedPlacing pieces under rules without trying every board — and, for Wirth and Dijkstra, showing how a correct search program can be derived step by step.
1857
Arthur Cayley (the name "tree"); no single inventor of the linked binary tree in programs
In 1857 the mathematician Arthur Cayley published "On the theory of the analytical forms called trees" in the Philosophical Magazine.
the problem it solvedRepresenting hierarchy and branching — anything where one thing splits into at most two smaller things of the same kind.
1869
Camille Jordan
In 1869 the French mathematician Camille Jordan studied trees in "Sur les assemblages de lignes".
the problem it solvedWhere to root a tree so that its farthest node is as close as possible.
1877–1879
Lewis Carroll (Charles Dodgson); later Donald Knuth
Around Christmas 1877, Lewis Carroll invented a word game he first called "Word-Links".
the problem it solvedFinding the shortest chain between two states when the connections are a rule ("change one letter"), not a list.
1882 (Trémaux's rule); 1972 (Tarjan)
Charles Pierre Trémaux, via Édouard Lucas; Robert Tarjan
In the early 1880s Édouard Lucas's Récréations mathématiques described Trémaux's rule for escaping any maze: mark each passage you use, and back up when you are stuck.
the problem it solvedGetting through any maze without walking in circles; later, solving connectivity questions in linear time.
1890s–1954
Herman Hollerith (punched-card machines) · unnamed card-sorter operators · Harold H. Seward (computer version, 1954)
Radix sorting began on punched-card machines, not computers. Hollerith's electric tabulating machines processed the 1890 US census, and Knuth calls Hollerith's sorting machine the basis of radix sorting.
the problem it solvedSorting stacks of punched cards by multi-digit keys (dates, account numbers) with a machine that could only read one column at a time.
1894 · 1909 · 1976
Paul Bachmann, Edmund Landau, Donald E. Knuth
Big-O came from number theory, not computing.
the problem it solvedComparing algorithms without depending on the computer, the language or the compiler — only on how the work grows.
1909–1917
Agner Krarup Erlang, Copenhagen Telephone Company
Nobody invented "first come, first served" — waiting lines are older than computers, and the FIFO queue in code has no single inventor.
the problem it solvedHow many lines a telephone exchange needs so that calls rarely wait or get lost — sizing any system that serves requests in arrival order.
1916–1936
Dénes Kőnig
Dénes Kőnig, a Hungarian mathematician, studied graphs whose vertices split into two sides with every edge crossing between them.
the problem it solvedMatching two groups — workers to jobs, students to slots — where every link joins one side to the other.
1924–1957
Jan Łukasiewicz; Charles L. Hamblin
Logician Jan Łukasiewicz came up with a parenthesis-free notation in 1924 (published 1929): write each operator before its operands.
the problem it solvedEvaluating arithmetic without parentheses or precedence rules: every operator simply uses the two most recent values.
1926
Otakar Borůvka (asked by Jindřich Saxel of West-Moravian Powerplants)
In winter 1925/26, Jindřich Saxel, an employee of the West-Moravian Powerplants, suggested a problem to the mathematician Otakar Borůvka from the electrification of south-west Moravia: connect a set of towns with the least total length of line.
the problem it solvedConnecting every site of a network — power lines, cables, roads — with the smallest possible total length.
1928
John von Neumann
In 1928 John von Neumann published "Zur Theorie der Gesellschaftsspiele" (usually translated "On the Theory of Games of Strategy") in Mathematische Annalen, proving the minimax theorem for two-player zero-sum games.
the problem it solvedDeciding the best move when an intelligent opponent moves in between — the value of a game under perfect play.
1930 · 1957 · 1959
Vojtěch Jarník; Robert C. Prim (Bell Labs); Edsger W. Dijkstra
In 1930 Jarník answered Borůvka's paper with a note "from a letter to O. Borůvka", describing a different method: grow one tree, always adding the shortest edge that leaves it.
the problem it solvedBuilding a minimum spanning tree by growing a single tree outward — no global sort of all edges needed.
1937–38
Claude E. Shannon
As an MIT master's student (thesis written in 1937, degree awarded in 1940), Claude Shannon showed that Boolean algebra can design relay and switching circuits.
the problem it solvedDoing arithmetic with switches: turning "add two numbers" into a circuit of on/off logic.
1945
George Pólya; UMPIRE as taught by CodePath
In How to Solve It (1945), the mathematician George Pólya turned problem solving into a checklist.
the problem it solvedFreezing in front of an unfamiliar problem: a routine always gives you a next step that needs no flash of genius.
1945–1960
Alan Turing; Friedrich L. Bauer & Klaus Samelson; Edsger W. Dijkstra
Turing's 1945 design for the ACE computer used two standard routines, BURY and UNBURY, to save and restore subroutine return addresses in a last-in, first-out list — a stack in all but name.
the problem it solvedLetting a method pause, call another method (even itself), and later resume exactly where it stopped, with its own local variables intact.
1945
John von Neumann
In 1945 John von Neumann wrote a routine for the planned EDVAC computer that merges ("meshes") two sorted sequences — part of a merge-sort program.
the problem it solvedCombining two sorted lists into one sorted list in a single pass — the step that makes merge sort O(n log n) and lets data bigger than memory be sorted in sequential passes.
1945
John von Neumann
Merge sort is one of the oldest computer algorithms: Knuth credits John von Neumann with merge sorting in 1945, for the planned EDVAC computer.
the problem it solvedSorting in a guaranteed O(n log n) using only sequential passes — which is also why it can sort data bigger than memory, one chunk at a time.
1945–1961
Konrad Zuse; Edward F. Moore; C. Y. Lee
The idea is usually traced to Konrad Zuse, whose 1945 manuscript on the Plankalkül language used it to find the connected parts of a graph — it was published only in 1972.
the problem it solvedVisiting things in order of distance from a start — so the first time you reach something, you reached it by the fewest steps.
1945
John von Neumann (EDVAC report); the EDSAC team at Cambridge
In his June 1945 "First Draft of a Report on the EDVAC", von Neumann stored a negative number through the complements of its digits, working modulo a power of two.
the problem it solvedOne adder for both addition and subtraction, and a single zero, instead of separate sign handling.
1946 · 1960
John Mauchly (first mention); D. H. Lehmer (first version for any n)
Binary search was first mentioned by John Mauchly in the 1946 Moore School Lectures, the first course on building electronic computers — as Knuth records in The Art of Computer Programming, Vol. 3.
the problem it solvedFinding an item among n sorted ones with about log₂ n comparisons instead of up to n.
1947
The Harvard Mark II team, including Grace Hopper
In 1947 engineers working on Harvard's Mark II computer found a moth stuck in the machine and taped it into their log book as the "first actual case of bug being found". The Smithsonian, which keeps that log book, notes the word was older — Thomas Edison talked about bugs in electrical circuits in the 1870s. The joke stuck because the work is real: debugging is finding where the program and your belief about it differ.
the problem it solvedA name — and later a discipline — for finding faults systematically instead of by luck.
1948 · 1970
John von Neumann and Stanislaw Ulam; John Horton Conway; popularised by Martin Gardner
In 1948 John von Neumann set out to describe a machine that could build a copy of itself.
the problem it solvedA precise model of many simple parts, one local rule and one shared clock, for studying how complex behaviour grows from simple rules.
1949
Alan Turing
In June 1949, at the Cambridge conference that opened the EDSAC computer, Turing gave a short talk, "Checking a Large Routine".
the problem it solvedChecking a long program by staring at it as a whole. Small, checkable facts about each step make bugs visible one row at a time.
1950s–1965
D. H. Lehmer or R. J. Walker (the name); Solomon W. Golomb & Leonard D. Baumert
Who named it is disputed. Golomb and Baumert (1965) say the mathematician D. H. Lehmer named it "backtrack"; Knuth (1975) credits R. J. Walker, who "aptly called" it backtracking.
the problem it solvedSearching enormous spaces of combinations on early computers without building every complete candidate first.
1950s–1977
R. J. Walker; the Soviet team that later built Kaissa; David Slate & Larry Atkin (Chess 4.x)
As Knuth tells it, R. J. Walker's 1950s n-queens program already kept the attacked columns and diagonals as bit vectors.
the problem it solvedAnswering "which squares are attacked?" for a whole board with a few word-wide operations instead of a loop over 64 squares.
1951–1959
Stephen C. Kleene; Michael O. Rabin & Dana Scott
In a 1951 RAND memo, logician Stephen Kleene studied which patterns of input a machine with a fixed, finite memory can recognise. His "regular events" are the idea behind today's regular expressions; the memo was printed in Automata Studies in 1956.
the problem it solvedDeciding, one character at a time and with a fixed amount of memory, whether input matches a pattern — and splitting it into pieces along the way.
1951–68
Stephen Kleene; Ken Thompson
In a December 1951 RAND memo (later printed in Automata Studies, 1956), Stephen Kleene asked which "events" a nerve net or finite automaton can respond to, and described them with an algebra of regular events: union, concatenation and an iterate operation (written E*F) that became today's Kleene star.
the problem it solvedDescribing a whole family of strings with a short pattern, and deciding quickly — without trying every split — whether a string belongs to it.
1952–57
Richard Bellman (RAND Corporation)
Richard Bellman studied multistage decision problems at the RAND Corporation; his 1952 PNAS paper is titled "On the Theory of Dynamic Programming", and his 1957 book Dynamic Programming spread the method.
the problem it solvedMultistage decisions — choosing a sequence of actions over time — where trying every sequence is hopeless, but each stage depends only on the state you are in.
1952–67
Richard Bellman (stages and states); Andrew Viterbi (best path per state per time step)
Bellman's dynamic programming (see the Dynamic Programming chapter) already thinks in stages and states: at each stage you are in some state, and the best future depends only on that state.
the problem it solvedChoosing the best sequence of actions when what you may do next depends on the mode you are in — holding or not, cooling down, trades used — without listing every sequence.
1953 (hashing) · 1996 (Java's contract)
Hans Peter Luhn (IBM); the designers of java.lang.Object
As Knuth records, hashing goes back to an internal IBM memo by H. P. Luhn in January 1953, which also suggested chaining colliding keys together. Java built hashing into every object: Object has both equals and hashCode, and its specification, from the first Java Language Specification (1996) to today's documentation, states the contract that equal objects must have equal hash codes. HashMap and HashSet rely on it: the hash code picks a bucket, equals confirms inside it.
the problem it solvedLet any class be a hash-table key, as long as its two methods agree on what "equal" means.
1953
Hans Peter Luhn (IBM) · Java's HashMap: Doug Lea, Josh Bloch, Arthur van Hoff, Neal Gafter
In January 1953 Hans Peter Luhn wrote an internal IBM memo: compute a number from a key's digits and put the record in that numbered bucket, so a search checks one bucket instead of the whole file. Knuth traces hashing back to this memo. Java's HashMap (JDK 1.2) follows the same plan: an array of buckets. In 2011 a public advisory showed that keys crafted to collide could slow servers down, Java included. Java 8 (2014, JEP 180) lets a crowded bucket turn into a balanced tree, so for keys that implement Comparable its worst case drops from O(n) to O(log n).
the problem it solvedFinding one record among millions by checking them one by one was too slow. Hashing jumps straight to the right bucket.
1953
Hans Peter Luhn; Gene Amdahl, Elaine M. McGraw (née Boehme), Nathaniel Rochester, Arthur Samuel (IBM); Arnold Dumey; W. Wesley Peterson
In January 1953 Hans Peter Luhn wrote an internal IBM memo that put keys into numbered buckets and chained the overflow — one of the first uses of linked lists.
the problem it solvedFinding a record by its key in about one step, instead of scanning everything or keeping the data sorted.
1954
Harold H. Seward (MIT)
In a May 1954 MIT report on sorting for business data processing (Project Whirlwind report R-232), Harold H. Seward described sorting by counting.
the problem it solvedSorting large numbers of records whose keys are small integers in linear time, on 1950s machines with very little memory.
1955–1960
Friedrich L. Bauer & Klaus Samelson
In Munich, from 1955, Bauer and Samelson wanted to translate formulas like a × (b + c) into machine code in one left-to-right pass.
the problem it solvedTranslating formulas with nested parentheses and operator precedence in one left-to-right pass, by postponing each operator until it can be applied.
1955–1959
Alfonso Shimbel; Lester R. Ford Jr.; Richard Bellman; Edward F. Moore
The method was found several times within a few years.
the problem it solvedShortest routes when some costs are negative — and a way to tell when a negative loop makes "shortest" meaningless.
1956
Allen Newell, J. C. (Cliff) Shaw and Herbert A. Simon
In 1956 Newell, Shaw and Simon were building the Logic Theory Machine, a program that searched for proofs in logic.
the problem it solvedStoring data whose size and shape you can't know in advance, without reserving big fixed blocks that overflow or sit empty.
1956–1962
E. H. Friend (1956 survey) · Kenneth E. Iverson (the name "bubble sort", 1962)
The simple sorts are older than their names.
the problem it solvedSorting small amounts of data on early machines with almost no spare memory — and, today, finishing tiny or nearly sorted ranges faster than any O(n log n) sort can.
1956 (idea) · 1959 (paper)
Edsger W. Dijkstra
In 1956 Dijkstra needed a demo for the new ARMAC computer in Amsterdam that non-mathematicians could follow: the shortest route between two Dutch cities, on a reduced map of 64 cities.
the problem it solvedThe cheapest route from one place to every other place when every link has a non-negative cost — in time only a little more than the size of the map.
1956
Joseph B. Kruskal
Probably a few months after his 1954 PhD, someone at Princeton handed Kruskal two flimsy typewritten pages in German that were "floating around" the maths department: an abstract of Borůvka's 1926 paper.
the problem it solvedA simple, provably correct way to build the shortest spanning tree — and to show it is unique when all lengths differ.
1956–1971
Joseph Kruskal; Richard Rado; David Gale; Jack Edmonds
Greedy rules were in use before anyone could say when they work. Kruskal's 1956 minimum spanning tree adds the cheapest safe edge, again and again.
the problem it solvedKnowing in advance when "always take the best remaining item" is guaranteed to be optimal, instead of hoping.
1956–57
G. B. Mathews (1890s); Richard Bellman & Stuart Dreyfus; George Dantzig; Richard Karp (1972)
The puzzle is old: its history is usually traced back to G. B. Mathews' paper "On the Partition of Numbers" (1896–97).
the problem it solvedChoosing the most valuable set of indivisible items under a weight or budget limit, without trying all 2ⁿ subsets.
1957
John Backus and the IBM FORTRAN team
Early programmers kept tables in numbered memory words and worked out every address by hand.
the problem it solvedKeeping many values of one kind under one name and reaching any of them by its number, without hand-written address arithmetic.
1957 · 1972
John Backus's IBM FORTRAN team (column order); Dennis Ritchie at Bell Labs (C, row order)
A grid has rows and columns, but memory is one long line of numbered slots. Every language must decide which cell comes next.
the problem it solvedTurning a two-dimensional table into addresses in one-dimensional memory, with one multiply and one add per lookup.
1957–1961
Edward F. Moore; C. Y. Lee
In April 1957, at a Harvard symposium on switching theory, Edward F. Moore presented "The Shortest Path Through a Maze" (printed in the 1959 proceedings).
the problem it solvedFinding the fewest-steps path through a maze or a grid, and routing connections between points in a wiring layout.
1957–1959
James E. Kelley Jr. & Morgan R. Walker (CPM); Malcolm, Roseboom, Clark & Fazar (PERT)
In 1957 duPont and Remington Rand developed the Critical-Path Method and piloted it on duPont's UNIVAC I; Kelley and Walker published it in 1959.
the problem it solvedThe earliest finish date of a project whose tasks depend on each other — and which tasks must not slip.
1958–1974
Andrei Ershov; Eiichi Goto
In 1958 Andrei Ershov, writing about how a compiler should translate arithmetic, used hashing so the compiler could spot an expression it had already built and reuse it instead of computing it again.
the problem it solvedSpotting repeated structure — the same subexpression, the same subtree — without comparing it node by node every time.
1959–1961
C. A. R. (Tony) Hoare
In 1959, as a student at Moscow State University, Tony Hoare came up with a new way to sort.
the problem it solvedSorting fast in place: no helper array and few memory moves — the reason a quicksort is still Java's default for primitive arrays.
1959–60
René de la Briandais; Edward Fredkin (who named it)
In March 1959 René de la Briandais presented "File searching using variable length keys": store keys letter by letter in a tree, so a lookup reads one letter per level.
the problem it solvedLooking up keys of different lengths — words, codes — in time that depends on the key's length, not on how many keys are stored.
1959–1962
Bernard Roy; Stephen Warshall; Robert W. Floyd
Roy (1959, in French) and Warshall (January 1962) described the same triple loop for reachability: can i reach j at all?
the problem it solvedDistances between every pair of points at once — negative edges included — with a few lines of code.
1960
Edsger W. Dijkstra
Early programs gave each subroutine one fixed block of working memory. A subroutine could not be called again before it finished, because the new call would overwrite the old one's data. In "Recursive Programming" (1960), written for ALGOL 60 compilers, Dijkstra kept each call's data on a stack instead: push a fresh area on every call, drop it on return. The JVM works the same way today: every thread has a stack of frames, and objects live on a shared heap.
the problem it solvedLet methods call each other, and themselves, without overwriting each other's local variables, and free that memory the instant a call returns.
1960
John McCarthy
McCarthy's Lisp built every program out of small linked cells, and cells that nothing pointed to any more piled up. His 1960 paper describes a reclamation cycle that starts when free storage runs out: find every cell still reachable from the program, and return the rest to the free list. Java has never had a free or delete: the JVM specification says heap objects are never explicitly deallocated, only reclaimed by a garbage collector. Since JDK 9, G1 has been HotSpot's default collector on server configurations (JEP 248).
the problem it solvedFree memory automatically and safely, so a program can neither forget to free an object nor use one after freeing it.
1960
John McCarthy (Lisp); the ALGOL 60 committee, report edited by Peter Naur
Recursion was a mathematical idea first; 1960 is when two landmark languages built it in.
the problem it solvedWriting code for nested, self-similar data — expressions, lists of lists, trees — in the same shape as the data.
1960–1979
Alan Perlis & Charles Thornton; Donald Knuth; Joseph M. Morris
In 1960 Perlis and Thornton's "threaded lists" reused empty links to point back up a structure — Knuth later credited them with the threaded tree.
the problem it solvedVisiting every node exactly once in a predictable order — with recursion, with an explicit stack, or (Morris) with almost no memory.
1960
John McCarthy
In his 1960 Lisp paper, McCarthy built all data from ordered pairs: an S-expression is a pair whose two parts are atoms or smaller S-expressions — a binary tree.
the problem it solvedComputing anything about a nested structure — equality, size, a transformed copy — with a function as short as the structure's definition.
1960–62
P. F. Windley; A. D. Booth & A. J. T. Colin; Thomas N. Hibbard — independently
Around 1960 several researchers arrived at the same idea on their own: keep keys in a tree where smaller keys go left and larger keys go right.
the problem it solvedA dictionary you can search like a sorted list, yet grow one key at a time without shifting everything after it.
1960
Maurice Pollack
In 1960 Maurice Pollack, at the Stanford Research Institute, posed the "maximum capacity" route problem in a short letter to Operations Research.
the problem it solvedChoosing a route by its worst (or weakest) link instead of its total length.
1960
Peter Wegner (first published); D. H. Lehmer (independently); made famous by Kernighan & Ritchie
Peter Wegner published the trick in 1960 in a one-page note, "A technique for counting ones in a binary computer" (Communications of the ACM).
the problem it solvedCounting the 1-bits of a word in as many steps as there are 1s, instead of one step per bit.
1960–75
Colin Mallows (patience sorting); Michael Fredman (the n log n bound)
A card game gives LIS a fast algorithm: deal each card onto the leftmost pile whose top card is not smaller; the number of piles is the LIS length.
the problem it solvedFinding the longest increasing run (gaps allowed) in O(n log n) instead of O(n²).
1961
C. A. R. (Tony) Hoare
Hoare published Algorithm 65: Find in the same July 1961 issue of Communications of the ACM as Quicksort.
the problem it solvedFinding the k-th smallest value — a median, a percentile — without sorting everything.
1961
Edsger W. Dijkstra (Mathematisch Centrum, Amsterdam)
While building an ALGOL 60 translator for the Electrologica X1 computer, Dijkstra described how to turn formulas into machine order in one left-to-right pass.
the problem it solvedEvaluating — or compiling — infix formulas with precedence and brackets in a single left-to-right pass.
1961
Peter Lucas (Vienna; his group became IBM's Vienna lab); Ned Irons is also credited
Around 1961, the people writing the first ALGOL 60 compilers found that a grammar can become code directly: one procedure per rule, calling each other — and themselves — exactly as the rules nest.
the problem it solvedTurning a grammar into a working parser by hand, with code that mirrors the rules so it is easy to check.
1962–1967
Ole-Johan Dahl and Kristen Nygaard
Dahl and Nygaard, at the Norwegian Computing Center, wanted to describe and simulate real systems. Simula I, a simulation language, and Simula 67, a general-purpose language built on ALGOL 60, introduced classes, objects and inheritance. In 2001 they received the ACM Turing Award "for ideas fundamental to the emergence of object oriented programming". Java's class, new and extends are those same three ideas.
the problem it solvedKeep each piece of state together with the only code allowed to change it, and create as many independent copies (objects) as the program needs.
1962
Thomas N. Hibbard
Inserting into a BST is easy; deleting a node with two children is not — its slot needs a value that fits between both subtrees.
the problem it solvedRemoving any key — even one with two children — while keeping every BST promise, in time proportional to the height.
1962
Georgy Adelson-Velsky & Evgenii Landis
A plain BST is fast only while it stays bushy; sorted input turns it into a chain.
the problem it solvedGuaranteeing O(log n) search, insert and delete whatever order the keys arrive in.
1962
A. B. Kahn (Westinghouse Electric Corporation, Baltimore)
In the late 1950s, big projects such as the US Navy's Polaris missile programme were planned as PERT networks: thousands of events, each waiting for others.
the problem it solvedPutting thousands of dependent events in a valid order — and noticing when the dependencies loop.
1964
J. W. J. Williams · Java's PriorityQueue: Josh Bloch and Doug Lea (Java 5, 2004)
In 1964 J. W. J. Williams published Algorithm 232: Heapsort in Communications of the ACM, and with it the binary heap. It is a tree packed into an array: every parent is ordered before its children, so the top item sits at the front, and a slot's children are found by arithmetic on its index, so no pointers are needed. Java 5 (2004) added PriorityQueue, a binary min-heap in an array: the smallest item sits at index 0, and the children of index n live at 2n + 1 and 2n + 2.
the problem it solvedRepeatedly taking the smallest item while new items keep arriving, without re-sorting everything each time.
1964
J. W. J. Williams
The binary heap arrived in June 1964, inside J. W. J. Williams's Algorithm 232: Heapsort in Communications of the ACM.
the problem it solvedTaking the smallest item again and again while new items keep arriving — O(log n) per step instead of re-sorting everything.
1964
Robert W. Floyd
Williams built his heap by inserting the items one at a time — O(n log n) for n items.
the problem it solvedTurning n unordered values into a heap in O(n) instead of O(n log n) — the first phase of heapsort and of new PriorityQueue<>(collection).
1964
J. W. J. Williams · Robert W. Floyd
Williams published Heapsort (Algorithm 232) in June 1964: build a heap, then take the extreme value out again and again.
the problem it solvedSorting with a guaranteed O(n log n) worst case and only O(1) extra memory.
1964 (analysed 1973–75)
Bernard A. Galler & Michael J. Fischer; analysis by John Hopcroft & Jeffrey Ullman, and Robert Tarjan
In 1964 Galler and Fischer published a three-page CACM paper on a compiler chore: FORTRAN's EQUIVALENCE statements say which variables share memory, and the compiler must group them.
the problem it solvedGrouping things that are declared equal pair by pair, and answering "same group?" without re-scanning everything.
1964 / 1993
Richard Durstenfeld; Preston Briggs & Linda Torczon (Rice University)
The move is old. Durstenfeld's 1964 random-permutation algorithm (CACM Algorithm 235) swaps a randomly chosen element with the last one of the not-yet-shuffled range, then shrinks the range — nothing shifts.
the problem it solvedCompilers needed many small sets drawn from a large range of numbers, with constant-time add, delete and clear, and iteration over the members only.
1965
Juris Hartmanis & Richard E. Stearns
In "On the computational complexity of algorithms" (1965), Hartmanis and Stearns classified computations by how the number of steps grows with the length of the input.
the problem it solvedSaying precisely what "fast" means: running time as a function of input size n, so algorithms can be ranked and budgeted.
1965–76
Vladimir Levenshtein; Robert Wagner & Michael Fischer; James Hunt & Douglas McIlroy
In 1965 Vladimir Levenshtein, working on error-correcting codes, measured the distance between strings by insertions, deletions and substitutions.
the problem it solvedMeasuring how different two sequences are — words, lines of code, DNA — in O(m·n) instead of trying every alignment.
1965–1974
Robert Daley & Peter Neumann (Multics); Dennis Ritchie & Ken Thompson (Unix)
In 1965 Daley and Neumann described the Multics file system as a tree hierarchy of files, where a file's path name is the chain of entry names from the root.
the problem it solvedOrganising thousands of files so that any one is found by name through a short chain of small directories, instead of one huge flat list.
1968
Donald Michie
In a 1968 Nature paper, "'Memo' Functions and Machine Learning", AI researcher Donald Michie described functions that remember their earlier results.
the problem it solvedRecursions that solve the same sub-problem again and again — exponential time turns into (number of distinct states) × (work per state).
1968
Donald R. Morrison (PATRICIA)
Fredkin's tries branch on letters; the same idea works on the bits of a key.
the problem it solvedStoring and searching keys bit by bit, so lookups cost the key's length in bits and runs of single-child nodes need not be stored.
1969–72
Ken Thompson, Dennis Ritchie and Doug McIlroy at Bell Labs (Unix)
Early Unix gave every program two ready-made files: standard input and standard output (file descriptors 0 and 1). The shell's < and > swapped them for files, so a program never needed to know where its data came from. Pipes appeared in 1972 at Doug McIlroy's suggestion, chaining one program's output into the next one's input. Online judges use exactly this: the test file becomes your stdin, and your stdout becomes a file they compare.
the problem it solvedPrograms could be combined and tested without changing their code — just by redirecting where input comes from and where output goes.
In print 1969
Robert W. Floyd (as credited by Donald E. Knuth); later Richard P. Brent
Knuth's The Art of Computer Programming, Vol. 2 (1969), gives the tortoise-and-hare idea as an exercise and credits it to Robert W. Floyd — its first known appearance in print.
the problem it solvedNoticing that a sequence repeats — and where the repeat begins — with two pointers, without storing everything you have seen.
1969–70 (found) · 1977 (published)
James H. Morris Jr., Donald E. Knuth and Vaughan R. Pratt
Summer 1969: James Morris was writing a text editor for the CDC 6400 and wanted a search that never backs up in the text file.
the problem it solvedFind a pattern in text in O(n + m) time while reading the text strictly left to right, never going back.
early 1970s · 1974
Allen Klinger; Raphael A. Finkel & Jon L. Bentley
Two early-1970s ideas share the name.
the problem it solvedFast search over two-dimensional data — points, regions, images — without scanning every cell.
1970–2005
S. K. Chang & A. Gill; Dexter Kozen & Shmuel Zaks; David Pearson
In 1970 Chang and Gill studied paying an amount with the fewest coins, and gave a test for when the simple biggest-coin-first rule is safe for a given coin set.
the problem it solvedKnowing when the cashier's rule "biggest coin first" is guaranteed to use the fewest coins, and catching coin sets where it isn't.
1971–1979
Akihiro Hashimoto & James Stevens; U. I. Gupta, D. T. Lee & J. Y.-T. Leung
Chip designers had to route many wires, each a horizontal interval, through a channel using as few tracks as possible: the same as fitting meetings into rooms.
the problem it solvedFitting every interval onto the fewest parallel resources (tracks, rooms, machines) with no clashes.
1972
Rudolf Bayer (1972) · Leo Guibas and Robert Sedgewick (1978) · Java's TreeMap: Josh Bloch and Doug Lea
A plain binary search tree is fast only while it stays bushy. Insert keys in sorted order and it becomes a chain. In 1972 Rudolf Bayer described symmetric binary B-trees, which keep search, insert and delete at O(log n). In 1978 Leo Guibas and Robert Sedgewick recast the idea with red and black colours: the red-black tree. Java's TreeMap (JDK 1.2) is a red-black tree, and its Javadoc credits Cormen, Leiserson and Rivest's Introduction to Algorithms for the algorithms.
the problem it solvedKeeping keys sorted while inserting and deleting, with a guaranteed O(log n) per operation instead of a hopeful one.
1972–1974
Robert Tarjan; John Hopcroft & Robert Tarjan
Tarjan's 1972 paper "Depth-First Search and Linear Graph Algorithms" showed that one DFS, with a "lowpoint" number per vertex, finds a graph's biconnected components — and so its articulation points — in time proportional to V + E.
the problem it solvedFinding every edge or vertex whose removal splits a graph, with a single DFS instead of one search per edge.
1972; 1978; 1981
Robert Tarjan; S. Rao Kosaraju; Micha Sharir
In a directed graph, u and v share a strongly connected component when each can reach the other.
the problem it solvedGrouping a directed graph into maximal "everyone reaches everyone" clusters in linear time, so the rest of the graph becomes a DAG.
1973–1984
Alfred Aho, John Hopcroft & Jeffrey Ullman; Dov Harel & Robert Tarjan
Aho, Hopcroft and Ullman defined the lowest common ancestor problem in 1973 (STOC; journal version 1976) and gave the first efficient algorithms.
the problem it solvedFinding where two branches of a hierarchy meet — the basis of tree distances, merges and "closest shared container" questions.
1974
Barbara Liskov (MIT) & Stephen Zilles (IBM)
In 1974 Barbara Liskov and Stephen Zilles published "Programming with Abstract Data Types" at an ACM SIGPLAN symposium.
the problem it solvedCode that reaches into a structure's fields everywhere can't change the structure without breaking. Fixing the operations first lets the inside change freely.
1975
John B. Goodenough (the exception-handling paper); Java's designers (JLS Chapter 11)
In December 1975 John Goodenough's paper in Communications of the ACM set out what exception handling in a language should look like. Java built it in from the start: when code breaks a rule, the JVM throws an exception, and control jumps to the nearest enclosing catch that can handle it, abandoning every frame in between. If nothing catches it, the thread ends and the stack trace is printed. Since JDK 15, a NullPointerException message even names what was null (JEP 358).
the problem it solvedErrors that can't be handled where they happen travel to code that can — instead of every function checking and passing error codes by hand.
1975
Glenn Manacher
Growing palindromes from their centres is folklore; the famous speed-up has a name.
the problem it solvedFinding palindromes without re-checking the same letters again and again: O(n) instead of O(n²) or O(n³).
1976
Edsger W. Dijkstra
Edsger Dijkstra used the Dutch national flag problem to teach how to derive a program from its invariant and prove it correct.
the problem it solvedGrouping three kinds of items in one pass with O(1) extra memory — the same split quicksort needs when many keys equal the pivot.
1976
Robert E. Tarjan
The second classic method comes from depth-first search: a vertex finishes only after everything it points to has finished, so the reversed finish order is a topological order.
the problem it solvedOrdering a dependency graph — and spotting which vertices sit on or lead into a cycle — with the DFS you already know.
1976
Michael Ian Shamos & Dan Hoey
In 1976 Shamos and Hoey asked: among n line segments, do any two cross? Checking every pair is O(n²).
the problem it solvedAnswering "what overlaps what" without testing every pair.
1977–1984
Ulf Grenander (posed it), Michael Shamos, Jay Kadane (linear scan); told by Jon Bentley
Ulf Grenander at Brown University met the maximum-subarray problem while working on pattern matching in digitised images; in 1977 he described it to Michael Shamos.
the problem it solvedFinding the best contiguous stretch of numbers — positive and negative mixed — in one pass instead of trying every start and end.
1977–1981
Donald E. Knuth & Michael F. Plass
Filling a line with as many words as fit, then starting the next, is the obvious method. The CSS Text specification notes that web browsers have so far used this kind of first-fit, greedy line breaking.
the problem it solvedBreaking a paragraph into lines that look even, instead of letting one bad early break spoil the lines after it.
1977
Jon Louis Bentley (Carnegie Mellon University)
In 1977 Victor Klee studied how fast you can compute the total length covered by n intervals on a line.
the problem it solvedAnswer questions about many overlapping intervals while they change — first covered length and area, later sums and minimums over any range — in O(log n) per step.
1978–1983
David P. Reed (MIT); Philip Bernstein & Nathan Goodman
In his MIT doctoral thesis, issued in 1978 as report TR-205, David Reed treated a changing object as a sequence of immutable versions, each named by the object and a pseudo-time.
the problem it solvedLetting readers see a consistent past state while writers keep changing the data, without readers and writers blocking each other.
1980
Robert S. Boyer & J Strother Moore
Boyer and Moore devised the algorithm in 1980; a University of Texas technical report followed in 1981.
the problem it solvedFinding the value that more than half the votes agree on, in one pass with constant memory — no table of counts.
1980–1985
Robert Hood & Robert Melville; Robert E. Tarjan
In a 1980 Cornell report (a journal paper in 1981), Hood and Melville showed several ways to build a queue in pure LISP, where lists can only be read from the front.
the problem it solvedA FIFO queue built only from structures that work at one end (stacks, or immutable lists in functional languages), at O(1) average cost per operation.
1983
Stephen C. Johnson & Brian W. Kernighan (in print); often attributed to Kent Beck
Trying every candidate is as old as counting — nobody invented it.
the problem it solvedOptimising — or freezing — before anything works. A slow, correct answer gives a baseline, a fallback and a target to beat.
1984
Franklin C. Crow; later Paul Viola & Michael Jones
In 1984 Franklin Crow presented summed-area tables at SIGGRAPH, to filter textures quickly in computer graphics.
the problem it solvedSumming any rectangle of a big image or table in O(1), however large the rectangle is.
1985
Robert E. Tarjan
Some operations are usually cheap but now and then very expensive — like a dynamic array that must copy everything when it fills up.
the problem it solvedGiving a fair, guaranteed cost to data structures whose rare expensive steps are paid for by many cheap ones.
1985 · 1998
Robert E. Tarjan (amortized analysis); the JDK 1.2 Collections Framework team (ArrayList)
Arrays that copy themselves into a bigger block when full are older than any name for the trick.
the problem it solvedLists whose final size nobody knows in advance, with O(1) access by index and appends that are cheap on average.
1987
Richard M. Karp and Michael O. Rabin
In March 1987 Richard Karp and Michael Rabin published "Efficient randomized pattern-matching algorithms" in the IBM Journal of Research and Development.
the problem it solvedCompare many substrings, or find a pattern, with O(1) work per position instead of O(m), using very little memory.
1989 · 1994
Boris Ryabko (1989, 1992); Peter M. Fenwick, University of Auckland (1994)
Adaptive data compression (arithmetic coding) keeps a table of how often each symbol has appeared, and for every symbol it codes it must both update the table and read a running total.
the problem it solvedKeep cumulative frequencies correct while they change on every symbol: update and prefix-sum both in O(log n), in a single array.
1994
Alexander Stepanov & Meng Lee (the names, in the C++ STL)
Searching for the first position where a condition turns true is as old as binary search itself.
the problem it solvedHandling duplicates and missing values: first and last occurrence, counts, and insert positions — all in O(log n).
1995
James Gosling and the Sun Java team
In C, an array is just a pointer to memory, and nothing stops you writing past its end. Java's October 1995 white paper made arrays real objects and promised that every access is checked against the array's bounds. The Java Language Specification still says it: all array accesses are checked at run time, and a bad index throws ArrayIndexOutOfBoundsException. Fun fact: that 1995 white paper wrote myPoints.length() for arrays — the shipped language made it a plain field, length, the same mix-up learners make today.
the problem it solvedOut-of-bounds writes in C silently corrupt memory and crash much later (the white paper calls it the "delayed-crash" syndrome). Checked arrays turn that into an immediate, named exception.
1995
James Gosling and the Sun Java team
In C a string is a char array anyone can overwrite. Java's October 1995 white paper made strings objects of two kinds: String for read-only (immutable) text and StringBuffer for text you want to change. The JLS adds the pool: equal string literals are interned so they share one object. Later changes kept the idea but changed the storage — since Java 7u6 (2012) substring copies instead of sharing the original's array, and since Java 9 (JEP 254) Latin-1 text takes 1 byte per char.
the problem it solvedText that can't change is safe to share, to cache and to use as a HashMap key — nobody can edit it behind your back.
1995
Java's designers, building on Unicode
Java made char a number from day one: the October 1995 white paper already calls it an unsigned 16-bit Unicode value, 0 to 65,535, and today's JLS defines it as a 16-bit unsigned integer holding UTF-16 code units. Unicode's Basic Latin block (U+0000–U+007F) keeps the old ASCII codes, so 'a'..'z' are the consecutive numbers 97..122 and '0'..'9' are 48..57. That is the whole trick: c - 'a' is plain subtraction, and the answer is an index.
the problem it solvedTurning letters and digits into array indexes and numbers without a lookup table or a HashMap.
1996
James Gosling, Bill Joy and Guy Steele (The Java Language Specification, first edition)
C and C++ let programs hold raw memory addresses and do arithmetic on them. Java's specification kept the idea of pointing at objects but limited what you can do with the pointer: a variable of class or array type holds a reference, and the JLS lists the few operations allowed on it, such as field access, method calls, casts and ==. Arithmetic is not one of them. The JLS also fixes how calls work: each argument's value initialises a brand-new parameter variable. So Java is pass-by-value, always; for objects, the value copied is the reference.
the problem it solvedShare big objects between methods cheaply, by copying one reference instead of the whole object, without letting code touch raw memory addresses.
1996 (fixed sizes) · 2006 (the binary search bug)
Java's designers; Joshua Bloch
Java fixed the size of every primitive on every machine: int is always 32-bit two's complement, long 64-bit, and the JLS says the integer operators never signal overflow. That keeps arithmetic fast and portable, but silent. In 2006 Joshua Bloch showed that int mid = (low + high) / 2; in the JDK's own binary search, which he had written, breaks once arrays reach about 2³⁰ elements. He reported that the bug sat unnoticed in the JDK for about nine years, and that the same bug is in the binary search Jon Bentley proved correct in Programming Pearls.
the problem it solvedThe same answer on every platform using plain hardware arithmetic, at the price of a silent wrap-around you must plan for.
1996 · 2004
Sun Microsystems' Java team (JDK 1.0 `String`); JDK 5 (`StringBuilder`)
Java 1.0 (1996) made String immutable: once created, its characters never change, so one string can be shared safely.
the problem it solvedText that is safe to share and to use as a map key — plus a cheap way to build new text piece by piece.
1996 · 2006
Java 1.0 team (Stack); Josh Bloch & Doug Lea (ArrayDeque, Java 6)
Java 1.0 shipped java.util.Stack as a subclass of Vector: every method is synchronized, and inherited methods like get(i) let code reach into the middle.
the problem it solvedA fast, unsynchronized stack and queue in one class, without Vector's locking and LIFO-breaking methods.
1997
Sun Microsystems (the JDK 1.1 Inner Classes Specification)
Java 1.0 had only top-level classes. JDK 1.1 added classes declared inside other classes: "nested top-level" classes (today's static nested classes) and inner classes, whose objects belong to an enclosing object. The specification explains that the compiler links each inner object to its outer object through an extra hidden field. That hidden link is exactly why DSA code writes static class Node.
the problem it solvedKeep helper classes (nodes, entries, iterators) next to the one class that uses them, without cluttering the top level.
1997
Sun's JDK team (JDK 1.1 readers; Scanner in J2SE 5.0)
JDK 1.1 added character streams, including BufferedReader, which reads through an 8,192-char buffer. StringTokenizer is older still (JDK 1.0); its docs now call it a legacy class, but it remains a fast way to split a line. J2SE 5.0 added Scanner, which parses tokens using regular expressions — very convenient, noticeably slower. And System.out is built with auto-flush on, so each println pushes its line out immediately.
the problem it solvedReading and writing millions of tokens without the I/O itself eating the time limit.
1997
Miguel A. Revilla, University of Valladolid (UVa Online Judge)
The UVa Online Judge in Spain opened to the public in April 1997 with a hundred problems: anyone could submit code and get an automatic verdict. Its 2008 paper splits verdicts into informed ones (AC, WA, Presentation Error) and uninformed ones (TLE, RE, compile error) — a TLE tells you nothing about whether your logic was right. From millions of submissions it also found that after five wrong answers in a row, the next submission was about four times more likely to be wrong than accepted.
the problem it solvedJudging thousands of submissions automatically and fairly, with the same hidden tests and limits for everyone.
1997 (netstrings) — the idea is older
No single inventor — Pascal dialects, ASN.1 (ITU-T X.690), D. J. Bernstein's netstrings
Pascal dialects such as Turbo Pascal stored a string's length in its first byte (index 0), so a string could hold any character — but at most 255 of them.
the problem it solvedSending several values through one stream so the reader knows exactly where each one ends — even when a value contains your separator.
1997 (popularised)
Dan Gusfield, UC Davis — Algorithms on Strings, Trees, and Sequences
Dan Gusfield's 1997 textbook Algorithms on Strings, Trees, and Sequences opens with "fundamental preprocessing".
the problem it solvedCompare every position of a string with the string's own start in O(n) total — which turns pattern search into one pass over pattern + '#' + text.
1998
Josh Bloch, Neal Gafter and John Rose (authors named in the JDK source)
JDK 1.2 shipped the Collections Framework and, with it, java.util.Arrays: static helpers so nobody has to hand-write sort, search, fill or equals for arrays again. Its javadoc still says "Since 1.2" and calls it a member of the Java Collections Framework. Today sort(int[]) is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch, and sorting objects uses a stable merge sort adapted from Tim Peters's list sort for Python (TimSort).
the problem it solvedHand-written copy, compare, fill and sort loops are where off-by-one bugs live. One tested call removes the bug and says what you mean.
1998 (GJ) · 2004 (Java 5)
Gilad Bracha, Martin Odersky, David Stoutamire and Philip Wadler (GJ); JSR 14
Before generics, a Java List held plain Objects: every get needed a cast, and a wrong cast failed only at run time. GJ ("Generic Java", OOPSLA 1998) added type parameters that the compiler checks and then erases, so existing class files kept working. JSR 14 took GJ as its basis for adding generics to Java, delivered with J2SE 5.0 in 2004.
the problem it solvedType-safe collections and algorithms, written once for every object type, without breaking existing code.
1998
Joshua Bloch (design lead) and the JDK team at Sun Microsystems
Early Java had arrays, Vector and Hashtable, with no shared interface between them. JDK 1.2 (renamed Java 2, shipped December 1998) added the Collections Framework: interfaces like List, Set and Map, plus ready-made implementations behind them. Joshua Bloch led its design. The old Vector and Hashtable were retrofitted to fit the new interfaces.
the problem it solvedEvery library invented its own containers, so code couldn't pass collections around, or swap a slow implementation for a faster one without a rewrite.
1998
Josh Bloch and Neal Gafter (ArrayList's credited authors) · Robert Tarjan (amortized analysis, 1985)
Java 1.0 already had Vector: an array that doubles when full (by default), with synchronized methods. JDK 1.2 (1998) added ArrayList, the same idea without the locking. Vector's own Javadoc now recommends ArrayList when you don't need thread safety. In JDK 17 it grows to old + (old >> 1), about 1.5×. Why is add still O(1)? Robert Tarjan's 1985 paper Amortized Computational Complexity explains the tool: average the cost over the whole sequence of operations.
the problem it solvedArrays have a fixed size, but you rarely know n in advance. Results, API responses and adjacency lists grow as you go.
1998–2000
William M. McKeeman (differential testing); Koen Claessen & John Hughes (QuickCheck)
At DIGITAL, McKeeman tested C compilers by running the same machine-generated test programs through several compilers and comparing the results.
the problem it solvedBugs that hide in inputs you would never think to write by hand.
1998 · 2014
Doug Lea, Josh Bloch, Arthur van Hoff, Neal Gafter (authors in the source); JEP 180 in JDK 8
java.util.HashMap arrived in JDK 1.2 (December 1998) with the new Collections Framework; its source lists Doug Lea, Josh Bloch, Arthur van Hoff and Neal Gafter as authors.
the problem it solvedA general-purpose map for any key with a sensible equals/hashCode — fast on average, and protected against keys that all collide.
2002
JSR 41 — spec lead Joshua Bloch
JSR 41, "A Simple Assertion Facility", went final in May 2002 and arrived with J2SE 1.4 as the assert keyword. Oracle's guide spells out the rules: assertions are disabled by default and switched on with -ea; assert expressions must not have side effects; and public methods should check their arguments with real exceptions, not asserts.
the problem it solvedWriting down what you believe is true ("left ≤ right here") so the program tells you the moment it isn't — and costs almost nothing when switched off.
2002 (Java 1.4)
Josh Bloch (author of java.util.LinkedList and LinkedHashMap)
Java 1.2 (1998) shipped LinkedList, a doubly linked list, in the new Collections Framework.
the problem it solvedO(1) lookup and O(1) reordering at the same time — exactly what an LRU cache needs to stay fast as it grows.
2002
Tim Peters (Python) · Joshua Bloch (Java port, Java 7)
In July 2002 Tim Peters replaced Python's list sort with an "adaptive stable mergesort" and described it in a text file (today's listsort.txt in CPython); it shipped with Python 2.3 and became known as TimSort.
the problem it solvedSorting real-world data — often partly sorted already — with far fewer comparisons than a plain merge sort, while staying stable.
2004
JSR 201 — spec leads Gilad Bracha and Joshua Bloch
Collections can only hold objects. Before Java 5 you wrapped every number yourself — list.add(new Integer(x)), then cast and call .intValue() to read it back. JSR 201, final in September 2004 as part of J2SE 5.0 "Tiger", added autoboxing together with enums, the enhanced for loop and static import. Since then Java converts int ↔ Integer for you: convenient, and also the reason the cost became invisible.
the problem it solvedWriting new Integer(x) and .intValue() around every collection call was noisy and easy to get wrong.
2004
Sun's JDK team (J2SE 5.0)
Java 1.0 already had a mutable StringBuffer, but its methods are synchronized for thread safety. J2SE 5.0 added StringBuilder: the same API with no synchronization, documented as the faster choice when a single thread builds the string — which is nearly always. Its internal array starts with room for 16 chars and grows to twice the old capacity plus 2 when full.
the problem it solvedBuilding text piece by piece without copying everything on every append.
2004
JSR 201 (submitted by Sun Microsystems; contacts Gilad Bracha and Joshua Bloch)
Before Java 5, constants were plain ints (static final int UP = 0): nothing stopped you passing 7 as a direction, and printing one showed a meaningless number. JSR 201 added enumerations to the language, together with autoboxing, the for-each loop and static import, in J2SE 5.0 (2004). A Java enum is a class with a fixed set of instances that can carry fields and methods.
the problem it solvedType-safe named constants: the compiler rejects anything that is not one of the listed values.
2004
The Java 5 language changes (JSR 201); Joshua Bloch led the JDK 5.0 language enhancements
Collections hold objects, so before Java 5 you wrapped every int by hand: list.add(new Integer(5)). Java 5 (2004) added autoboxing: the compiler now calls Integer.valueOf(5) for you. A fresh object for every small number would waste memory, so the Java Language Specification (§5.1.7) makes a pragmatic compromise, and Integer.valueOf always caches −128..127. Outside that range, identity is not promised.
the problem it solvedBoxing small numbers everywhere (counts, indices, flags) without creating a new object each time.
2006
Josh Bloch and Doug Lea (Java 6)
Java 1.0's Stack extends Vector, so it inherits its synchronized methods. Java 1.2's LinkedList allocates a node object for every element. Java 6 (December 2006) added the Deque interface and ArrayDeque: one circular array with a moving head and tail. Its Javadoc says it is likely faster than Stack as a stack and faster than LinkedList as a queue. Stack's own Javadoc now points you to Deque.
the problem it solvedStacks and queues need O(1) at the ends, without locking overhead or one extra object per element.
2006
Daniel Lemire (a well-known published version; we found no first inventor)
The idea — keep only the values that can still become the max — is widely taught with no name attached; we couldn't trace who first used it.
the problem it solvedThe max or min of every window of a long stream — without re-scanning the window and without waiting for future values.
2006 (Java 6)
Josh Bloch & Doug Lea (ArrayDeque); the name "deque": E. J. Schweppe, as credited by Knuth
A deque — say "deck" — is a queue that is open at both ends.
the problem it solvedOne structure that can be a stack, a queue, or both at once, with O(1) work at either end and no node object per element.
2006
Joshua Bloch
java.util.Arrays.binarySearch computed its midpoint from low + high. For arrays of more than about 2³⁰ (1.07 billion) elements, that sum can pass 2³¹ − 1 and wrap negative.
the problem it solvedA midpoint that stays correct for every array size and every value range up to Integer.MAX_VALUE.
2009
Vladimir Yaroslavskiy, with Jon Bentley and Joshua Bloch
In 2009 Vladimir Yaroslavskiy proposed a quicksort with two pivots that splits a range into three parts at once.
the problem it solvedMaking the default sort for primitive arrays faster than classic one-pivot quicksort on modern hardware.
2010
Ketan Shah, Anirban Mitra & Dhruv Matani
An LFU (least frequently used) cache evicts the key with the fewest uses. The paper notes that the best-known implementations, a min-heap plus a hash table, cost O(log n) per operation.
the problem it solvedMaking "most (or least) frequently used" as cheap as "least recently used": O(1) per access instead of O(log n).
2012
Daniel Delling, Thomas Pajor & Renato Werneck (Microsoft Research)
Picking the right vertices is an old modelling habit with no single inventor, but transit routing shows it at full scale.
the problem it solvedAnswering fewest-transfer and earliest-arrival journey queries on city-scale transit networks quickly, without Dijkstra.
2020–2021
Gavin Bierman (owner of JEP 395), reviewed and endorsed by Brian Goetz
A simple data class in Java used to need a constructor, getters, equals, hashCode and toString: many lines that hide the one line of intent and are easy to get wrong. JEP 359 previewed records in JDK 14, JEP 384 refined them in JDK 15, and JEP 395 made them final in JDK 16. Java 17, the version this course uses, has them as a standard feature.
the problem it solvedModel plain, immutable data in one line, with equals, hashCode and toString generated correctly.
Some ideas grew in many places at once, or were passed on as habits. Where the chapters found no reliable first inventor, they say so instead of guessing.
Choosing by cumulative weights (inverse-transform sampling on a discrete distribution) is folklore in probability and simulation; we found no single inventor to credit. The O(1)-per-pick alias method is credited to Alastair J. Walker (1974).
09 · Math & Numbers →Indexing an array by the value itself is programming folklore with no single inventor. Its best-known relative is counting sort: CLRS (Chapter 8 notes) reports that Knuth credits H. H. Seward with inventing counting sort in 1954.
10 · Arrays & Strings →Running totals from the left and from the right are as old as bookkeeping; there is no single inventor to credit. In interviews the technique is known from problems like Product of Array Except Self and Trapping Rain Water.
10 · Arrays & Strings →Using an array's own indices as a lookup table for values 1..n is folklore from programming puzzles and interviews; we found no single inventor to credit.
10 · Arrays & Strings →Storing grid moves as {dr, dc} pairs, and walking a spiral with four shrinking walls, are programming folklore from games and puzzles. We found no documented inventor.
11 · Matrices →The transpose is basic linear algebra. Doing a quarter turn as "transpose, then mirror each row" is programming folklore; we found no documented first use.
11 · Matrices →Reusing part of the input as scratch space is an old space-saving habit with no single inventor. Set Matrix Zeroes and Game of Life are its best-known interview forms.
11 · Matrices →Folklore: nobody is credited with inventing it. Indices that start at both ends and walk towards each other already drive the partition step of Tony Hoare's Quicksort (1961), but the interview pattern grew out of everyday practice, not one paper.
12 · Two Pointers →Folklore: compacting an array in place with one index that reads and one that writes has no single inventor we could find.
12 · Two Pointers →Running totals over the last k values are as old as moving averages in statistics; as an array technique it is programming folklore, and we found no single inventor to credit.
13 · Sliding Window →The grow-right, shrink-left loop is programming folklore, usually taught as a form of same-direction two pointers; we found no single inventor to credit.
13 · Sliding Window →Running totals are as old as account books; the technique has no single inventor to credit. Its 2D form does have a clear history — see the summed-area table.
14 · Hashing →Pairing running sums with a hash map of earlier sums is a well-known competitive-programming and interview technique; we found no single inventor to credit.
14 · Hashing →No single inventor: a dummy (sentinel) node is an old programming trick, passed down through textbooks rather than published as an algorithm.
15 · Linked Lists →No single inventor: flipping links to reverse a list is list-processing folklore, taught in textbooks rather than credited to one paper.
15 · Linked Lists →The one-pass stack for "nearest bigger / smaller value" is folklore — we found no inventor to credit. Under the name "all nearest smaller values", the problem was studied on parallel computers by Berkman, Schieber and Vishkin (Journal of Algorithms, 1993).
16 · Stacks →Ring buffers grew out of early I/O and operating-system practice. We couldn't find a reliable first inventor or date, so we don't name one.
17 · Queues →A folklore technique passed on through algorithm courses and contest write-ups. We couldn't verify a first publication or inventor, so we name none.
17 · Queues →Searching a range of possible answers with a yes/no test is the integer cousin of the bisection method from numerical analysis, and is folklore in programming contests; we found no single inventor to credit.
18 · Binary Search →A textbook argument rather than one inventor's paper: Knuth (TAOCP Vol. 3, §5.3.1) and Cormen et al. (CLRS, §8.1) both present it as a decision tree with n! leaves. We couldn't pin down who first wrote it down, so we don't name anyone.
19 · Sorting →Writing a tree as a flat sequence with a marker for every missing child is old programming folklore; we found no single inventor to credit.
21 · Traversals →Carrying context (depth, bounds, a running total) into recursive calls as parameters is as old as recursion itself; there is no single inventor to credit.
22 · Tree Recursion →The "return the best arm, record the best bend" trick is standard tree dynamic programming folklore; we found no single inventor to credit.
22 · Tree Recursion →Rebuilding a tree from its preorder and inorder sequences is a classic textbook exercise; we found no single inventor to credit.
22 · Tree Recursion →No single inventor is credited: keeping the best k in a bounded heap is folklore that grew out of priority queues and selection. The effort here goes into when and why to use it.
24 · Heaps →No single inventor is credited: splitting the data into a max-heap lower half and a min-heap upper half is a classic textbook exercise and interview pattern.
24 · Heaps →Merging many sorted runs at once is as old as sorting data on magnetic tape, and Knuth's The Art of Computer Programming, Vol. 3 treats multiway merging under external sorting — but no single inventor is credited for picking the next item with a heap.
24 · Heaps →A habit, not an invention: many greedy algorithms (Huffman coding, Dijkstra, Prim) are usually implemented by pulling the next step from a priority queue, but nobody is credited with the general pattern.
24 · Heaps →No single inventor: it is a trie's prefix check used to cut a backtracking search short — a standard combination in word-game solvers and in problems like Word Search II.
25 · Tries →No single inventor: seed-fill programs existed in several 1970s paint systems. Alvy Ray Smith's 1979 SIGGRAPH paper "Tint Fill" documents one used at NYIT and says fill algorithms had already been presented "several times before".
26 · Graphs →A standard textbook trick — one BFS from an imaginary source wired to every real source. No single inventor.
26 · Graphs →No single inventor for the white/gray/black DFS convention. The same three colours mark reachable objects in Dijkstra and colleagues' 1978 paper "On-the-fly garbage collection".
26 · Graphs →No single inventor: it is a folklore special case of Dijkstra with only two distance levels in play. Dial's 1969 bucket queue (CACM Algorithm 360) is the general version for small integer weights; the deque form spread through competitive programming.
27 · Shortest Paths →No single inventor: multiplying conversion factors along a chain is ordinary unit arithmetic. Union-find that also stores each element's ratio to its parent is a widely taught extension of Galler and Fischer's 1964 structure (see the Union-Find chapter); we found no single published origin for it.
30 · Advanced Graphs →Counting subsets and combinations is centuries-old mathematics; generating them with a start index is folklore with no single inventor.
These are proof styles, not inventions. Kleinberg and Tardos's textbook Algorithm Design (2005) uses them as section titles: "The Greedy Algorithm Stays Ahead" and "An Exchange Argument".
32 · Greedy →A classic interview technique with no single documented inventor. Jump Game II is BFS where every level is a contiguous range, so two integers replace the queue.
32 · Greedy →A folklore technique with no single inventor: it's what any "union of ranges" code does after sorting. The HTML standard even requires browsers to keep a video's buffered ranges merged this way.
33 · Intervals →No documented first inventor. Textbooks treat it as the model greedy algorithm: Cormen, Leiserson and Rivest's Introduction to Algorithms (1990) says its correctness proof follows Gavril's 1972 paper on chordal graphs, and Kleinberg & Tardos (2005) open their greedy chapter with it.
33 · Intervals →XOR comes from Boolean logic, and the "pairs cancel" trick has no single inventor — it is simply a ^ a = 0 put to work.
34 · Bits →Filling a table from the smallest subproblem up, and keeping only the rows you still read, is programming folklore with no single inventor. Its top-down twin, memoization, does have a clear origin — Donald Michie's 1968 "memo" functions, covered in the Recursion chapter.
35 · Dynamic Programming →The sign-to-subset rewrite is two lines of algebra with no inventor. Knapsack's own history (Mathews, Bellman and Dreyfus, Dantzig, Karp) is told in the Dynamic Programming chapter.
36 · DP Patterns →No documented first inventor. Kleinberg and Tardos's Algorithm Design (2005) opens its dynamic-programming chapter with it — sections 6.1 and 6.2 are both "Weighted Interval Scheduling". Its unweighted cousin, earliest end first, is the greedy algorithm in the Intervals chapter.
36 · DP Patterns →Counting identical items in a table is as old as tallying, and the HashMap-of-counts idiom has no single inventor, so we name none.
37 · Design DS →We found no single paper that introduced lazy tags on segment trees. Postponing work on a subtree until someone needs it is standard textbook and programming-contest practice, so we credit no inventor.
38 · Range Queries & Strings →