5 Algorithms that Changed the World
An algorithm is a straightforward rule of action to solve a problem or a class of problems. Algorithms consist of a finite number of well-defined individual steps. Thus, they can be implemented in a computer program for execution and formulated in human language. When solving a problem, a specific input is converted into a particular output.
In the following, five algorithms are listed that have significantly influenced our world.
1. Metropolis Algorithm for Monte Carlo
The Metropolis algorithm is a Markov-Chain-Monte-Carlo method for generating states of a system according to the Boltzmann distribution. The more general Metropolis-Hastings algorithm derived from this algorithm makes it possible to simulate sequences of random variables, more precisely Markov chains, which have the desired distribution as stationary distribution, especially in many cases where the distributions of the random variables cannot be simulated directly. (more info)
2. Simplex Method for Linear Programming
A simplex method (also known as a simplex algorithm) is a numerical optimization method for solving linear optimization problems, also known as linear programs (LP). It solves such a problem exactly after finitely many steps or determines its insolubility or unboundedness. George Dantzig introduced the basic idea of simplex methods in 1947; since then, they have developed into the most critical solution methods of linear optimization in practice through numerous improvements. Simplex methods are pivot methods. (more info)
3. Fast Fourier Transform
The fast Fourier transform (FFT) is an algorithm for the efficient calculation of discrete Fourier transform (DFT). It can be used to decompose a digital signal into its frequency components, which can then be analyzed. Analogously there is the inverse fast Fourier transformation (IFFT) for the discrete inverse Fourier transformation. The IFFT uses the same algorithms but with conjugated coefficients.
The FFT has numerous applications in engineering, natural sciences, and applied mathematics. It is also used in mobile technologies such as UMTS and LTE and wireless data transmission such as WLAN. (more info)
4. Quicksort Algorithm for Sorting
Quicksort s a fast, recursive, non-stable sorting algorithm that works on the principle of parts and dominance. It was developed around 1960 by C. Antony R. Hoare in its basic form and has since been improved by many researchers. The algorithm has the advantage of a very short inner loop (which significantly increases the execution speed). It does not require additional memory (apart from the extra space needed on the call stack for recursion). (more info)
5. QR Algorithm for Computing Eigenvalues
The QR algorithm is a numerical method for calculating all eigenvalues and possibly the eigenvectors of a quadratic matrix. The QR method or QR iteration is based on QR decomposition and was introduced independently by John G. F. Francis and Wera Nikolajewna Kublanowskaja in 1961–1962. A predecessor was the LR algorithm by Heinz Rutishauser (1958), which is less stable and based on LR decomposition. Often the iterates from the QR algorithm converge against the Schur form of the matrix. Therefore, the original procedure is quite complex — even on today’s computers — not practicable for matrices with hundreds of thousands of rows and columns.
Derived variants like the multishift method of Z. Bai and James Demmel 1989 and the numerically more stable variant of K. Braman, R. Byers, and R. Mathias 2002 have practical runtimes cubic in the size matrix. The latter method is implemented in the numerical software library LAPACK, which is used in many computer algebra systems (CAS) for the numerical matrix algorithms. (more info)
If I had to pick one, my favorite would be Fast Fourier Transform (FFT), because FFT has numerous applications in engineering, natural sciences, and applied mathematics and has an inherent beauty. ~ Murat Durmus
Murat
(The text is an excerpt from my new book “MINDFUL AI — Reflection Artificial Intelligence”)
