Pseudocode - a high-level English-like language used to define
When presented with a problem to solve, the first requirement is to list a
set of steps (algorithm) which describe the operations
required to obtain the solution. For example, suppose we are
asked to find the greatest common divisor (gcd) of two positive integers
a and b, i.e., gcd(a,b) is the largest integer that divides
both a and b without remainder. Here is an algorithm to solve the gcd
1. Input a,b.
2. Initialize the value of x to a and the value of y to b.
3. If x>y then set x to x-y.
4. If x<y then set y to y-x.
5. Repeat steps 3 and 4 until x=y.
6. Output x (or y) and halt.
Euclid's algorithm, which can be traced to 300 B.C.,
is guaranteed to eventually terminate (convince yourself!)
and output the gcd of a and b.
The algorithm is based on the observation that for a>b or a=b, an
integer divides both a and b if and only if it divides a-b and
b. Thus gcd(a,b)=gcd(a-b,b), a>b or a=b, gcd(a,a)=a.
The language used to describe the algorithm is called pseudocode
because it is not written in any real programming language but is a
concise, English-like description of the necessary steps. An
algorithm is an abstraction of a program, since
it precisely specifies the unambiguous set of operations and steps necessary to
solve a problem while avoiding the low-level details of a programming
language. By removing the low-level coding details of the program, the
method of problem solution is much easier to understand. In order to solve
the problem on a computer, the algorithm must be translated into a
computer program using a
real programming language like C as shown below:
else if(x<y) y=y-x;
Obviously, the pseudocode algorithm is much easier to understand
than the corresponding C program, which is full of all kinds of strange
symbols and cryptic notation.
The pseudocode describes the algorithm
for solving the problem while avoiding the low-level, and mostly
of the programming language. In essence, then, an algorithm is an
abstraction of a program. Once an algorithm is defined, it can be
translated and implemented in any programming language and run
on any computer with the same results.
Attributes of a Good Algorithm
Here are some attributes of a good algorithm design. It is not always
possible to satisfy all of these properties completely and
simultaneously, since some problems are very complex and hence
require complex algorithmic solutions. Rather, they
should serve as general goals in designing algorithms.
- Correctness - terminates on ALL inputs (even invalid inputs!) and
outputs the correct answer.
- Simplicity - each step of the algorithm performs one logical step
in solving the problem.
- Precision - each step of the algorithm is unambiguous in meaning.
- Comprehensibility - the algorithm is easy to read and understand.
- Abstraction - presents the solution steps precisely and
concisely without referring to low-level (program code) details.
- Efficient - Gives results rapidly based on the problem size;
does not waste any space or time.
- Easy to Implement - relatively easy to translate into a programming language.