CSIT 5th Semester
Design and Analysis of Algorithms Board Question Paper 2082

CSC 325-2082 ✡
Tribhuvan University
Institute of Science and Technology
2082
✡
Bachelor Level/Third Year/Fifth Semester/Science
Computer Science Information Technology (CSC 325)
(Design and Analysis of Algorithms)
(New Course)
Full Marks:60 Pass Marks:24 Time:3 hours

Candidates are required to give their answers in their own words as for as practicable.
The figures in the margin indicate full marks

Section A
Long Answer Questions
Attempt any Two question.
[2x10=20]
1.

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.

What is order statistics? Write and analyze the algorithm for randomized quick sort.

3.

Distinguish between dynamic programming and memorization. Parenthesize the matrices A(30 x 1), B(1 x 40), C(40 x 10) and D(10 x 15), for computing matrix multiplication using dynamic programming.

Section B

Attempt any Eight questions

[8x5=40]
4.

Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method.

5.

Find the best and worst case for Bubble sort.

6.

Using Extended Euclidean Algorithm, find the GCD of 12 and 16.

7.

Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique.

8.

Define class P and NP problem. Why do we need approximation algorithms? Justify.

9.

State the time and space complexity for sequential search. Write the rules for master theorem for finding asymptotic bounds.

10.

Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach.

11.

Distinguish between recursion and backtracking. Using Miller-Rabin primality test, check whether 53 is prime or not?

12.

How does 0/1 Knapsack problem differ with fractional one? Find the minimum vertex cover in the following graph. question pic