The concept of algorithms has a long history, dating back to ancient civilizations. The word "algorithm" can be traced back to the 9th century when it was coined by the Persian mathematician Abdullah Muhammad bin Musa al-Khwarizmi, who is often referred to as "The Father of Algebra."
In the 12th century, one of al-Khwarizmi's books was translated into Latin, and his name was rendered as "Algorithmi." However, the idea of algorithms existed long before this time, as various cultures and civilizations developed methods and techniques for solving problems and making calculations. Let's have a look:
- Euclid's algorithm for finding the greatest common divisor of two numbers, developed 2,000 years ago.
- The Urdhva Tiryakbhyam algorithm, used by Vedic mathematicians for fast integer multiplication.
- Arithmetic algorithms used by the Babylonians and Egyptians, such as a division algorithm.
- The Sieve of Eratosthenes, used by Greek mathematicians to find prime numbers.
- Cryptographic algorithms used by Arabic mathematicians for code-breaking.
- The Chinese Remainder Theorem, discovered by Chinese mathematicians in the 3rd century AD.
- The Babylonian-Sumerian method of extracting a root, one of the first documented examples of a mathematical algorithm.
- Gauss's Gaussian elimination algorithm for solving systems of linear equations.
- The "Chakravala" method, a cyclic algorithm developed by Brahmagupta, Bhaskara, and Jayadeva to solve indeterminate quadratic equations.
Even most of the above algorithms are still relevant. Now the critical question is - Why we used the above algorithms in ancient times? Are algorithms just about computers or more than that? Think!
Timeline of famous algorithms after 1500 AD!
- 1540 — method to find the roots of a quartic polynomial
- 1545 — method for finding the roots of a cubic polynomial
- 1614 — method for performing calculations using logarithms
- 1671 — Newton–Raphson method
- 1842 — The first algorithm for a computing engine
- 1847—George Boole unified logic with calculations and formed the basis of today's computing logic: Boolean Algebra.
- 1888— Giuseppe Peano established the axiomatisation of mathematics. He used equations with symbols to obtain results that would later become rules that modern-day mathematics and algorithms are based on.
- 1930 — Lambda calculus. It is equivalent to a Turing machine that has provided a solid theoretical foundation for functional programming languages.
- 1936 — Turing machine, an abstract machine that developed the modern notion of "algorithm."
- 1942 — A fast Fourier transform algorithm
- 1945 — Merge sort
- 1943—Kleene's algorithm. It transforms a given nondeterministic finite automaton into a regular expression.
- 1947 — Simplex algorithm
- 1952 — Huffman coding
- 1954 — Radix sort algorithm
- 1956 — Kruskal's algorithm
- 1956 — Ford–Fulkerson algorithm
- 1957 — Prim's algorithm
- 1957 — Bellman-Ford algorithm
- 1959 — Dijkstra's algorithm
- 1959 — Shell sort
- 1960 — Karatsuba multiplication
- 1962 — AVL trees
- 1962 — Quicksort
- 1962 — Stable-marriage algorithm
- 1964 — Heapsort
- 1965 — Cooley–Tukey algorithm
- 1965 — Levenshtein distance
- 1965 — LR parsers
- 1967 — Viterbi algorithm
- 1968 — A* graph search algorithm
- 1969 — Strassen algorithm for matrix multiplication
- 1972 — Graham scan
- 1972 — Red-black trees and B-trees
- 1973 — RSA encryption algorithm
- 1973 — Jarvis march algorithm
- 1973 — Hopcroft–Karp algorithm
- 1974 — Quadtree developed
- 1976 — Knuth–Morris–Pratt algorithm
- 1977 — Boyer–Moore string search algorithm for searching the occurrence of a string into another string.
- 1980 — Brent's Algorithm for cycle detection
- 1983 — Classification and regression tree algorithm
- 1984 — Karmarkar's interior-point algorithm
- 1985 — Splay trees
- 1986 — Push relabel maximum flow algorithm
- 1991 — Wait-free synchronization
- 1993 — Apriori algorithm
- 1993 — Algorithm to compute the minimum cut of a connected graph
- 1998 — PageRank algorithm
- 2001 — Distributed hash table
- 2001 — BitTorrent, the first fully decentralized peer-to-peer file distribution system, is published
- 2009 — Bitcoin, a first trust-less decentralized cryptocurrency system, is published
As computing power has increased, algorithms have become more complex. Today, we are on the verge of a new era of artificial intelligence and quantum computing, and algorithms are evolving at every stage of technological innovation. However, despite the changes and advances, the basic principles of algorithms remain the same as they have been throughout history.
Algorithms are present in every generation and can be found in various forms and applications from ancient times to the present day. Algorithms are an integral part of our daily lives and will continue to play a vital role as technology advances. Enjoy learning, enjoy algorithms!