IGNOU Question Paper Solutions/MCA/Semester 3/MCS-031 Design and Analysis of Algorithms/December 2009

1. (a) (i) Write Euclid’s Algorithm to find GCD of two positive integers.

Ans. GCD(n,m),if n>m GCD (m,n) = m,if n=0 GCD(n,MOD(M,N),oterwise

(ii) Differentiate between ‘problem’ and ‘instance’ with an example each.

Ans. A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance. and should not be confused with the problem itself. In computational complexity theory. A problem refers to the abstract question to be solved In contrast. An instance of this problem. For example. Consider the problem of primality testing. The instance is a number and the solution is “yes” if the number is prime and “no” otherwise. Alternately. the instance is a particular input to the problem, and the solution is the output corresponding to the given input.

To further highlight the difference between a problem and an instance. consider the following example.

Problem of multiplying two positive integers.

There is a general solution to the problem of multiplying two positive integers. We say that (912,2436)is an instance of this problem.

However, multiplying – 12 by 8745 is not an instance of the above problem as -12 is a negative number.