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

- 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^{ [1] } - 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 calculus
^{ [2] } - 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

- 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
^{ [3] } - 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
^{ [4] } - 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*.

- 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

- 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
^{ [5] }^{ [6] } - 1959 – Rabin–Scott powerset construction for converting NFA into DFA published by Michael O. Rabin and Dana Scott

- 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

- 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 and J.L. Bentley
- 1975 – Genetic algorithms popularized by John Holland
- 1975 – Pollard's rho algorithm developed by 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 and 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 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 algorithm proposed for powers of two by Georg Bruun
- 1979 – Khachiyan's ellipsoid method developed by Leonid Khachiyan
- 1979 – ID3 decision tree algorithm developed by Ross Quinlan

- 1980 – Brent's Algorithm for cycle detection 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 – 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 trees discovered by Sleator and Tarjan
- 1986 – Blum Blum Shub proposed by L. Blum, M. Blum, and M. Shub
- 1986 – Push relabel maximum flow algorithm by Andrew Goldberg and Robert Tarjan
- 1986 - Barnes–Hut tree method developed by Josh Barnes and Piet Hut for fast approximate simulation of n-body problems
- 1987 – Fast multipole method developed by Leslie Greengard and Vladimir Rokhlin
- 1988 – Special number field sieve developed by John Pollard
- 1989 - ACORN PRNG published by Roy Wikramaratna
- 1989 – Paxos protocol developed by Leslie Lamport
- 1989 – Skip list discovered by William Pugh

- 1990 – General number field sieve developed from SNFS by Carl Pomerance, Joe Buhler, Hendrik Lenstra, and Leonard Adleman
- 1990 – Coppersmith–Winograd algorithm developed by Don Coppersmith and Shmuel Winograd
- 1990 – BLAST algorithm developed by Stephen Altschul, Warren Gish, Webb Miller, Eugene Myers, and David J. Lipman from National Institutes of Health
- 1991 – 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 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 and 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 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 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, and Niels Ferguson

- 2000 – Hyperlink-induced topic search a hyperlink analysis algorithm developed by Jon Kleinberg
- 2001 – Lempel–Ziv–Markov chain algorithm for compression developed by Igor Pavlov
- 2001 – Viola–Jones algorithm for real-time face detection was developed by Paul Viola and Michael Jones.
- 2001 – 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 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 PEG (Parsing expression grammar) in linear time parsing developed by Bryan Ford
- 2009 – Bitcoin a first trust-less decentralized cryptocurrency system is published

- 2013 – 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.

In mathematics and computer science, an **algorithm** is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes and deduce valid inferences, achieving automation eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus".

In number theory, **integer factorization** is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called **prime factorization**; the result is always unique up to the order of the factors by the prime factorization theorem. A prime factorization algorithm typically involves testing whether each factor is prime after each step.

In computer science, a **search algorithm** is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.

In computer science, the **Cocke–Younger–Kasami algorithm** is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming.

**LZ77** and **LZ78** are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as **LZ1** and **LZ2** respectively. These two algorithms form the basis for many variations including LZW, LZSS, LZMA and others. Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including GIF and the DEFLATE algorithm used in PNG and ZIP.

In computer science, the **clique problem** is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

**Richard Manning Karp** is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

**Combinatorics** is a branch of mathematics concerning the study of finite or countable discrete structures.

In numerical linear algebra, the **QR algorithm** or **QR iteration** is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR algorithm was developed in the late 1950s by John G. F. Francis and by Vera N. Kublanovskaya, working independently. The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate.

**Vaughan Pratt** is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science. Since 1969, Pratt has made several contributions to foundational areas such as search algorithms, sorting algorithms, and primality testing. More recently, his research has focused on formal modeling of concurrent systems and Chu spaces.

A timeline of events related to information theory, quantum information theory and statistical physics, data compression, error correcting codes and related subjects.

**Programming language theory** (**PLT**) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is closely related to other fields including mathematics, software engineering, and linguistics. There are a number of academic conferences and journals in the area.

**Grammar induction** is the process in machine learning of learning a formal grammar from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects. More generally, grammatical inference is that branch of machine learning where the instance space consists of discrete combinatorial objects such as strings, trees and graphs.

This is a timeline of pure and applied mathematics history. It is divided here into three stages, corresponding to stages in the development of mathematical notation: a "rhetorical" stage in which calculations are described purely by words, a "syncopated" stage in which quantities and common algebraic operations are beginning to be represented by symbolic abbreviations, and finally a "symbolic" stage, in which comprehensive notational systems for formulas are the norm.

In numerical analysis, **Gauss–Legendre quadrature** is a form of Gaussian quadrature for approximating the definite integral of a function. For integrating over the interval [−1, 1], the rule takes the form:

In computing, a compiler is a computer program that transforms source code written in a programming language or computer language, into another computer language. The most common reason for transforming source code is to create an executable program.

In computer science and information theory, **Tunstall coding** is a form of entropy coding used for lossless data compression.

The **Lempel–Ziv complexity** is a measure that was first presented in the article *On the Complexity of Finite Sequences*, by two Israeli computer scientists, Abraham Lempel and Jacob Ziv. This complexity measure is related to Kolmogorov complexity, but the only function it uses is the recursive copy.

- ↑ Simon Singh,
*The Code Book*, pp. 14–20 - ↑ Victor J. Katz (1995). "Ideas of Calculus in Islam and India",
*Mathematics Magazine***68**(3), pp. 163–174. - ↑ Bruce, Ian (June 29, 2010). "Euler's Institutionum Calculi Integralis".
*www.17centurymaths.com*. Archived from the original on February 1, 2011. Retrieved 17 May 2023. - ↑ Ciliberto, Ciro; Hirzebruch, Friedrich; Miranda, Rick; Teicher, Mina, eds. (2001).
*Applications of Algebraic Geometry to Coding Theory, Physics and Computation*. Dordrecht: Springer Netherlands. ISBN 978-94-010-1011-5. - ↑ Francis, J.G.F. (1961). "The QR Transformation, I".
*The Computer Journal*.**4**(3): 265–271. doi: 10.1093/comjnl/4.3.265 . - ↑ Kublanovskaya, Vera N. (1961). "On some algorithms for the solution of the complete eigenvalue problem".
*USSR Computational Mathematics and Mathematical Physics*.**1**(3): 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).

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.