Algorithms

An algorithm – step by step recipes that tell a computer or a person what to do in certain situations. As far as programming field is concerned an algorithm is used to refer to some fairly well-known recipes that have been thoroughly tested in practice. But before the discussion of particular algorithms, one must know what an algorithm is. Actually the word algorithm is derived from the name of a Persian mathematician, Abu Ja’far Mohammed ibn Musa al Khowarizmi, who lived in the Middle ages, around 800 C.E. An algorithm is a finite set of instructions to be carried out in order to solve a given problem. Each instruction of the algorithm tells what task is to be performed by it. In addition every algorithm must satisfy the following criteria in order to work it properly:

1. every algorithm is supposed to receive zero or more values as an external input
2. every algorithm is supposed to produce at least one output
3. each instruction must be very clear and unambiguous; there can be no ambiguity about what is supposed to be done at any point in the running of the application
4. the algorithm must terminate after a finite number of steps; that is it must be efficient
5. It must produce the desirable results at least under any foreseeable or probable conditions of use, that is it must be effective

An algorithm can be described in many ways. An algorithm can be expressed in English-like language, called pseudo code, in a programming language such as Pascal or C, or in the form of a flow chart. In this section we will study how to express an algorithm in pseudo code.

Let we want to find out the largest number among three numbers, A, B and C. An algorithm for this problem can be constructed as:

Algorithm : Large

Now let us study the execution of this algorithm. Execution of the algorithm starts from the step-1 and continues from there in sequential order unless it is terminated. In first step we receive the value in three variables A, B and C. In step-2 we set large = A. In step-3 we compare the value of large with B. If the value of large is less than B then we assign the value of B to large; otherwise it goes to step-4. In step-4 we compare the value of large with C. If the value of large is less than C then we assign the value of C to large; otherwise it goes to step-5. In step-5 we print the value of large on the screen and finally in step-6 the algorithm is terminated.

Let us see another algorithm, which searches an element ‘item’ from a set of ‘N’ number of elements. We begin searching with the very first element by comparing ‘item’ with the first element. If it matches with the first element then it displays the message – the search is successful along with its position and the control is returned back; otherwise the second element is being taken. Then the second element is compared with the ‘item’. If it matches with the second element then it displays the message – the search is successful along with its position and the control is returned back; otherwise the third element is being taken. And this process goes on until the search is successful or the entire set gets exhausted.

The formal representation of the algorithm is given below:

Algorithm : Search

Similarly we can write any algorithm for any type of problem. The algorithms that we have seen so far has its own input and output statements. When these algorithms are implemented in any programming language then they can run on its own. But in some cases when our problem is too complex then it is not a great idea to write a single algorithm for such a complex problem. The possible solution to such problem is to divide it into smaller manageable independent subproblems. And once all these subproblems are designed, they can be integrated as a solution to overall problem. The algorithms to such subproblems are called as subalgorithms. These subalgorithms when implemented in any programming language can’t run on its own, rather they are being called by the main algorithm or by any other subalgorithm. In last example, we have assumed that there is an ‘N’ number of elements in the array ‘A’ and we have to find out whether a given element is an array or not.

Now let us slightly modify it. Let we write a subalgorithm which just returns the location of the item if the search is successful; otherwise returns a value –1.

Algorithm – SearchElement

The problem of finding an element in a given array can be solved as:

Algorithm – Search

Efficiency of Algorithms

One of the important features of an algorithm is that it should be as efficient as possible. Every algorithm uses some of the computer resources to complete its task. The resources most important in the relation to efficiency are central processing unit and internal memory. This means that an algorithm should run as fast as possible and require as little computer memory as possible because of the high cost of computing resources. Note that there is no clear cut methods of designing efficient programs, but we can inculcate some good programming habits which are very useful in designing efficient algorithms, as follows:

1. One must avoid redundant computations, specially within a loop which is to be executed many times. To understand this point, let we have following loop:

for (i=1; i<= 100; i++)
{
for (j=10; j<= 50; j++)
{
sum = (x*x*x*x + y*y) * i + z*z*j;
printf(“%d\n”, sum)
}
}

This loop unnecessarily computes the (x*x*x*x + y*y) and z*z repeatedly, which can be overcome by computing them before execution of the loop.

1. One must terminate the algorithm as soon as the problem has been solved. It means that there is no need to compute unnecessary instruction. Let we want to search a name “Mohan” sequentially in an alphabetically ordered list of names. In such case our algorithm must terminate if the point in the list was reached where the given name is found or the name could not occur later. Thus the algorithm must terminate for a name that have encountered later that “Mohan” or “Mohit” as there is no need to move further.
2. One must pay more attention towards more frequently used routines rather than routines that are called once in a program. Of course algorithm efficiency is important, but it is not equally important in every situation. For example, let it displays some text on the computer screen then it is silly to waste too much time worrying about how efficiently you do it.
3. One must efficiently write routines that handle user input and output.

There are some of the tips to achieve efficient programs. There is generally trade-off between the storage space and the efficiency to improve the performance of an algorithm. It all depends upon the circumstances in which it is intended to work.