Introduction
Informally, an algorithm is any well-deûned computational procedure that takes
some value, or set of values, as input and produces some value, or set of values, as
output in a ûnite amount of time. An algorithm is thus a sequence of computational
steps that transform the input into the output.
You can also view an algorithm as a tool for solving a well-speciûed computational
problem. The statement of the problem speciûes in general terms the desired
input/output relationship for problem instances, typically of arbitrarily large size.
The algorithm describes a speciûc computational procedure for achieving that input/
output relationship for all problem instances.
As an example, suppose that you need to sort a sequence of numbers into monotonically
increasing order. This problem arises frequently in practice and provides
fertile ground for introducing many standard design techniques and analysis tools.
Here is how we formally deûne the sorting problem:
Input: A sequence of n numbers ha 1 ; a 2 ; : : : ; a n i.
Output: A permutation (reordering) ha 0
1 ; a 0
2 ; : : : ; a 0
n i of the input sequence such
that a 0
1 හ a 0
2 හ හ a 0
n .
Thus, given the input sequence h31; 41; 59; 26; 41; 58i, a correct sorting algorithm
returns as output the sequence h26; 31; 41; 41; 58; 59i. Such an input sequence is