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 \( \pi \) 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