## Fifth Semester | Third Year | Tribhuvan University

Old Question Collection | Question Bank

Design and Analysis of Algorithm(daa), Year: 2069

Computer Science and Information Technology (CSc. 303)

**Download Question Paper File**

[File Type: PDF | File Size: 512 KB | Download]

Candidates are required to give their answer in their own words as far as practicable.

**The figures in the margin indicate full marks.**

** Attempt all the questions**

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

`for(i=1 ; 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;

}**(8)** - What do you mean by recurrence relation? Estimate the running time of algorithm given by following recurrence relations using master method.

a. T(n) = 4 T (n/2) + n^{3}

b. T(n) = 2 T (n/2) + n

c. T(n) = 3 T (n/4) + n log n**(8)** - Explain the quick sort algorithm with its complexity analysis. How randomized quick sort works efficiently even for worst case.
**(6+2)** - Define order statistics. Write an algorithm that is able to select i
^{th}largest element from an unordered list in linear time and analyze for its complexity.**(2+6)** - Sketch the Prim’s algorithm for computing MST of a graph and analyze its complexity. Also trace the algorithm for the following graph.
**(2+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 }

Find the optimal job lists that can be executed in sequence with in their deadlines so as to maximize the profits.**(4+4)** - Explain and analyze the Floyd’s warshall algorithm for all pair shortest path problem. Trace the algorithm for the following graph.
**(4+4)** - 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.
**(2+6)** - Explain about class P, class NP and NP complete with suitable examples.
**(8)** - Explain the Gram’s scan algorithm with example to compute the convex hull of the set of points in 2D.
**(8)**