19SOEIT13007 DESIGN AND ANALYSIS OF ALGORITHM
6IT
Assignment-1
1. What is an algorithm? Explain various properties of an algorithm.
Ans.
An algorithm is an effective, efficient and best method which can be used to
express solution of any problem within a finite amount of space and time and
in a well-defined formal language.
Starting from an initial state the instructions describe a process or
computational process that, when executed, proceeds through a finite number
of well-defined successive states, eventually producing "output" and
terminating at a final ending state.
An algorithm is a finite set of instructions that, if followed, accomplishes a
particular task.
An algorithm is a sequence of computational steps that transform the input
into a valuable or required output.
Step by step procedure for solving any problem is known as algorithm.
Any special method of solving a certain kind of problem is known as
algorithm.
All Algorithms must satisfy the following criteria –
1) Input
There are more quantities that are extremely supplied.
2) Output
At least one quantity is produced.
3) Definiteness
Each instruction of the algorithm should be clear and unambiguous.
4) Finiteness
The process should be terminated after a finite number of steps.
5) Effectiveness
Every instruction must be basic enough to be carried out theoretically or by
using paper and pencil.
Ruturajsinh Gohil 1
19SOEIT13007 DESIGN AND ANALYSIS OF ALGORITHM
6IT
Properties of Algorithm:
1) Non Ambiguity
Each step in an algorithm should be non-ambiguous. That means each instruction
should be clear and precise. The instruction in any algorithm should not denote
any conflicting meaning. This property also indicates the effectiveness of
algorithm.
2) Range of Input
The range of input should be specified. This is because normally the algorithm is
input driven and if the range of input is not being specified then algorithm can go
in an infinite state.
3) Multiplicity
The same algorithm can be represented into several different ways. That means
we can write in simple English the sequence of instruction or we can write it in
form of pseudo code. Similarly, for solving the same problem we can write
several different algorithms.
4) Speed
The algorithm is written using some specified ideas. Bus such algorithm should be
efficient and should produce the output with fast speed.
5) Finiteness
The algorithm should be finite. That means after performing required operations it
should be terminate.
Ruturajsinh Gohil 2
19SOEIT13007 DESIGN AND ANALYSIS OF ALGORITHM
6IT
2. Give the recursive algorithm to find Fibonacci sequence. Give its
complexity.
Ans.
Algorithm:
#include<stdio.h>
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}
Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.[O (2n)]
Extra Space: O(n) if we consider the function call stack size, otherwise O(1).
Ruturajsinh Gohil 3
19SOEIT13007 DESIGN AND ANALYSIS OF ALGORITHM
6IT
3. Give the algorithm to solve Tower of Hanoi Problem. Comment on the
complexity of the algorithm.
Ans.
Algorithm:
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi (disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
Analysis of Recursion:
We have seen that the minimum number of moves required for a Towers of Hanoi
instance with n disks is 2n-1.This is O(2n) and grows very fast as increases. To get a
sense of how bad this time complexity is, suppose it takes us one second to move one
disk from a rod to another rod. Then to solve an instance with 64 disks it will take us
about 585 billion years!
Ruturajsinh Gohil 4
19SOEIT13007 DESIGN AND ANALYSIS OF ALGORITHM
6IT
Ruturajsinh Gohil 5
