Algorithms, Design Goals, Pseudocode and Implementations

What is an algorithm?

An algorithm is a set of instructions for performing a specific task.

Somewhat more formally, to ensure that we truly do have an algorithm in the strict sense, we require that such a set of instructions also be

• finite (it can't go on forever)
• concrete and unambiguous (it must say exactly, and clearly, what to do)
• effective (it must actually get the job done, i.e., it must perform the required task correctly)

Goals of Algorithm Design

When designing an algorithm you should strive to

1. Make it easy to understand, code and debug. In order to do this, an appropriate choice of algorithm design methodology will have to be chosen:
   1. Find an algorithm that's already been written and solves your problem.
   2. Use a structured, top-down approach to design your own.
   3. Use an object-oriented approach to design your own.
   4. Use a "generic" approach to design your own, as illustrated by the STL.
2. Have it make the best possible use of the computer's resources, and in particular:
   1. The time taken by the algorithm to perform its task
   2. The amount of computer storage (memory and disk) used by the algorithm to perform its task.
   In order to convince ourselves that we have chosen the most appropriate algorithm for the task at hand, we may have to perform some algorithm analysis. That is, we may have to perform some mathematical calculations designed to tell us how well an algorithm will perform, either in the absolute sense, or relative to some other algorithm with which we want to compare it, and for which we will perform the same, or similar, calculations.

Question: How do we describe algorithms? Answer: Pseudocode (usually)

The term pseudocode refers to a sequence of short English phrases used to describe the steps of an algorithm and formatted in such a way as to make the instructions clearer than they would be without such formatting.

You can also think of pseudocode as an informal "language" used to help programmers develop software. What many inexperienced programmers do not realize about pseudocode is this: If they cannot, or do not, or will not, describe their algorithm in clear and unambiguous pseudocode, the chances of their succeeding in describing it in actual code are very, very small.

The pseudocode for an algorithm is best given in such a way that it is programming-language independent. However, most programmers tend to write pseudocode that reflects their language of choice. This is probably a better alternative than trying to design a new "pseudocode" language and attempting to have everyone agree to write their pseudocode using yet another language.

Implementations

Any algorithm described by pseudocode can be implemented by any mechanism that can understand and carry out the instructions embodied in that pseudocode.

Thus an algorithm might be implemented by:

1. A human
2. A machine
3. A computer program running on a machine (i.e., a computer)
4. Any other suitable mechanism

And, if an algorithm is implemented by a computer program running on a machine, that algorithm might be written in any number of different programming languages. The only requirement is that the language be expressive enough to be able to describe the steps necessary to perform the steps of algorithm.