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

**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**

- Explain Worst case, best case and average case of algorithm analysis with an example. (8)
- 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) - Make a tight big-O analysis of following code.

`void main( )`

(8)

{

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

} } - What is order statistics? How can you devise an algorithm that guarantee the selection of i
^{th}order statistics in linear time? Write the algorithm of it and analyze it. (1+3+4) - What is the main idea of randomized algorithm? Write an algorithm quick sort and analyze it. (2+6)
- Define greedy paradigm. How can you define Huffman algorithm is greedy algorithm? Explain. (2+6)
- What is minimum spanning tree? Write the execution trace of the following graph to construct minimum spanning tree by prime algorithm.

(2+6) - Explain Graham’s Scan algorithm to compute convex hull. (8)
- Define the terms ”Class P”, ”Class NP” and ”NP – Completeness”. (8)
- What is the concept of dynamic programming? Find the longest common subsequence (LCS) between ”XMJYAUZ” and ”MZJAWXU”. (2+6)

(Visited 88 times, 1 visits today)