Next: Describing an Algorithm Up: Introduction to C++ Programming Previous: Review Questions

# Algorithms

Informally, an algorithm is a series of instructions which if performed in order will solve a problem. For an algorithm to be suitable for computer use it must possess various properties:

1. Finiteness: The algorithm must terminate after a finite number of steps. For example the algorithm:
produce first digit of 1/7.
while there are more digits of 1/7 do
produce next digit.

never terminates because 1/7 cannot be expressed in a finite number of decimal places.
2. Non-ambiguity: Each step must be precisely defined. For example the statement
set k to the remainder when m is divided by n.
is not precise because there is no generally accepted definition for what the remainder is when m is divided by n when m and n are negative. Different programming languages may well interpret this differently.
3. Effectiveness: This basically means that all the operations performed in the algorithm can actually be carried out, and in a finite time. Thus statements like if there are 5 successive 5's in the expansion of then ...' may not be able to be answered.

Even if an algorithm satisfies the above criteria it may not be a practical way of solving a problem. While an algorithm may execute in a finite time it is not much use if that finite time is so large as to make solution completely impractical. Thus there is a lot of interest in finding good' algorithms which generate correct solutions in a short time compared with other algorithms. In sorting 10,000 numbers into ascending order a good' algorithm executing on a PC took less than a second while a poor' algorithm took over 10 minutes.

Subsections

Next: Describing an Algorithm Up: Introduction to C++ Programming Previous: Review Questions
Peter JB King
1999-08-31