Design and Analysis of Algorithms 2068

Attempt all questions.

1.  Write down the formal definition of big-oh, big-omega and big-theta notation with examples.

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

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=1;i<=m;i++)

      a[i]=i*i;

   for(j=1;j<=n;j++)

      b[j]=-j;

   for(i=1;i<=m;i++)

      printf(“%d”, a[i]);

   for(j=1;j<=n;j++)

      printf(“%d”, b[j]);

4.  What is linear data structure? Write down the algorithm of heap sort and find its complexity analysis.

5.  What is divide and conquer technique? Using this technique. Write an algorithm of quick sort then analyze it.                                                                                                        

6.  What are the advantages of dynamic programming? Find Longest Common Subsequence (LCS) between “abbaab” and “aabaabb”.                                                                     

7.  What is shortest path problem? Explain Dijkstra’s algorithm for shortest path problem. 

8.  What is left turn and right turn? Give an algorithm for finding two lines segments intersect or not by using left turn and right turn. Does this algorithm works for all cases? Justify with example.

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

10.  What is the concept of randomized algorithm? Write an algorithm of approx..-vertex-cover problem and analyze it.