Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 5 · TU Board 2082
Course Title: Design and Analysis of Algorithms (CSC314)
Full Marks: 60Pass Marks: 24Time: 3 hours
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.
Group A
Attempt any TWO questions.(2 × 10 = 20)
- 1.10
How 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.
- 2.10
What is order statistics? Write and analyze the algorithm for randomized quick sort.
- 3.10
Distinguish between dynamic programming and memorization. Parenthesize the matrices A(30 × 1), B(1 × 40), C(40 × 10) and A(10 × 15), for computing matrix multiplication using dynamic programming.
Group B
Attempt any EIGHT questions.(8 × 5 = 40)
- 4.5
Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method.
Answer comingAlso asked in 2081, 2079, 2078, 2076
- 5.5
Find the best and worst case for Bubble sort.
- 6.5
Using Extended Euclidean Algorithm, find the GCD of 12 and 16.
- 7.5
Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique.
- 8.5
Define class P and NP problem. Why do we need approximation algorithms? Justify.
- 9.5
State the time and space complexity for sequential search. Write the rules for master theorem for finding asymptotic bounds.
- 10.5
Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach.
- 11.5
Distinguish between recursion and backtracking. Using Miller-Rabin primality test, check whether 53 is prime or not?
- 12.5
How does 0/1 Knapsack problem differ from fractional one? Find the minimum vertex cover in the following graph.
[figure in the original paper]
— The End —