## Algorithm (Pseudocode)

• Procedure - a set of steps required to solve a problem.
• Algorithm - a procedure which terminates on ALL inputs.
• Pseudocode - a high-level English-like language used to define an algorithm.

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 problem:

Algorithm Euclid.
```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:

```main()
{int a,b,x,y;

scanf("%d%d",&a,&b);
x=a;
y=b;

do
{if(x>y) x=x-y;
else if(x<y) y=y-x;
}
while(x!=y);

printf("gcd=%d\n",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 uninteresting, details 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.