Algorithms

Precise definition

An algorithm is a finite, unambiguous sequence of effective steps that transforms every permitted input into an output satisfying a stated specification. Correctness has two parts: partial correctness says that any terminating run returns a valid output; termination says that every permitted run eventually stops. Together they give total correctness.

Notation and mathematical language

Write an input instance as $x$, the algorithm as $A$, and its output as $A(x)$. A precondition $P(x)$ describes legal inputs and a postcondition $Q(x,A(x))$ describes required outputs. For a loop, an invariant $I$ is true before and after every iteration; a decreasing non-negative variant can establish termination.

Conceptual picture

An algorithm is not merely code in a particular language. It is the mathematical process behind the code. A trace table records the state after each step, while an invariant captures what all those states have in common. Correctness explains why every input works; testing can only reveal behaviour on selected inputs.

Fully worked example

Interpretation and application

Algorithms govern routing, scheduling, searching, encryption, and numerical computation. In practice, input validation belongs to the specification: if negative values, missing data, or overflow are possible, either the precondition must exclude them or the algorithm must define how they are handled.

Common mistakes