TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2081 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.
- 1Differentiate between dynamic programming and memoization. Compute the shortest path between every pair in the graph using Floyd Warshall algorithm. [2+8]
- 2What is the worst case of quick sort and how does randomized quick sort handle it? Sort data {-2, 4, -3, 6, 12, 10, 11, 13, 9} using quick sort. [3+7]
- 3Does greedy algorithm guarantee optimal solution? Solve Fractional knapsack to find maximum loot (W=20kg). [2+8]
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Given a set $A = \\{5, 7, 10, 12, 15, 18, 20\\}$, find the subset that sum to 35 using backtracking. [5]
- 5Solve the following recurrence relations using master's method: a) $T(n) = 2T\left(\frac{n}{2}\right) + n^3$, for $n > 1$ and $T(1) = 1$ b) $T(n) = 2T\left(\frac{n}{4}\right) + 1$, for $n > 1$ and $T(1) = 1$ $[2.5 + 2.5]$
- 6Write the algorithm to find nth fibonacci number with its time and space complexity. [5]
- 7Define order statistics problem. Find the edit distance between "cat" and "car" using dynamic programming. [1+4]
- 8Discuss about recursion and backtracking. Analyze the complexity of Miller Rabin Randomized Primality test. [1+4]
- 9Solve the linear equations using Chinese Remainder Theorem: $x \equiv 1 \pmod 3, x \equiv 2 \pmod 5, x \equiv 0 \pmod 7$. [5]
- 10Explain the approximation algorithm for vertex cover of a connected graph with an example. [5]
- 11State cooks theorem. discuss about problem reducibility. [2+3]
- 12Write short Notes: [2.5+2.5] a) Asymptotic notations b) Class P, NP and NP-complete