Characteristics of an Algorithm

While designing an algorithm as a solution to a given problem, we must take care of the following five important characteristics of an algorithm:

1. Finiteness

An algorithm must terminate after a finite number of steps and further each step must be executable in finite amount of time. In order to establish a sequence of steps as an algorithm, it should be established that it terminates (in finite number of steps) on all allowed inputs.

2. Definiteness (no ambiguity)

Each step of an algorithm must be precisely defined; the action to be carried out must be rigorously and unambiguously specified for each case. Through the next example, we show how an instruction may not be definite.
Example: Method which is effective (to be explained later) but not definite.
The following is a program fragment for the example method:
x ← 1
Toss a coin,
If the result is Head then x ←3 else x ← 4
{In the above, the symbol ‘←’ denotes that the value on its R.H.S is assigned to the variable on its L.H.S. Detailed discussion under (i) of Section 1.6.1}
All the steps, like tossing the coin etc., can be (effectively) carried out. However, the method is not definite, as two different executions may yield different outputs.

3. Inputs

An algorithm has zero or more, but only finite, number of inputs.
Examples of algorithms requiring zero inputs:

1. Print the largest integer, say MAX, representable in the computer system being used.
2. Print the ASCII code of each of the letter in the alphabet of the computer system being used.
3. Find the sum S of the form 1+2+3+…, where S is the largest integer less than or equal to MAX defined in Example (i) above.

4. Output

An algorithm has one or more outputs. The requirement of at least one output is obviously essential, because, otherwise we cannot know the answer/solution provided by the algorithm.

The outputs have specific relation to the inputs, where the relation is defined by the algorithm.

5. Effectiveness

An algorithm should be effective. This means that each of the operation to be performed in an algorithm must be sufficiently basic that it can, in principle, be done exactly and in a finite length of time, by a person using pencil and paper. It may be noted that the ‘FINITENESS’ condition is a special case of ‘EFFECTIVENESS’. If a sequence of steps is not finite, then it cannot be effective also.

Read More

Difference between Problems and Instances

The difference between the two concepts viz., ‘problem’ and ‘instance’, can be understood in terms of the following example. An instance of a problem is also called a question. We know that the roots of a general quadratic equation

 (1)

are given by the equation

 (2)

where a, b, c may be any real numbers except the restriction that a ≠ 0.

Now, if we take a = 3, b = 4 and c = 1, we get the particular equation

 (3)

Using (2), the roots of (3) are given by

With reference to the above discussion, the issue of finding roots of the general quadratic equation ax2 + bx + c = 0, with a ≠ 0 is called a problem, whereas the issue
of finding the roots of the particular equation

is called a question or an instance of the (general) problem.

In general, a problem may have a large, possibly infinite, number of instances. The above-mentioned problem of finding the roots of the quadratic equation

with a ≠ 0, b and c as real numbers, has infinitely many instances, each obtained by giving some specific real values to a, b and c, taking care that the value assigned to a is not zero. However, all problems may not be of generic nature. For some problems, there may be only one instance/question corresponding to each of the problems. For example, the problem of finding out the largest integer that can be stored or can be arithmetically operated on, in a given computer, is a single-instance problem. Many of the interesting problems like the ones given below, are just single-instance problems.

Read More

Euclid’s Algorithm for Finding G.C.D. of two Natural Numbers m & n

E1. {Find Remainder}. Divide m by n and let r be the (new) remainder {r have 0≤r<n}
E2. {Is r zero?} If r = 0, the algorithm terminates and n is the answer. Otherwise,
E3. {Interchange}. Let the new value of m be the current value of n and the new value of n be the current value of r. Go back to Step E1.

The termination of the above method is guaranteed, as m and n must reduce in each iteration and r must become zero in finite number of repetitions of steps E1, E2 and E3.

The great Greek mathematician Euclid sometimes between fourth and third century BC, at least knew and may be the first to suggest, the above algorithm. The algorithm is considered as among the first non-trivial algorithms. However, the word ‘algorithm’ itself came into usage quite late. The word is derived from the name of the Persian mathematician Mohammed al-Khwarizmi who lived during the ninth century A.D. The word ‘al-khowarizmi’ when written in Latin became ‘Algorismus’, from which ‘algorithm’ is a small step away.

In order to familiarise ourselves with the notation usually used to express algorithms, next, we express the Euclid’s Algorithm in a pseudo-code notation which is closer to a programming language.

Algorithm GCD-Euclid (m, n)

{This algorithm computes the greatest common divisor of two given positive integers}
begin {of algorithm}
while n ≠ 0 do
begin {of while loop}
r ← m mod n;
{a new variable is used to store the remainder which is obtained by dividing m by n, with 0≤ r < m}
m ←n;
{the value of n is assigned as new value of m; but at this stage value of n remains unchanged}
n← r;
{the value of r becomes the new value of n and the value of r remains unchanged}
end {of while loop}
return (n).
end; {of algorithm}

Read More

Notation for expressing algorithms

This issue of notation for representations of algorithms will be discussed in some detail, later. However, mainly, some combinations of mathematical symbols, English phrases and sentences, and some sort of pseudo-high-level language notations, shall be used for the purpose.

Particularly, the symbol ‘←’ is used for assignment. For example, x←y + 3, means that 3 is added to the value of the variable y and the resultant value becomes the new value of the variable x. However, the value of y remains unchanged.

If in an algorithm, more than one variables are required to store values of the same type, notation of the form A[1..n] is used to denote n variables A[1], A[2], … A[n].

In general, for the integers m, n with m ≤ n, A [m..n] is used to denote the variables A[m], A[m+1], …, A[n]. However, we must note that another similar notation A[m, n] is used to indicate the element of the matrix (or twodimensional array) A, which is in mth row and nth column.

Role and Notation for Comments

The comments do not form that part of an algorithm, corresponding to which there is an (executable) action in the process. However, the comments help the human reader of the algorithm to better understand the algorithm. In different programming languages, there are different notations for incorporating comments in algorithms. We use the convention of putting comments between pair of braces, i.e., { } . The comments may be inserted at any place within an algorithm. For example, if an algorithm finds roots of a quadratic equation, then we may add the following comments, somewhere in the beginning of the algorithm, to tell what the algorithm does:

{this algorithm finds the roots of a quadratic equation in which the coefficient of x2 is assumed to be non-zero}.

Read More