TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2082 B.S.
Candidates are required to give their answers in their own words as far as practicable.
Group A
Long Answer QuestionsAttempt any Two questions.
- 1How do you define optimal solution? Does greedy algorithm always guarantee optimal solution? Given the string "SUPER DUPER CSIT", use a Greedy algorithm to build a Huffman tree. [1+2+7]
- 2What is order statistics? Write and analyze the algorithm for randomized quick sort. [3+7]
- 3Distinguish between dynamic programming and memorization. Parenthesize the matrices $A(30\times1)$, $B(1\times40)$, $C(40\times10)$ and $D(10\times15)$ for computing matrix multiplication using dynamic programming. [1+9]
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Solve the recurrence relation $T(n)=2T(n/2)+n$ using recursion tree method. [5]
- 5Find the best and worst case for Bubble sort. [5]
- 6Using Extended Euclidean Algorithm, find the GCD of 12 and 16. [5]
- 7Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using backtracking technique. [5]
- 8Define class P and NP problem. Why do we need approximation algorithms? Justify. [2+3]
- 9State the time and space complexity for sequential search. Write the rules for master theorem for finding asymptotic bounds. [1+4]
- 10Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach. [1+4]
- 11Distinguish between recursion and backtracking. Using Miller-Rabin primality test, check whether 53 is prime or not? [1+4]
- 12How does $0/1$ Knapsack problem differ with fractional one? Find the minimum vertex cover in the following graph. [1+4]