Algorithms

An algorithm is a finite, well-defined sequence of steps or instructions that solves a problem or performs a calculation. It is neither a program nor a machine: it is the abstract procedure that a person with pencil and paper can carry out just as a computer can. A bread recipe or the long-division method taught in school are, in this sense, algorithms.

The word comes from al-Khwarizmi (Muhammad ibn Musa al-Khwarizmi), a ninth-century Persian mathematician at the House of Wisdom in Baghdad; the medieval Latinization of his name, «Algoritmi», came to denote methods of calculation. The idea is older still: Euclid's algorithm for the greatest common divisor is more than two thousand years old. Primary source.

Properties of an algorithm

In «The Art of Computer Programming», Donald Knuth sets out five properties every algorithm must have. Finiteness: it always terminates after a finite number of steps. Definiteness: each step is specified rigorously and without ambiguity. Input: it takes zero or more initial values drawn from a defined set. Output: it produces one or more results bearing a precise relation to the input. Effectiveness: its operations are basic enough to be carried out exactly and in finite time. A procedure that never ends, or whose steps are ambiguous, is not an algorithm.

Classic examples

Sorting algorithms such as quicksort and mergesort rearrange a list from smallest to largest. Binary search finds an item in a sorted list by halving it at each step. Euclid's algorithm, Knuth's favorite example, computes the greatest common divisor of two numbers through successive subtractions or divisions. All share the same anatomy: defined input, precise steps, output, and a guaranteed end. Primary source.

Complexity

A single problem admits many algorithms, and they do not all cost the same. Complexity measures the resources an algorithm consumes as its input grows: time (the number of operations) and space (memory). It is expressed with Big O notation, an upper bound on that growth. Binary search runs in O(log n), which is very efficient; sorting with quicksort or mergesort is around O(n log n). This measure lets us compare algorithms independently of the particular computer that runs them. Primary source.

Algorithms and AI

Machine-learning algorithms —gradient descent, backpropagation, k-means— are a type of algorithm, not something apart. It is worth distinguishing the algorithm (the training procedure) from the model it produces (the specific set of parameters fitted to some data). Gradient descent adjusts weights to minimize error; backpropagation computes how to do so in a neural network; k-means groups unlabeled data into clusters. Modern AI is, at bottom, a catalogue of algorithms applied to data.