Algorithm - Introduction
Computers are used for problem solving, automating and processing of data and information. The computer does these, based on the instructions it receives through various programming languages such as C, C++ or a variety of others. The set of instructions given to the computer to perform a job is called a program which is nothing but an algorithm expressed in language known as programming language. Thus, writing a program requires knowledge of the programming language. However, the set of instructions can also be expressed independent of any programming language which is called algorithm. There are various explanations of algorithm. As per Dromey, "algorithm consists of a set of explicit and unambiguous finite steps which, when carried out for a given set of initial conditions, produce the corresponding output and terminate in a finite time."
To understand the concept of algorithm, let us consider a simple example of real life problem solving. To look for the meaning of a word from a dictionary, one wouldn't go to first word in the dictionary and search till the required word is found. An algorithm can be applied by taking advantage of alphabetical order of words in dictionary. The steps followed to search for a word are:
1) Go to page that has the starting letter of the word
2) Search for the subsequent letters till the exact word is found
This kind of algorithmic process can be used for problem solving using computers.
To obtain solution to a problem through the computer, usually we have to provide the computer program with input or data. The program then takes this input and manipulates it according to its instructions and eventually produces an output which represents the computer solution to the problem.
Algorithms are written in a unique language and style. The way any language is used to write an algorithm is its representation. A natural language like English can be used to write algorithms. Let us take a simple problem of adding numbers from 1 to 'n' (that is if 'n'= 4, then it should add 1+2+3+4). If the algorithm is written for this problem in natural language, it would read as follows:
Initially set the sum value to 0 and count to 1. Accept 'n' as input from the user. If the value of 'n' is 0 then print the value of sum as 0. If the value is greater than 0 then add the count till it reaches the input
value 'n'. Each time after addition increase the count value.
It can be noticed that even for this small problem, the natural language is unstructured. In case of huge problem, the natural language algorithm will be difficult to understand while programming.
The next choice of writing the algorithm may be in formal languages like C, C++, etc. But, at the initial phase of design one would be thinking and writing at a highly abstract level. Using a programming language forces the use of punctuations and syntax properly which cannot be done at this early stage of design. The syntax of the algorithm should be free of the programming language.
A language between a natural and formal language is necessary to write algorithms efficiently. There is a notation called pseudo code which is most commonly used to write algorithms. It is simple, readable and has no grammatical rules. As it has a very well defined structure it is easy to visualize the organization of statements. As pseudo code resembles many of the programming languages, it is easy to convert the algorithm to programs.
Algorithm for the above problem in pseudo code is as follows:
Step 1 Initialize the variable Count to 1 for counting the addition.
Step 2 Initialize the variable Sum to 0 to store the sum.
Step 3 Get the input value 'Num' for number of times sum has to be performed.
Step 4 Add Count with Sum and assign it to Sum
Step 5 Increase Count to next value.
Step 6 Repeat steps 4 and 5 till Count exceeds the value of Num.
There are pseudo code constructs for three types of algorithmic operations viz. sequential, conditional and iterative.
A sequential instruction performs a single well defined task. When the task is finished, the algorithm moves on to the next operation.
In pseudo code computation, input and output are the basic sequential operations. The instructions performing computations look like;
Set value of "variable" to" arithmetic expression"
This operation says that, evaluate the "arithmetic operation" and store the result in the indicated" variable".
In our above example "Add Count with Sum and assign it to Sum" is the computational statement. Add count with Sum is arithmetic expression and assign it to Sum explains that the result has to be stored in the variable Total itself.
Eg of computational operations
Set the value of Area to (Ðr2)
Set the value of c to (a+b)
Input operations get the value from outside to the computational part. Input statement look like;
Get value for variable1, variable2
Eg. Get value of customer name, account_ number.
Output operations send the output value for display. This then looks like
Print value of variable1, variable2
Eg. Print the value of Area
The conditional statements allow the algorithm to ask a question and based on the answer, and perform certain set of operations through statements. Most commonly used conditional construct is if/then/else.
Take an example of displaying greater value among two input values. The algorithm for that is;
Step 1 Get value of 'a' and 'b'
Step 2 If 'a' is greater than 'b' then display 'a'
Step 3 If 'b' is greater then 'a' then display 'b'
The structure of steps 2 and 3 is as follows:
If a >b then
So the algorithm can be written as:
Step 1 Get value of a and b
Step 2 If a >b then
In general, the structure of conditional operations appears as:
If true/false condition is true then
First set of operations
Next set of operations
Basically if/then/else operations allow selecting one or two alternatives.
Iterative operation is used to repeat a block of statements in many situations. In the earlier example of adding, n numbers requires adding each number from 1 to input value with previous sum.
Step 1 Initialise the variable Count to 1 for counting the addition.
Step 2 Initialise the variable Sum to 0 to store the sum.
Step 4 Repeat steps 5 and 6 till Count exceeds the value of Num.
Step 5 Add Count with Sum and assign it to Sum
Step 6 Increase Count to next value.
Step 4 above is a loop which will terminate when the count exceeds the value of input number. The statements under the loop are called body of the loop and condition is called termination condition. Most commonly used loop structure is while/do. The basic structure of while/do loop looks like this:
While true/false condition remains true do
End of the loop
Let us consider the example of calculating the sum of square of first ten numbers
i = 1;
sum = 0;
while i <= 10
sum = sum + (i*i);
i = i+1;
Let us consider another example of a program for calculating factorial for a given number "n" as an example for iterative operation.
int i, n;
int factor, nfactorial;
printf("Enter the number for which factorial should be
for (i =1 ; i<=n;I++)
factor = I * factor;
nfactorial = factor;
printf(" Factorial value is : %d", nfactorial);
Here the factorial calculation is done for value from 1 to n iteratively.
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!