# Design and Analysis of Algorithm (daa)| BSc.CSIT (TU) Question Paper 2069 | Fifth Semester

Download our Android App from Google Play Store and start reading Reference Notes Offline.

## 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)

[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

1. 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)
2. 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) + n3
b. T(n) = 2 T (n/2) + n
c. T(n) = 3 T (n/4) + n log n                                             (8)
3. Explain the quick sort algorithm with its complexity analysis. How randomized quick sort works efficiently even for worst case. (6+2)
4. Define order statistics. Write an algorithm that is able to select ith largest element from an unordered list in linear time and analyze for its complexity. (2+6)
5. 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)
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)
7. Explain and analyze the Floyd’s warshall algorithm for all pair shortest path problem. Trace the algorithm for the following graph. (4+4)
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. (2+6)
9. Explain about class P, class NP and NP complete with suitable examples. (8)
10. Explain the Gram’s scan algorithm with example to compute the convex hull of the set of points in 2D. (8)
(Visited 136 times, 1 visits today)

Posted By : | Comment RSS | Category : Fifth Semester, Old Question Collection
Subscribe Notes