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

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

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

Download Question Paper File
[File Type: PDF | File Size: 409 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. Write down the formal definition of big-oh, big-omega and big-thita notation with examples. (8)
  2. What is recurrence relation? Find the big-O of following recurrence by using recurrence tree method.
    T(n) = 2T(n/2) + n                         n>1
    =1                                              n=1                                               (2+6)
  3. Make a tight big-O analysis of following code segment.
    void main( )
    {
    int m, n, i, j, a[ }, b[ };
    printf(''Enter value of m and n'');
    scanf(''%d %d', &m, &n);
    for (i = 1,I <= m, i++)
    a[i] = i*i;
    for (j=1, j<=n; j++)
    b[j] = -j;
    for (i = 1,I <= m, i++)
    printf(''%d'', a[i]);
    for (j=1, j<=n; j++)
    printf(''%d'', b[j]);
    }
    (8)
  4. What is linear data structure? Write down the algorithm of heap sort and find its complexity analysis. (2+6)
  5. What is divide and conquer technique? Using this technique. Write an algorithm of quick sort then analyze it. (2+6)
  6. What are the advantages of dynamic programming? Find Longest Common Subsequence (LCS) between ”abbaab” and ”aabaabb”. (2+6)
  7. What is shortest path problem? Explain Dijkstra’s algorithm for shortest path problem. (2+6)
  8. What is left turn and right turn? Give an algorithm for finding two lines segments intersect or not by using left turn and right turn. Does this algorithm works for all cases? Justify with example. (2+6)
  9. Define the terms ”Class P”, ”Class NP” and ”NP Completeness”. (8)
  10. What is the concept of randomized algorithm? Write an algorithm of approx-vertex-cover problem and analyze it. (2+6)
(Visited 58 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