Foundations of Algorithms

Definition

An algorithm is a finite, ordered sequence of well-defined instructions that, if followed, accomplishes a particular task.

From this definition we can derive the necessary properties that an algorithm must have.

Properties of Algorithms

1. Input: Zero or more quantities are externally supplied to the algorithm.
2. Output: At least one quantity will be produced by the algorithm. If an algorithm does not return anything then it must have an observable side-effect.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If we trace out the instructions of the algorithm, then for all cases, the algorithm must terminate after a finite number of steps.
5. Effectiveness: Every instruction must be so basic that it can be carried out, in principle, by a person using pen and paper. Moreover, each instruction must be feasible.

In the following sections we examine how algorithms are written.