Design and Analysis of Algorithms 2067

Attempt all questions.

1.  Explain worst case, best case and average case of algorithm analysis with an example. [8]

2.  What is recurrence relation? Find big-O of following recurrence using recurrence tree method.      [2+6]

3.  Make a tight big-O analysis of following code.

void main()

{

   int m, n, i, j, a[], b[], c[];

   printf(“Enter value of m and n”);

   scanf(“%d%d”,&m,&n);

   for(i=0;i<n;i++)

   {

      a[i]=i;

      b[i]=i*i;

      c[i]=-i;

   }

   for(j=0;j<m;j++)

   {

      printf(“%d\\t%d\\t%d\\n”,a(j), b(j), c(j);

   }

}                                                                                                                                   [8]

4.  What is order statistics? How can you devise an algorithm that guarantee the section of i^th order statistics in linear time? Write the algorithm of it and analyze it.                   [1+3+4]

5.  What is the main idea of randomized algorithm? Write an algorithm quick sort and analyze it.                                                                                                                       [2+6]

6.  Define greedy paradigm. How can you define Huffman algorithm is greedy algorithm? Explain.

7.  What is minimum spanning tree? Write the execution trace of the following graph to construct minimum spanning tree by prims algorithm.                                                                   

8.  Explain Graham’s scan algorithm to compute convex hull.

9.  Define the terms “Class P”, “Class NP” and “NP-completeness”. 

10.  What is the concept of dynamic programming? Find the longest common subsequence (LCS) between “XMJYAUZ” and “MZJAWXU”. [2+6]