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

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

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); } } ```(8)
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.
(2+6)
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)

Posted By : | Comment RSS | Category : Fifth Semester, Old Question Collection
Tag :
Subscribe Notes
Check your Email Inbox after submitting.

### Recent Entry

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