This page is a compilation of the list of top algorithms tweeted here.
Disclaimers:
- It is not intended to be a definitive list. To add a name to the list, drop me an email or do a pull request.
- Credits are not intended to be complete, I often just put a single name but many algorithms have a much more complicated history (you can check the associated link for more details).
- “Algorithm” should be understood in a loose sense and it includes mathematical models (eg. least squares, lasso, SVM, etc.) that can be solved using different algorithms (but these concepts were key conceptual breakthroughs which often drove algorithmic research).
- The classification is rather arbitrary, since many algorithms belong to several classes.
Arithmetic and Polynomials
Computer Science and Graphs
- 1880: Depth-first search (Charles Pierre Trémaux)
- 1887: Radix sort (Herman Hollerith)
- 1930: Prim minimum spanning tree (Vojtěch Jarník, Robert Prim)
- 1945: Breadth-first search (Konrad Zuse, Michael Burke)
- 1953: Hashing (Hans Peter Luhn)
- 1953: Katz Centrality (Leo Katz)
- 1954: Dynamic programming (Richard Bellman)
- 1956: Dijkstra (Edsger Dijkstra)
- 1956: Kruskal minimum-spanning-tree (Joseph Kruskal)
- 1956: Bellman-Ford shortest paths (Richard Bellman, Lester Ford)
- 1959: Quicksort (Tony Hoare)
- 1962: Topological sorting (Arthur Kahn)
- 1962: Floyd–Warshall all pairs shortest path (Robert Floyd, Stephen Warshall)
- 1963: Planar graph embedding (William Tutte)
- 1964: Steinhaus-Johnson-Trotter permutation generation (Hugo Steinhaus, Selmer M. Johnson, Hale F. Trotter)
- 1968: A star shortest path (Peter Hart, Nils Nilsson, Bertram Raphael )
- 1970: Knuth-Morris-Pratt string search (Donald Knuth, Vaughan Pratt, James H. Morris)
- 1970: Needleman-Wunsch dynamic programming (Saul Needleman, Christian Wunsch)
- 1972: Tarjan stronly connected components (Robert Tarjan)
- 1977: Boyer-Moore string search ( Robert S. Boyer, Strother Moore)
- 1984: Maximum subarray problem (Jay Kadane)
- 1999: Locality sensitive hashing (Piotr Indyk)
- 2000: Dancing links (Donald Knuth)
- 2002: Girvan-Newman communities detection (Michelle Girvan, Mark Newman)
- 2004: Chaitin graph coloring (Gregory Chaitin)
- 2008: MapReduce (Jeffrey Dean, Sanjay Ghemawat)
Numerical Analysis, ODEs and PDEs
Matrices
Graphics and Geometry
- 1960: B-Splines (Pierre Bezier, Paul de Faget de Casteljau)
- 1968: Ray tracing (Appel A.)
- 1969: Binary space partitioning (Robert Schumacker)
- 1969: Non-uniform rational B-spline (Ken Versprille)
- 1971: de Boor’s algorithm (Carl de Boor)
- 1972: Newell’s painter algorithm (Martin Newell, Dick Newell, Tom Sancha)
- 1972: Graham scan convex hull (Ronald Graham)
- 1974: Sutherland-Hodgman polygons clipping (Ivan Sutherland, Gary Hodgman)
- 1974: Z buffer (Wolfgang Straßer)
- 1975: k-d tree nearest neighbor search (J. L. Bentley)
- 1976: Floyd–Steinberg dithering (Robert Floyd, Louis Steinberg)
- 1978: Catmull–Clark Subdivision Surfaces (Edwin Catmull, Jim Clark)
- 1981: Bowyer–Watson Delaunay triangulation (Adrian Bowyer, David Watson)
- 1983: Perlin noise (Ken Perlin)
- 1983: Alpha shapes (Herbert Edelsbrunner)
- 1988: Semi-discrete optimal transport (V. I. Oliker and L. D. Prussner)
- 1987: Marching cubes (William Lorensen, Harvey Cline)
- 1993: Delaunay refinement (Ruppert, Chew)
- 1996: Progressive meshes (Hugues Hoppe)
- 1996: Path tracing (E. Lafortune)
- 1997: Metropolis light transport (Eric Veach, Leonidas Guibas)
- 2001: Photon mapping (Henrik Wann Jensen)
Signal and Image
- 1964: Mathematical morphology (Georges Matheron, Jean Serra)
- 1965: Fast Fourier transform (John Tukey, James Cooley)
- 1972: Gerchberg-Saxton phase retrieval (R. W. Gerchberg and W. O. Saxton)
- 1978: Discrete Cosine Transform (Narasimha, M.; Peterson, A.)
- 1977: MUSIC frequency estimation (R.O Schmidt)
- 1986: Canny edge detector (John Canny)
- 1987: Anisotropic diffusion (Pietro Perona, Jitendra Malik)
- 1988: Orthogonal Wavelets (Ingrid Daubechies)
- 1989: Fast wavelet transform (Stéphane Mallat)
- 1989: ESPRIT frequency estimation (R. Roy and T. Kailath)
- 1989: Mumford-Shah segmentation (David Mumford, Jayant Shah)
- 1990: Matrix pencil frequency estimation (Y. Hua and T. K. Sarkar)
- 1992: Approximate recursive filtering (Rachid Deriche)
- 1992: Total variation denoising (L. I. Rudin, S. Osher, E. Fatemi)
- 1993: Matching pursuit (Stéphane Mallat)
- 1997: Lifting scheme (Wim Sweldens)
- 1998: Basis pursuit (David Donoho)
- 1999: FastICA (Aapo Hyvärinen)
- 2004: SIFT (David Lowe)
- 2005: Non-local means (Antoni Buades, Jean-Michel Morel)
- 2006: Compressed sensing (Emmanuel Candes)
- 2007: Block-matching and 3D filtering (Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, Karen Egiazarian)
- 2011: Phase lift phase retrieval (Emmanuel Candes, Thomas Strohmer, Vladislav Voroninski)
- 2013: Blasso sparse spikes superresolution (Yohann de Castro)
Statistics and Machine Learning
- 1901: Principal component analysis (Karl Pearson)
- 1912: Maximum likelihood estimation (Ronald Fisher)
- 1943: Ridge regression (Andrey Tikhonov)
- 1956: Kernel density estimation (Emanuel Parzen, Murray Rosenblatt)
- 1957: K-means / Lloyd-max (Stuart Lloyd)
- 1958: Logistic regression (David Cox)
- 1960: Empirical risk minimization (Vladimir Vapnik)
- 1962: k-nearest neighbor (George Sebestyen)
- 1963: Support vector machine (Vladimir Vapnik)
- 1966: Hidden Markov model (Leonard Baum)
- 1966: Baum-Welch HMM MLE (Leonard Baum, Lloyd Welch)
- 1968: K-fold cross validation (John Tukey)
- 1981: RANSAC parameter estimation (Martin Fischler, Robert Bolles)
- 1982: Recurrent neural network (John Hopfield)
- 1984: Approximate Bayesian Computation (Peter Diggle, Richard Gratton)
- 1984: Classification And Regression Tree (Leo Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone)
- 1984: Probably approximately correct learning (Leslie Valiant)
- 1990: Boosting (Robert Schapire)
- 1990: Convolutional neural network (Yann LeCun)
- 1990: Spectral clustering (A. Pothen, H. Simon, K.-P. Liou)
- 1994: Bootstrap (Leo Breiman)
- 1995: Random forests (Leo Breiman)
- 1995: Kernel trick for SVM (Corinna Cortes, Vladimir Vapnik)
- 1996: Lasso (Robert Tibshirani)
- 1996: DBSCAN clustering (Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu)
- 1997: Long short-term memory (Sepp Hochreiter, Jürgen Schmidhuber)
- 2001: Aggregating algorithm (Volodya Vovk)
- 2003: Latent Dirichlet Allocation (Blei, David M.; Ng, Andrew, Michael Jordan)
- 2012: Dropout (Geoffrey Hinton et al)
- 2014: Generative adversarial networks (Ian Goodfellow)
Probability
- 1949: Metropolis–Hastings (Stanislaw Ulam, Nicholas Metropolis, John von Neumann)
- 1955: Importance sampling (Herman Kahn)
- 1960: Kalman filter (Rudolf Kálmán)
- 1967: Max product message passing (Andrew Viterbi)
- 1967: Sobol low-discrepancy sequences (Ilya Sobol)
- 1974: Milstein method (Grigori Milstein)
- 1974: Alias method (Alastair Walker)
- 1977: Expectation Maximization (Arthur Dempster, Nan Laird, Donald Rubin)
- 1978: VEGAS Monte-Carlo (G.P. Lepage)
- 1982: Sum product message passing, belief propagation) (Judea Pearl)
- 1984: Gibbs sampling (Stuart and Donald Geman)
- 1985: Reservoir sampling (Jeffrey Vitter)
- 1987: Hamiltonian Monte Carlo (Simon Duane)
- 1990: Junction tree for message passing (P. Shafer, G. Shenoy)
- 1996: Particle filter (Neil Gordon, David Salmond, Adrian Smith)
- 1996: Coupling from the past (James Propp, David Wilson)
- 1997: Mersenne twister for random number generation (Makoto Matsumoto, Takuji Nishimura)
- 2004: Nested-sampling (John Skilling)
- 2012: Tamed Euler method (Martin Hutzenthaler)
Optimization
- 1669: Newton’s Method (Isaac Newton)
- 1847: Steepest descent (Augustin-Louis Cauchy)
- 1939: Linear programming (Leonid Kantorovich)
- 1944: Levenberg-Marquardt ( Kenneth Levenberg, Donald Marquardt)
- 1947: Simplex (George Dantzig)
- 1952: Stochastic gradient descent (Herbert Robbins, Sutton Monro, Jacob Wolfowitz, Jack Kiefer)
- 1956: Ford-Fulkerson maximum flow (L. R. Ford, D. R. Fulkerson)
- 1956: Frank-Wolfe (Marguerite Frank, Philip Wolfe)
- 1957: Hungarian (Harold Kuhn, James Munkres)
- 1958: Cutting-plane mixed integer programming (Ralph Gomory)
- 1960: Branch and bound for combinatorial optimization (A. H. Land, A. G. Doig)
- 1962: Gale-Shapley stable marriage (David Gale, Lloyd Shapley)
- 1964: Powell’s method (Michael Powell)
- 1965: Nelder–Mead derivative free method (John Nelder, Roger Mead)
- 1967: Bregman iterative projections (Lev Bregman)
- 1970: Proximal point algorithm (Tyrrell Rockafellar)
- 1970: Reverse mode automatic differentiation (Seppo Linnainmaa)
- 1970: BFGS (Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno)
- 1970: Majorize-Minimize (J.M. Ortega, W.C. Rheinboldt)
- 1970: Edmonds–Karp max-flow (Yefim Dinitz, Jack Edmonds, Richard Karp)
- 1973: Genetic algorithm (Ingo Rechenberg, Hans-Paul Schwefel)
- 1975: Alternating direction method of multipliers (R. Glowinski, A. Marrocco, D. Gabay, B. Mercier)
- 1979: Mirror descent (Arkadi Nemirovski)
- 1979: Auctions (Dimitri Bertsekas)
- 1979: Forward-Backward (Pierre-Louis Lions, Bertrand Mercier)
- 1979: Douglas-Rachford (Pierre-Louis Lions, Bertrand Mercier)
- 1983: Fast gradient method (Yurii Nesterov)
- 1983: Simulated Annealing (Scott Kirkpatrick)
- 1984: Interior point method (Narendra Karmarkar)
- 1984: Espresso minimization algorithm (Robert Brayton)
- 1986: Push-relabel maximum flow (Andrew V. Goldberg, Robert Tarjan)
- 1986: Dykstra (Richard Dykstra)
- 1994: Dynamic time warping (D. J. Berndt, J. Clifford)
- 1995: Network simplex (James Orlin, Robert Tarjan)
- 1995: Maxcut SDP relaxation (Michel Goemans, David Williamson)
- 1995: alphaBB for global optimization (Ioannis Androulakis)
- 1996: Conflict driven clause learning (Marques-Silva and Sakallah)
- 2001: Burrer-Montero (Samuel Burer, Renato Monteiro)