Timeline Of Algorithms

The following timeline of algorithms outlines the development of algorithms (mainly "mathematical recipes") since their inception.

Medieval Period

* Before – writing about "recipes" (on cooking, rituals, agriculture and other themes)
* c. 1700–2000 BC – Egyptians develop earliest known algorithms for multiplying two numbers
* c. 1600 BC – Babylonians develop earliest known algorithms for factorization and finding square roots
* c. 300 BC – Euclid's algorithm
* c. 200 BC – the Sieve of Eratosthenes
* 263 AD – Gaussian elimination described by Liu Hui
* 628 – Chakravala method described by Brahmagupta
* c. 820 – Al-Khawarizmi described algorithms for solving linear equations and quadratic equations in his ''Algebra''; the word ''algorithm'' comes from his name
* 825 – Al-Khawarizmi described the algorism, algorithms for using the Hindu–Arabic numeral system, in his treatise ''On the Calculation with Hindu Numerals'', which was translated into Latin as ''Algoritmi de numero Indorum'', where "Algoritmi", the translator's rendition of the author's name gave rise to the word algorithm (Latin ''algorithmus'') with a meaning "calculation method"
* c. 850 – cryptanalysis and frequency analysis algorithms developed by Al-Kindi (Alkindus) in ''A Manuscript on Deciphering Cryptographic Messages'', which contains algorithms on breaking encryptions and ciphers
* c. 1025 – Ibn al-Haytham (Alhazen), was the first mathematician to derive the formula for the sum of the fourth powers, and in turn, he develops an algorithm for determining the general formula for the sum of any integral powers, which was fundamental to the development of integral calculusVictor J. Katz (1995). "Ideas of Calculus in Islam and India", ''Mathematics Magazine'' 68 (3), pp. 163–174.
* c. 1400 – Ahmad al-Qalqashandi gives a list of ciphers in his ''Subh al-a'sha'' which include both substitution and transposition, and for the first time, a cipher with multiple substitutions for each plaintext letter; he also gives an exposition on and worked example of cryptanalysis, including the use of tables of letter frequencies and sets of letters which can not occur together in one word

Before 1940

* 1540 – Lodovico Ferrari discovered a method to find the roots of a quartic polynomial
* 1545 – Gerolamo Cardano published Cardano's method for finding the roots of a cubic polynomial
* 1614 – John Napier develops method for performing calculations using logarithms
* 1671 – Newton–Raphson method developed by Isaac Newton
* 1690 – Newton–Raphson method independently developed by Joseph Raphson
* 1706 – John Machin develops a quickly converging inverse-tangent series for π and computes π to 100 decimal places
* 1768 – Leonard Euler publishes his method for numerical integration of ordinary differential equations in problem 85 of Institutiones calculi integralis
* 1789 – Jurij Vega improves Machin's formula and computes π to 140 decimal places,

* 1805 – FFT-like algorithm known by Carl Friedrich Gauss
* 1842 – Ada Lovelace writes the first algorithm for a computing engine
* 1903 – A fast Fourier transform algorithm presented by Carle David Tolmé Runge
* 1918 - Soundex
* 1926 – Borůvka's algorithm
* 1926 – Primary decomposition algorithm presented by Grete Hermann
* 1927 – Hartree–Fock method developed for simulating a quantum many-body system in a stationary state.
* 1934 – Delaunay triangulation developed by Boris Delaunay
* 1936 – Turing machine, an abstract machine developed by Alan Turing, with others developed the modern notion of ''algorithm''.

1940s

* 1942 – A fast Fourier transform algorithm developed by G.C. Danielson and Cornelius Lanczos
* 1945 – Merge sort developed by John von Neumann
* 1947 – Simplex algorithm developed by George Dantzig

1950s

* 1952 – Huffman coding developed by David A. Huffman
* 1953 – Simulated annealing introduced by Nicholas Metropolis
* 1954 – Radix sort computer algorithm developed by Harold H. Seward
* 1964 – Box–Muller transform for fast generation of normally distributed numbers published by George Edward Pelham Box and Mervin Edgar Muller. Independently pre-discovered by Raymond E. A. C. Paley and Norbert Wiener in 1934.
* 1956 – Kruskal's algorithm developed by Joseph Kruskal
* 1956 – Ford–Fulkerson algorithm developed and published by R. Ford Jr. and D. R. Fulkerson
* 1957 – Prim's algorithm developed by Robert Prim
* 1957 – Bellman–Ford algorithm developed by Richard E. Bellman and L. R. Ford, Jr.
* 1959 – Dijkstra's algorithm developed by Edsger Dijkstra
* 1959 – Shell sort developed by Donald L. Shell
* 1959 – De Casteljau's algorithm developed by Paul de Casteljau
* 1959 – QR factorization algorithm developed independently by John G.F. Francis and Vera Kublanovskaya Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki ournal of Computational Mathematics and Mathematical Physics 1(4), pages 555–570 (1961).
* 1959 – Rabin–Scott powerset construction for converting NFA into DFA published by Michael O. Rabin and Dana Scott

1960s

* 1960 – Karatsuba multiplication
* 1961 – CRC (Cyclic redundancy check) invented by W. Wesley Peterson
* 1962 – AVL trees
* 1962 – Quicksort developed by C. A. R. Hoare
* 1962 – Bresenham's line algorithm developed by Jack E. Bresenham
* 1962 – Gale–Shapley 'stable-marriage' algorithm developed by David Gale and Lloyd Shapley
* 1964 – Heapsort developed by J. W. J. Williams
* 1964 – multigrid methods first proposed by R. P. Fedorenko
* 1965 – Cooley–Tukey algorithm rediscovered by James Cooley and John Tukey
* 1965 – Levenshtein distance developed by Vladimir Levenshtein
* 1965 – Cocke–Younger–Kasami (CYK) algorithm independently developed by Tadao Kasami
* 1965 – Buchberger's algorithm for computing Gröbner bases developed by Bruno Buchberger
* 1965 – LR parsers invented by Donald Knuth
* 1966 – Dantzig algorithm for shortest path in a graph with negative edges
* 1967 – Viterbi algorithm proposed by Andrew Viterbi
* 1967 – Cocke–Younger–Kasami (CYK) algorithm independently developed by Daniel H. Younger
* 1968 – A* graph search algorithm described by Peter Hart, Nils Nilsson, and Bertram Raphael
* 1968 – Risch algorithm for indefinite integration developed by Robert Henry Risch
* 1969 – Strassen algorithm for matrix multiplication developed by Volker Strassen

1970s

* 1970 – Dinic's algorithm for computing maximum flow in a flow network by Yefim (Chaim) A. Dinitz
* 1970 – Knuth–Bendix completion algorithm developed by Donald Knuth and Peter B. Bendix
* 1970 – BFGS method of the quasi-Newton class
* 1970 – Needleman–Wunsch algorithm published by Saul B. Needleman and Christian D. Wunsch
* 1972 – Edmonds–Karp algorithm published by Jack Edmonds and Richard Karp, essentially identical to Dinic's algorithm from 1970
* 1972 – Graham scan developed by Ronald Graham
* 1972 – Red–black trees and B-trees discovered
* 1973 – RSA encryption algorithm discovered by Clifford Cocks
* 1973 – Jarvis march algorithm developed by R. A. Jarvis
* 1973 – Hopcroft–Karp algorithm developed by John Hopcroft and Richard Karp
* 1974 – Pollard's ''p'' − 1 algorithm developed by John Pollard
* 1974 – Quadtree developed by Raphael Finkel

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases