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.

daa question paper 2069Fifth 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

  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)

Posted By : Digvijay | Comment RSS | Category : Fifth Semester, Old Question Collection
Tag :

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

Wordpress DMCA
Community | Toolbar | Android App | Founder/Developer : Hari Prasad Chaudhary | CSIT Portal Manager : Digvijay Chaudhary