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

- Write down the formal definition of big-oh, big-omega and big-thita notation with examples. (8)
- 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) - Make a tight big-O analysis of following code segment.

`void main( )`

(8)

{

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

} - What is linear data structure? Write down the algorithm of heap sort and find its complexity analysis. (2+6)
- What is divide and conquer technique? Using this technique. Write an algorithm of quick sort then analyze it. (2+6)
- What are the advantages of dynamic programming? Find Longest Common Subsequence (LCS) between ”abbaab” and ”aabaabb”. (2+6)
- What is shortest path problem? Explain Dijkstra’s algorithm for shortest path problem. (2+6)
- 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)
- Define the terms ”Class P”, ”Class NP” and ”NP Completeness”. (8)
- What is the concept of randomized algorithm? Write an algorithm of approx-vertex-cover problem and analyze it. (2+6)

(Visited 154 times, 1 visits today)