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

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

daa 2067 question paperFifth Semester | Third Year | Tribhuvan University
Old Question Collection | Question Bank
Design and Analysis of Algorithm(daa), Year: 2067
Computer Science and Information Technology (CSc. 303)

Download Question Paper File
[File Type: PDF | File Size: 424 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. Explain Worst case, best case and average case of algorithm analysis with an example. (8)
  2. What is recurrence relation? Find big-O of following recurrence using recurrence tree method.
    T(n) = T(n/2) + 1      n > 1
    = 1                        n = 1                                         (2+6)
  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 = 0; i < n; i++)
    a[i] = i;
    b[i] = i*i;
    c[i]= -i;
    for (j = 0; j < m; j++)
    printf(''%d\t %d\t %d\n'', a(j), b(j), c(j);
    } }
  4. What is order statistics? How can you devise an algorithm that guarantee the selection of ith order statistics in linear time? Write the algorithm of it and analyze it. (1+3+4)
  5. What is the main idea of randomized algorithm? Write an algorithm quick sort and analyze it. (2+6)
  6. Define greedy paradigm. How can you define Huffman algorithm is greedy algorithm? Explain. (2+6)
  7. What is minimum spanning tree? Write the execution trace of the following graph to construct minimum spanning tree by prime algorithm.daa_2067.qn.7
  8. Explain Graham’s Scan algorithm to compute convex hull. (8)
  9. Define the terms ”Class P”, ”Class NP” and ”NP – Completeness”. (8)
  10. What is the concept of dynamic programming? Find the longest common subsequence (LCS) between ”XMJYAUZ” and ”MZJAWXU”. (2+6)
(Visited 98 times, 1 visits today)

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