Top algorithms

A compilation of “top” algorithms from different sources.

First, the algorithms that appeared on multiple independent lists:

• The FFT 0 2 4 6
• The simplex method for linear programming 0 2 6
• The QR algorithm and related decompositions (LU, SVD, etc.) for computing eigenvalues and least-squares solutions 0 2 4
• Monte Carlo methods and the Metropolis algorithm 0 2
• Mergesort 3 5
• Krylov subspace iteration methods such as conjugate-gradient and Lanczos 0 2
• Quicksort 0 6
• Hashing and hash tables 3 6
• Dijkstra’s algorithm 4 6
• PageRank and related link-analysis algorithms 1 6
• Huffman coding and other data compression 4 6
• Newton and quasi-Newton methods 1 4
• Binary search 3 6
• RSA 4 6
• Heapsort 4 6
• Diffie-Hellman key exchange 4
• The quadratic sieve and other integer factorization algorithms 4
• The Ford-Fulkerson algorithm for maximum flow 4
• The decompositional approach to matrix computations 0
• The Fortran I optimizing compiler 0
• fast multipole methods (for e.g. N-body simulation) 0
• the Kalman filter 1
• Dynamic programming 4
• Gradient descent 4
• A* search 4
• PID control 5
• RANSAC 4
• Q-learning 4
• Gaussian elimination 2
• the Viterbi algorithm 4

Here are the ones that I think appeared on only one list:

• Integer relation detection 0
• JPEG 1
• least-squares fitting 2
• Gauss quadrature for numerical integration 2
• Adams formulae for ODEs 2
• Runge-Kutta formulae for ODEs 2
• finite differences for PDEs 2
• floating-point arithmetic 2
• splines (including Bézier, de Boor, and others) 2
• stiff ODE solvers 2
• the finite element method for PDEs 2
• orthogonal linear algebra (Givens rotations, etc.) (maybe this should be part of the QR item?) 2
• preconditioning of linear systems 2
• spectral methods for PDEs 2
• MATLAB 2
• multigrid methods for PDEs 2
• IEEE floating-point arithmetic 2
• nonsymmetric Krylov iterations 2
• interior point methods for optimization 2
• wavelets 2
• automatic differentiation 2
• Rabin-Karp string matching (e.g. for plagiarism detection) 6
• the Gayle-Shapely algorithm for the Stable Marriage problem 6
• Bloom filters for e.g. malicious site filtering 6
• LALR parsing 6
• Red-black trees 6
• Bresenham’s algorithms for drawing circles and lines 6
• Kruskal’s algorithm 6
• Depth-first search 6
• Breadth-first search 6
• Convnets 6
• the forward algorithm for hidden Markov models 6
• Raycasting 6
• Knuth-Morris-Pratt string search 6
• Radix sort 6
• Markov-chain Monte Carlo/particle filters 6
• Shor’s algorithm 6
• prune-and-branch tree search 6
• Beam search 4
• Branch and bound (is this the same as “interior point methods”?) 4
• Buchberger’s algorithm (generalization of Euclid’s) 4
• Discrete differentiation 4
• Euclid's algorithm 4
• The expectation-maximization algorithm (EM-training) 4
• Binary heaps 4
• Karatsuba multiplication 4
• Lenstra-Lenstra-Lovasz (LLL) lattice reduction 4
• The Schönhage-Strassen algorithm 4
• Strukturtensor 4
• Union-find 4
• SHA-1 and SHA-2 5
• PRNGs 5