TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2079 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.
- 1Explain the divide and conquer strategy for problem solving. Describe the worst-case linear time selection algorithm and analyze its complexity.
- 2Write the dynamic programming algorithm for matrix chain multiplication. Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as $A_{5\times10}, B_{10\times15}, C_{15\times20}, D_{20\times30}$.
- 3What do you mean by Backtracking? Explain the backtracking algorithm for solving 0-1 knapsack problem and find the solution for the problem given below: | Items $\to$ | 1 | 2 | 3 | 4 | | :--- | :--- | :--- | :--- | :--- | | Weight (wi) $\to$ | 2 | 3 | 4 | 5 | | Profit (Pi) $\to$ | 3 | 5 | 6 | 10 | and capacity of knapsack = 10 kg
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity
- 5Trace the quick sort algorithm for sorting the array $A[\ ] = \{15, 7, 6, 23, 18, 34, 25\}$ and write it's best and worst complexity
- 6Generate the prefix code for the string " CYBER CRIME" using Huffman algorithm and find the total number of bits required.
- 7Solve the following recurrence relations using masters method a) $T(n)=2T(n/4)+kn^2$, $n>1$ $=1$, $n=1$. b) $T(n)=5T(n/4)+kn$, $n>1$ $=1$, $n=1$.
- 8Find the edit distance between the srtring " ARTIFICIAL" and "NATURAL" Using dynamic programming
- 9Find the MST from following graph using Kruskal's algorithm. [diagram/image to be added manually]
- 10Solve the following linear congruences using Chinese Remainder Theorem. $x\equiv1\pmod{2}$ $x\equiv3\pmod{5}$ $x\equiv6\pmod{7}$
- 11Define tractable and intractable problem. Illustrate vertex cover problem with an example.
- 12Write short notes on: a) Best, Worst and average case complexity b) Greedy Strategy