Editing Timeline of algorithms

{{short description|None}}

The following '''timeline of algorithms''' outlines the development of [[algorithm]]s (mainly "mathematical recipes") since their inception.

==Antiquity==
* Before – [[writing]] about "[[recipes]]" (on [[cooking]], [[ritual]]s, [[agriculture]] and other themes)
* c. 1700–2000 BC – Egyptians develop earliest known algorithms for [[Ancient Egyptian multiplication|multiplying]] two numbers
* c. 1600 BC – [[Babylonia]]ns develop earliest known algorithms for [[factorization]] and finding [[square root]]s
* c. 300 BC – [[Euclidean algorithm|Euclid's algorithm]]
* c. 200 BC – the [[Sieve of Eratosthenes]]
* 263 AD – [[Gaussian elimination]] described by [[Liu Hui]]

==Medieval Period==
* 628 – [[Chakravala method]] described by [[Brahmagupta]]
* c. 820 – [[Al-Khawarizmi]] described algorithms for solving [[linear equation]]s and [[quadratic equation]]s in his ''[[The Compendious Book on Calculation by Completion and Balancing|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 [[Latin translations of the 12th century|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 [[encryption]]s and [[cipher]]s<ref>[[Simon Singh]], ''[[The Code Book]]'', pp. 14–20</ref>
* c. 1025 – [[Ibn al-Haytham]] (Alhazen), was the first mathematician to derive the formula for the sum of the fourth [[Exponentiation|powers]], and in turn, he develops an algorithm for determining the general formula for the sum of any [[integral]] powers<ref name=Katz>Victor J. Katz (1995). "Ideas of Calculus in Islam and India", ''Mathematics Magazine'' '''68''' (3), pp. 163–174.</ref>
* c. 1400 – [[Ahmad al-Qalqashandi]] gives a list of [[cipher]]s in his ''Subh al-a'sha'' which include both [[Substitution cipher|substitution]] and [[Transposition cipher|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 function|quartic polynomial]]
* 1545 – [[Gerolamo Cardano]] published Cardano's method for finding the roots of a [[Cubic function|cubic polynomial]]
* 1614 – [[John Napier]] develops method for performing calculations using [[logarithm]]s
* 1671 – [[Newton's method|Newton–Raphson method]] developed by [[Isaac Newton]]
* 1690 – [[Newton's method|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 – [[Leonhard Euler]] publishes his method for numerical integration of ordinary differential equations in problem 85 of Institutiones calculi integralis<ref>{{cite web |last1=Bruce |first1=Ian |title=Euler's Institutionum Calculi Integralis |url=http://www.17centurymaths.com/contents/integralcalculusvol1.htm |website=www.17centurymaths.com |access-date=17 May 2023 |archive-url=https://web.archive.org/web/20110201051037/http://www.17centurymaths.com/contents/integralcalculusvol1.htm |archive-date=February 1, 2011 |language=en |date=June 29, 2010 |url-status=live}}</ref>
* 1789 – [[Jurij Vega]] improves Machin's formula and computes π to 140 decimal places,
<!-- FFT?? 1965 -- * [[1805]] - [[Cooley–Tukey FFT algorithm|Cooley–Tukey algorithm]] known by [[Carl Friedrich Gauss]] -->
* 1805 – [[Cooley–Tukey FFT algorithm#History|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]]<ref>{{cite book|editor1-last=Ciliberto|editor1-first=Ciro|editor2-last=Hirzebruch|editor2-first=Friedrich|editor3-last=Miranda|editor3-first=Rick|editor4-last=Teicher|editor4-first=Mina|editor4-link= Mina Teicher |title=Applications of Algebraic Geometry to Coding Theory, Physics and Computation|date=2001|publisher=Springer Netherlands|location=Dordrecht|isbn=978-94-010-1011-5|url=https://www.springer.com/us/book/9781402000041|language=en}}</ref>
* 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 [[Turing machine#Models equivalent to the Turing machine model|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==
* 1950 – [[Hamming code|Hamming codes]] developed by [[Richard Hamming]] 
* 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]] [[QR algorithm|algorithm]] developed independently by [[John G.F. Francis]] and [[Vera Kublanovskaya]]<ref>{{cite journal | last1 = Francis | first1 = J.G.F. | year = 1961 | title = The QR Transformation, I | journal = The Computer Journal | volume = 4 | issue = 3| pages = 265–271 | doi=10.1093/comjnl/4.3.265| doi-access = free }}</ref><ref>{{cite journal | last1 = Kublanovskaya | first1 = Vera N. | year = 1961 | title = On some algorithms for the solution of the complete eigenvalue problem | journal = USSR Computational Mathematics and Mathematical Physics | volume = 1 | issue = 3| pages = 637–657 | doi = 10.1016/0041-5553(63)90168-X }} Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki [Journal of Computational Mathematics and Mathematical Physics], 1(4), pages 555–570 (1961).</ref>
* 1959 – [[Powerset construction|Rabin–Scott powerset construction]] for converting [[Nondeterministic finite automaton|NFA]] into [[Deterministic finite automaton|DFA]] published by [[Michael O. Rabin]] and [[Dana Scott]]

==1960s==
* 1960 – [[Karatsuba multiplication]]
* 1961 – [[Cyclic redundancy check|CRC (Cyclic redundancy check)]] invented by [[W. Wesley Peterson]]
* 1962 – [[AVL tree]]s
* 1962 – [[Quicksort]] developed by [[C. A. R. Hoare]]
* 1962 – [[Bresenham's line algorithm]] developed by [[Jack E. Bresenham]]
* 1962 – [[Stable marriage problem|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 FFT algorithm|Cooley–Tukey algorithm]] rediscovered by [[James Cooley]] and [[John Tukey]]
* 1965 – [[Levenshtein distance]] developed by [[Vladimir Levenshtein]]
* 1965 – [[CYK algorithm|Cocke–Younger–Kasami (CYK) algorithm]] independently developed by [[Tadao Kasami]]
* 1965 – [[Buchberger's algorithm]] for computing [[Gröbner basis|Gröbner bases]] developed by [[Bruno Buchberger]]
* 1965 – [[LR parser]]s invented by [[Donald Knuth]]
* 1966 – [[Dantzig algorithm]] for shortest path in a graph with negative edges
* 1967 – [[Viterbi algorithm]] proposed by [[Andrew Viterbi]]
* 1967 – [[CYK algorithm|Cocke–Younger–Kasami (CYK) algorithm]] independently developed by [[Daniel H. Younger]]
* 1968 – [[A* search algorithm|A* graph search algorithm]] described by [[Peter E. Hart|Peter Hart]], [[Nils Nilsson (researcher)|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 method|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 tree]]s and [[B-tree]]s discovered
* 1973 – [[RSA (algorithm)|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|Pollard's ''p''&nbsp;−&nbsp;1 algorithm]] developed by [[John Pollard (mathematician)|John Pollard]]
* 1974 – [[Quadtree]] developed by [[Raphael Finkel]] and [[J.L. Bentley]]
* 1975 – [[Genetic algorithm]]s popularized by [[John Henry Holland|John Holland]]
* 1975 – [[Pollard's rho algorithm]] developed by [[John Pollard (mathematician)|John Pollard]]
* 1975 – [[Aho–Corasick string matching algorithm]] developed by [[Alfred V. Aho]] and [[Margaret J. Corasick]]
* 1975 – [[Cylindrical algebraic decomposition]] developed by [[George E. Collins]]
* 1976 – [[Salamin–Brent algorithm]] independently discovered by [[Eugene Salamin (mathematician)|Eugene Salamin]] and [[Richard Brent (scientist)|Richard Brent]]
* 1976 – [[Knuth–Morris–Pratt algorithm]] developed by [[Donald Knuth]] and [[Vaughan Pratt]] and independently by [[J. H. Morris]]
* 1977 – [[Boyer–Moore string-search algorithm]] for searching the occurrence of a string into another string.
* 1977 – [[RSA (algorithm)|RSA]] encryption algorithm rediscovered by [[Ron Rivest]], [[Adi Shamir]], and [[Len Adleman]]
* 1977 – [[LZ77]] algorithm developed by [[Abraham Lempel]] and [[Jacob Ziv]]
* 1977 – [[multigrid methods]] developed independently by [[Achi Brandt]] and [[Wolfgang Hackbusch]]
* 1978 – [[LZ78]] algorithm developed from [[LZ77]] by [[Abraham Lempel]] and [[Jacob Ziv]]
* 1978 – [[Bruun's FFT algorithm|Bruun's algorithm]] proposed for powers of two by [[Georg Bruun]]
* 1979 – Khachiyan's [[ellipsoid method]] developed by [[Leonid Khachiyan]]
* 1979 – [[ID3 algorithm|ID3]] decision tree algorithm developed by [[Ross Quinlan]]

==1980s==
* 1980 – [[Cycle detection#Brent.27s algorithm|Brent's Algorithm]] for cycle detection [[Richard P. Brent|Richard P. Brendt]]
* 1981 – [[Quadratic sieve]] developed by [[Carl Pomerance]]
* 1981 – [[Smith–Waterman algorithm]] developed by [[Temple F. Smith]] and [[Michael S. Waterman]]
* 1983 – [[Simulated annealing]] developed by [[S. Kirkpatrick]], [[C. D. Gelatt]] and [[M. P. Vecchi]]
* 1983 – [[Classification and regression tree]] (CART) algorithm developed by [[Leo Breiman]], ''et al.''
* 1984 – [[Lempel–Ziv–Welch|LZW]] algorithm developed from [[LZ78]] by [[Terry Welch]]
* 1984 – [[Karmarkar's interior-point algorithm]] developed by [[Narendra Karmarkar]]
* 1984 – [[ACORN PRNG]] discovered by Roy Wikramaratna and used privately 
* 1985 – [[Simulated annealing]] independently developed by [[V. Cerny]]
* 1985 – [[Car–Parrinello molecular dynamics]] developed by [[Roberto Car]] and [[Michele Parrinello]]
* 1985 – [[Splay tree]]s discovered by [[Daniel Dominic Sleator|Sleator]] and [[Robert Endre Tarjan|Tarjan]]
* 1986 – [[Blum Blum Shub]] proposed by [[Lenore Blum|L. Blum]], [[Manuel Blum|M. Blum]], and [[Michael Shub|M. Shub]]
* 1986 – [[Push–relabel maximum flow algorithm|Push relabel maximum flow algorithm]] by Andrew Goldberg and Robert Tarjan
* 1986 – [[Barnes–Hut simulation|Barnes–Hut tree method]] developed by [[Josh Barnes]] and [[Piet Hut]] for fast approximate simulation of [[n-body problem]]s
* 1987 – [[Fast multipole method]] developed by [[Leslie Greengard]] and [[Vladimir Rokhlin (American scientist)|Vladimir Rokhlin]]
* 1988 – [[Special number field sieve]] developed by [[John Pollard (mathematician)|John Pollard]]
* 1989 – [[ACORN PRNG]] published by Roy Wikramaratna
* 1989 – [[Paxos (computer science)|Paxos protocol]] developed by [[Leslie Lamport]]
* 1989 – [[Skip list]] discovered by [[William Pugh (computer_scientist)|William Pugh]]

==1990s==
* 1990 – [[General number field sieve]] developed from [[Special number field sieve|SNFS]] by [[Carl Pomerance]], [[Joe Buhler]], [[Hendrik Lenstra]], and [[Leonard Adleman]]
* 1990 – [[Coppersmith–Winograd algorithm]] developed by [[Don Coppersmith]] and [[Shmuel Winograd]]
* 1990 – [[BLAST (biotechnology)|BLAST algorithm]] developed by [[Stephen Altschul]], [[Warren Gish]], [[Webb Miller]], [[Eugene Myers]], and [[David J. Lipman]] from [[National Institutes of Health]]
* 1991 – [[Lock-free and wait-free algorithms|Wait-free synchronization]] developed by [[Maurice Herlihy]]
* 1992 – [[Deutsch–Jozsa algorithm]] proposed by [[D. Deutsch]] and [[Richard Jozsa]]
* 1992 – [[C4.5 algorithm]], a descendant of [[ID3 algorithm|ID3]] decision tree algorithm, was developed by [[Ross Quinlan]]
* 1993 – [[Apriori algorithm]] developed by Rakesh Agrawal and Ramakrishnan Srikant
* 1993 – [[Karger's algorithm]] to compute the minimum cut of a connected graph by David Karger
* 1994 – [[Shor's algorithm]] developed by [[Peter Shor]]
* 1994 – [[Burrows–Wheeler transform]] developed by [[Michael Burrows (computer scientist)|Michael Burrows]] and [[David Wheeler (computer scientist)|David Wheeler]]
* 1994 – [[Bootstrap aggregating]] (bagging) developed by [[Leo Breiman]]
* 1995 – [[AdaBoost]] algorithm, the first practical boosting algorithm, was introduced by [[Yoav Freund]] and [[Robert Schapire]]
* 1995 – soft-margin [[support vector machine]] algorithm was published by [[Vladimir Vapnik]] and [[Corinna Cortes]]. It adds a soft-margin idea to the 1992 algorithm by Boser, Nguyon, Vapnik, and is the algorithm that people usually refer to when saying SVM
* 1995 – [[Ukkonen's algorithm]] for construction of suffix trees
* 1996 – [[Bruun's FFT algorithm|Bruun's algorithm]] generalized to arbitrary even composite sizes by [[H. Murakami]]
* 1996 – [[Grover's algorithm]] developed by [[Lov K. Grover]]
* 1996 – [[RIPEMD-160]] developed by [[Hans Dobbertin]], [[Antoon Bosselaers]], and [[Bart Preneel]]
* 1997 – [[Mersenne Twister]] a pseudo random number generator developed by [[Makoto Matsumoto (mathematician)|Makoto Matsumoto]] and [[Tajuki Nishimura]]
* 1998 – [[PageRank]] algorithm was published by [[Larry Page]]
* 1998 – [[rsync algorithm]] developed by [[Andrew Tridgell]]
* 1999 – [[gradient boosting]] algorithm developed by [[Jerome H. Friedman]]
* 1999 – [[Yarrow algorithm]] designed by [[Bruce Schneier]], [[John Kelsey (cryptanalyst)|John Kelsey]], and [[Niels Ferguson]]

==2000s==
* 2000 – [[HITS algorithm|Hyperlink-induced topic search]] a hyperlink analysis algorithm developed by Jon Kleinberg
* 2001 – [[Lempel–Ziv–Markov chain algorithm]] for compression developed by [[Igor Pavlov (programmer)|Igor Pavlov]]
* 2001 – [[Viola–Jones object detection framework|Viola–Jones]] algorithm for real-time face detection was developed by Paul Viola and Michael Jones.
* 2001 – [[Distributed hash table|DHT (Distributed hash table)]] is invented by multiple people from academia and application systems
* 2001 – [[BitTorrent]] a first fully decentralized peer-to-peer file distribution system is published
* 2001 – [[LOBPCG]] Locally Optimal Block Preconditioned Conjugate Gradient method finding extreme eigenvalues of symmetric eigenvalue problems by [[Andrei Knyazev (mathematician)|Andrew Knyazev]] 
* 2002 – [[AKS primality test]] developed by [[Manindra Agrawal]], [[Neeraj Kayal]] and [[Nitin Saxena]]
* 2002 – [[Girvan–Newman algorithm]] to detect communities in complex systems
* 2002 – [[Packrat parser]] developed for generating a parser that parses [[Parsing expression grammar|PEG (Parsing expression grammar)]] in linear time parsing developed by [[Bryan Ford]]
* 2009 – [[Bitcoin]] a first trust-less decentralized cryptocurrency system is published

==2010s==
* 2013 – [[Raft (computer science)|Raft consensus protocol]] published by [[Diego Ongaro]] and [[John Ousterhout]]
* 2015 – YOLO (“[[You Only Look Once]]”) is an effective real-time object recognition algorithm, first described by [[Joseph Redmon]] et al.<ref>{{Cite web |date=19 December 2023 |title=YOLO: Real-Time Object Detection |url=https://pjreddie.com/darknet/yolo/ |access-date=19 December 2023 |archive-url=https://web.archive.org/web/20231219001012/https://pjreddie.com/darknet/yolo/ |archive-date=19 December 2023 }}</ref><ref>{{Cite web |date=19 December 2023 |title=Understanding a Real-Time Object Detection Network: You Only Look Once (YOLOv1) |url=https://pyimagesearch.com/2022/04/11/understanding-a-real-time-object-detection-network-you-only-look-once-yolov1/ |access-date=20 December 2023 |archive-url=https://web.archive.org/web/20231220194202/https://pyimagesearch.com/2022/04/11/understanding-a-real-time-object-detection-network-you-only-look-once-yolov1/ |archive-date=20 December 2023 }}</ref><ref>{{Cite web |date=20 December 2023 |title=how to use darknet to train your own neural network |url=https://www.surfactants.net/how-to-use-darknet-to-train-your-own-neural-network/ |access-date=20 December 2023 |archive-url=https://web.archive.org/web/20231220203408/https://www.surfactants.net/how-to-use-darknet-to-train-your-own-neural-network/ |archive-date=20 December 2023 }}</ref><ref>{{Cite web |date=20 December 2023 |title=How computers learn to recognize objects instantly |url=https://www.ted.com/talks/joseph_redmon_how_computers_learn_to_recognize_objects_instantly |access-date=20 December 2023 |archive-url=https://web.archive.org/web/20231220204643/https://www.ted.com/talks/joseph_redmon_how_computers_learn_to_recognize_objects_instantly |archive-date=20 December 2023 }}</ref><ref name="Dr Kumar Gaurav - Amit Doegar 2021 1" >{{Cite web |date=20 December 2023 |title=Darknet: The Open Source Framework for Deep Neural Networks |url=https://www.opensourceforu.com/2021/04/darknet-the-open-source-framework-for-deep-neural-networks/ |access-date=20 December 2023 |archive-url=https://web.archive.org/web/20231220210732/https://www.opensourceforu.com/2021/04/darknet-the-open-source-framework-for-deep-neural-networks/ |archive-date=20 December 2023 }}</ref>

==References==
{{Reflist}}

{{Timelines of computing}}
{{History of mathematics}}
{{DEFAULTSORT:Timeline Of Algorithms}}
[[Category:Algorithms]]
[[Category:Computing timelines|Algorithms]]
[[Category:Mathematics timelines|Algorithms]]