## Fifth Semester | Third Year | Tribhuvan University

Old Question Collection | Question Bank

Design and Analysis of Algorithm(daa), Year: 2071

Computer Science and Information Technology (CSc. 303)

**Download Question Paper File**

[File Type: PDF | File Size: 459 KB | Download]

Candidates are required to give their answer in their own words as far as practicable.

**The figures in the margin indicate full marks.**

** Attempt all the questions**

1.) Why do you need the algorithm analysis? Explain the best, worst and average case complexities with suitable example. (2+6)

2.) Explain the master method for solving the recurrence relations. Solve the following recurrence relations using this method. (2+3+3)

a) T(n) = 3T(n/2) + n

b) T(n) = 2T(n/4) + √n

3.) Explain the divide and conquer approach for algorithm design. Design the binary search algorithm and analyze it’s time complexity. (2+6)

4.) Explain the merge-sort algorithm with example and analyze its time complexity. (8)

5.) What do you mean by a prefix code? How Huffman algorithm generates prefix codes? Explain with an example. (2+3+3)

6.) Discuss the 0/1 knapsack problem and how this problem can be solved? Explain the algorithm. (4+4)

7.) Explain the algorithm to find the all pair shortest path of a weighted connected graph. Trace the algorithm for the following graph. (3+5)

8.) Write an algorithm for depth first search. Use depth first search to find a spanning tree of the following graph. (3+5)

9.) Define the convex hull in 2D. Write the Grahm’s scan algorithm for computing the convex hull of points in 2D and analyze its time complexity. (2+6)

10.) What do you mean by approximation algorithm? Write the algorithm for approximate the vertex cover of a connected graph with example. (2+6)