# Timeline of algorithms

The following**timeline**outlines the development of

**algorithms**since their inception.

Table of contents |

2 1940s 3 1950s 4 1960s 5 1970s 6 1980s 7 1990s 8 2000s |

## Before 1940

- C. 1600 BC - Babylonians develop first algorithms
- C. 300 BC - Euclid's algorithm
- C. 200 BC - the Sieve of Eratosthenes
- 263 - Gaussian elimination described by Liu Hui
- 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
- 1805 - Cooley-Tukey algorithm known by Carl Friedrich Gauss
- 1926 - Boruvka's algorithm

## 1940s

- 1945 - Merge sort developed by John von Neumann
- 1947 - Simplex algorithm developed by George Dantzig

## 1950s

- 1952 - Huffman coding developed by David A. Huffman
- 1954 - Radix sort computer algorithm developed by Harold H. Seward
- 1956 - Kruskal's algorithm developed by Joseph Kruskal
- 1957 - Prim's algorithm developed by Robert Prim
- 1957 - Bellman-Ford algorithm developed by R. Bellman and L. R. Ford
- 1959 - Dijkstra's algorithm developed by Edsger Dijkstra
- 1959 - Shell sort developed by D. L. Shell
- 1959 - De Casteljau's algorithm developed by Paul de Casteljau

## 1960s

- 1962 - Quicksort developed by C. A. R. Hoare
- 1962 - Ford-Fulkerson algorithm developed by L. R. Ford and D. R. Fulkerson
- 1962 - Bresenham's line algorithm developed by Jack E. Bresenham
- 1964 - Heapsort developed by J. W. J. Williams
- 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 T. Kasami
- 1967 - Viterbi algorithm proposed by Andrew Viterbi
- 1967 - Cocke-Younger-Kasami (CYK) algorithm independently developed by D. H. Younger

## 1970s

- 1970 - Knuth-Bendix completion algorithm developed by Donald Knuth and P. B. Bendix
- 1972 - Graham scan developed by Ronald Graham
- 1973 - RSA encryption algorithm discovered by Clifford Cocks
- 1973 - Jarvis march algorithm developed by R. A. Jarvis
- 1974 - Pollard's p-1 algorithm developed by John Pollard
- 1975 - Genetic algorithms popularized by John Holland
- 1975 - Pollard's rho algorithm developed by John Pollard
- 1975 - Aho-Corasick algorithm developed by Alfred V. Aho and Margaret J. Corasick
- 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 - RSA encryption algorithm rediscovered by Ron Rivest, Adi Shamir, and Len Adleman
- 1977 - LZ77 algorithm developed by Abraham Lempel and Jacob Ziv
- 1978 - LZ78 algorithm developed from LZ77 by Abraham Lempel and Jacob Ziv
- 1978 - Bruun's algorithm proposed for powers of two by G. Bruun

## 1980s

- 1981 - Quadratic sieve developed by Carl Pomerance
- 1983 - Simulated annealing developed by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi
- 1984 - LZW algorithm developed from LZ78 by Terry Welch
- 1985 - Simulated annealing independently developed by V. Cerny
- 1986 - Blum Blum Shub proposed by L. Blum, M. Blum, and M. Shub
- 1987 - RC4 (cipher) developed by Ron Rivest
- 1987 - Skipjack (cipher) designed by NSA
- 1988 - Special number field sieve developed by John Pollard

## 1990s

- 1990 - General number field sieve developed from SNFS by Carl Pomerance, Joe Buhler, Hendrik Lenstra, and Leonard Adleman
- 1991 - IDEA designed by Xuejia Lai and James L. Massey
- 1991 - MD5 developed by Ronald Rivest
- 1991 - Wait-free synchronization developed by Maurice Herlihy
- 1992 - Deutsch-Jozsa algorithm proposed by D. Deutsch and R. Jozsa
- 1993 - Blowfish (cipher) developed by Bruce Schneier
- 1994 - Shor's algorithm developed by Peter Shor
- 1994 - Burrows-Wheeler transform developed by Michael Burrows and David Wheeler
- 1995 - SHA-1 published by NIST
- 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
- 1999 - Yarrow algorithm designed by Bruce Schneier, John Kelsey, and Niels Ferguson

## 2000s

- 2000 - Rijndael cypher developed by Joan Daemen and Vincent Rijmen
- 2001 - AES cypher (based on Rijndael) adopted by NIST
- 2002 - AKS primality test developed by Manindra Agrawal, Neeraj Kayal and Nitin Saxena