The success of computers is largely due to the existence of efficient algorithms for solving numerical and combinatorial problems. These algorithms are used billion of times per second. Many users (even among scientists) do not know them. One may find a list of algorithms on Wikipedia. Depending on your tastes, you may distinguish some favorite ones, for their simplicity, elegance, or versatility. Here are some few of my favorite algorithms and paradigms:
- Gram-Schmidt algorithm, QR algorithm, LU algorithms
- Gauss elimination, Euclidean algorithm and Gröbner bases
- Simplex algorithm, Hungarian algorithm, linear programming, semi-definite programming
- Gradient descent, binary search, Newton algorithm
- Robbins-Monro and Kiefer-Wolfowitz stochastic approximation
- Expectation-Maximization, Matching pursuit, Classification And Regression Tree
- Fast Fourier Transform algorithm, Fast Wavelet Transform algorithm, Kalman filter
- Euler algorithms, finite elements algorithms, finite volume algorithms
- Quick sort, Dijkstra algorithm, Message-Digest algorithm, Secure Hash Algorithm
- Huffman coding, Lempel-Ziv-Welch coding
- Hamming coding, Reed-Muller coding, Gallager coding
- Rivest-Shamir-Adleman algorithm, Digital Signature Algorithm
- Knuth-Morris-Pratt, Rabin-Karp, and string matching algorithms
- Miller-Rabin algorithm, Schonhage-Strassen algorithm
- Fisher-Yates-Knuth shuffle, Mersenne twister, Marsaglia ziggurat
- Metropolis-Hastings, Propp-Wilson coupling from the past, simulated annealing
- Monte-Carlo methods
- Dynamic programing paradigm
- Genetic algorithms paradigm
- Branch and bound paradigm
- Greedy algorithms paradigm
- Divide and conquer paradigm
Ironically, the most used algorithms (if we measure say in Megawatt) concern coding, compression, cryptography, linked with what is often identified as “pure mathematics” (finite fields algebra, discrete linear algebra, discrete harmonic analysis). This does not mean that numerical algorithms, identified as “applied mathematics”, are not used! To me, what matters is the depth and beauty of concepts and the efficiency and versatility of implementations.
- Iterative and non-iterative
- Exact and approximate
- Stochastic and deterministic
- Integer and numerical
- Euclid and Archimedes