Algorithm
Algorithm
An algorithm is a finite sequence of well-defined instructions, typically used to solve a class of problems or perform a computation. Algorithms are fundamental to computer science and mathematics, serving as the blueprint for writing computer programs. They can be expressed in many notations, including natural language, pseudocode, flowcharts, or programming languages.
The term derives from the name of the 9th-century Persian mathematician Muhammad ibn Musa al-Khwarizmi, whose works introduced systematic procedures for solving linear and quadratic equations. Al-Khwarizmi's name was Latinized as "Algoritmi," which eventually led to the word "algorithm."
Algorithms are characterized by their input, output, definiteness, finiteness, effectiveness, and generality. They may be evaluated based on correctness, time complexity, and space complexity. Problems in computer science often involve designing algorithms that are as efficient as possible, using techniques such as divide and conquer, dynamic programming, or greedy algorithms.
History
The concept of an algorithm predates modern computing. Ancient examples include the Euclidean algorithm for computing the greatest common divisor, described by the Greek mathematician Euclid around 300 BCE. In the 9th century, al-Khwarizmi's work The Compendious Book on Calculation by Completion and Balancing introduced algebraic methods that became foundational. During the Islamic Golden Age, algorithms were refined for arithmetic and astronomy.
The modern understanding emerged with the development of computability theory in the 1930s, thanks to Alan Turing, Alonzo Church, and others. Turing's Turing machine formalized the notion of an algorithm, providing a model for computation. The subsequent rise of digital computers made algorithmic thinking essential for programming.
Features
- Finiteness: An algorithm must always terminate after a finite number of steps.
- Definiteness: Each step must be precisely defined and unambiguous.
- Input: Zero or more inputs are supplied externally.
- Output: At least one output is produced.
- Effectiveness: Each instruction must be basic enough to be carried out, in principle, by a human using pencil and paper.
- Generality: The algorithm should apply to a set of inputs, not just a single case.
Common Types
- Sorting algorithms (e.g., quicksort, mergesort)
- Search algorithms (e.g., binary search, depth-first search)
- Graph algorithms (e.g., Dijkstra's algorithm, Bellman-Ford algorithm)
- Cryptographic algorithms (e.g., AES, RSA)