DAA MID-1 IMP QUESTIONS

1.Define an algorithm?Describe the characteristics of an algorithm?

2.Define time and space complexity?with the help of mathematical formula by taking an example-

Calculate time and space req.of an algorithm?

3.Describe diff notations used to represent the complexities?

4.write an algorithm to find largest element in an array of n-elements and find its time complexity?

5.derive the complexity for general divide and conquer algorithm?

6.Explain strassen`s matrix multiplication concept? And also derive the time complexity for strassen`s algorithm?

7.Explain how a problem is solved using divide and conquer strategy?

8.Trace the quick sort algorithm to sort the list consists of elements {C,O,L,L,E,G,E} in an alphabetical order

9.a)Explain when the quick sort is preferred to an merge sort and viceversa

b)what is the principle of partioning in quick sort?give an example

10.Find the optimal solution to the knapsack instance

n=7 , m=15 , profits {p1,p2,p3,p4,p5,p6,p7}={10,5,15,7,6,18,3}

and weights {w1,w2,w3,w4,w5,w6,w7}={2,3,5,7,1,4,1}

11.Write an algorithm to find articulation point?

12.Write an algorithm to find collapsing rule?

13.solve the following recurrence relation

T(n)=a n=1

=2T(n/2) n>1

14.consider the following graph and find the shortest path as a vertex=’2’ as source

Fig: SARAJ SAHANI Page num:261 (a)

15.Assume that we have started with a forest of trees each having 1-node.Let ‘T’ be the tree with m-nodes created as a result of sequence of unions.each perform using weighted union .

Prove height of ‘T’ IS NO greater than (logn+1)