Design and Analysis of Algorithms 2069

Attempt all questions.

1.  Use RAM model to estimate the big-oh of the running time for following code segment.

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

                             small pos = i;

                                    smallest = Array[small pos];

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

                                    if(Array[j]<smallest){

                                                small pos = j;

                                                smallest=Array[small pos];

                                    }

            }

            Array[small pos]=Array[i];

            Array[i] = smallest;

2.  What do you mean by recurrence relation? Estimate the running time of algorithm given by following recurrence relations using master method.

3.  Explain the quick sort algorithm with its complexity analysis. How randomized quick sort works efficiently even for worst case.

4.  Define order statistics. Write an algorithm that is able to select i^th largest element from an un-ordered list in linear time and analyzer for its complexity.

5.  Sketch the Prim’s algorithm for computing MST of a graph and analyze its complexity. Also trace the algorithm for the following graph.

6.  Give the job sequencing algorithm with deadlines. You have given 5 jobs with profit pi and deadline di as

job i = { 1, 2, 3, 4, 5}

pi = {20, 10, 5, 15, 1}

di = { 2, 1, 3, 2, 3}

7.  Explain and analyze the Floyd’s warshall algorithm for all pair shortest path problem. Trace the algorithm for the following graph.

8.  What do you mean by left turn and right turn for given three points in 2D? Explain the method for computing the intersection of two line segment efficiently.

9.  Explain about Class P, Class NP and NP-complete with suitable examples.

10. Explain the Gram’s scan algorithm with example to compute the convex hull of the set of points in 2D.