Design and Analysis of Algorithm (daa)| BSc.CSIT (TU) Question Paper 2068 | Fifth Semester 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)

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 199 times, 1 visits today)

Posted By : | Comment RSS | Category : Fifth Semester, Old Question Collection
Community | Toolbar | Android App | Founder/Developer : Hari Prasad Chaudhary | CSIT Portal Manager : Digvijay Chaudhary