IGNOU MCA MCS-031 Design and Analysis of Algorithms SOLVED ASSIGNMENTS 2014-2015

IGNOU SOLVED ASSIGNMENTS FOR 1st Semester MCS-031 2014-2015  Design and Analysis of Algorithms

Ans: Comming soon. Now follow - How to write Best ASSIGNMENTS / ANSWERS by Yourself

Q.1. a) Discuss briefly the five essential attributes of an algorithm.

b) Write a recursive procedure for the product of first n natural numbers.

  Then explain how your algorithm computes product of first 6 natural numbers.

c) Arrange the following growth rates in increasing order: O (n (log n)2 ), O ( (35)n ) , O (35n2 +11), O (1), O (n log n)

d) In respect of understanding a problem for solving it using a computer, explain „analysing the problem‟ step.

Q.2. Suppose that instead of binary or decimal representation of integers, we have a representation using 5 digits, viz. 0,1,2,3,4, along with 5‟s complement, representation of integers. For example, the integer 147 is represented as (01042)5 = (in decimal) + 1. 53 + 0. 52 + 4. 51 + 2. 30 , where the leading zero indicates positive sign.

And the integer ( − 147 ) in 5’s complement is represented by 13403, the leading 1 indicates negative sign. The other digits, except the right-most, in the representation of ( − 147) are obtained by subtracting from 4 the corresponding digit in 147‟s representation, and then adding 1 (the representation of –147 is obtained as 13402 + 00001).

Write a program for the arithmetic (negation of an integer, addition, subtraction and multiplication of two integers) of integers using 5‟s complement representation. The program should include a procedure for calculating each of negation of an integer, addition,  subtraction and multiplication of two integers. The integers will use 8 5-digit positions, in which the left-most position will be used for sign.
Using your program find the 5-digit representation of each of the decimal numbers/ expression: 345, − 297, 18 and ((345 − 297) * 18)

Q.3. a) Write a short note on each of the following: i) Best case analysis ii) amortized analysis

b) Using one-by-one (i) insertion sort (ii)heap sort and (iii) merge sort, sort the following sequence in increasing order and analyze (i.e., find number of comparisons and assignments in each of ) the algorithm: 84, 35, 47, 18, 82, 17, 56, 40, 12 ,67

Q.4. a) The following pseudo-code is given to compute ( ab )mod n, where a, b and n are positive integers. Trace the algorithm to compute 11362 mod 561

MODULAR-EXPONENTION (a, b, n)
Let (bk, bk − 1, … , b0) be binary representation of b, in which bk=1 1. d  a; d stores partial results of (ab ) mod n 2. for i  ( k –1) downto 0 3. do 4. d  (d . d) mod n 5. if bi = 1 6. d  (d . a) mod n 7. end-do 8. return d.

Note: The above algorithm is a sort of implementation of the ideas explained in Section 1.9 of Block2 of MCS- 031, and should be learned along with Section 1.9.

b) Explain the essential idea of Dynamic Programming. How does Dynamic Programming differ from Divide and conquer approach for solving problems?

Q.5. a) For the graph given in Figure below, use (i) BFS (ii)DFS to visit various vertices. The vertex B is taken as the starting vertex and, if there are more than one vertices adjacent to a vertex, then the adjacent vertices are visited in lexicographic order.

b) In context of graph search, explain the minimax principle.

Q.6. a) Is there a greedy algorithm for every interesting optimization problems? Justify your Claim.

b) Apply each of (i) Prim‟s and (ii)Kruskal‟s algorithms one at a time to find minimal spanning tree for the following graph

Q7. Write note on each of the following: i) Unsolvability/ undecidability of a problem ii) Halting problem iii) Reduction of a problem for determining decidability iv) Rice theorem v) Post correspondence problem vi) NP-complete problem vii) K-colourability problem viii) Independent set problem