# Design and Analysis of Algorithm (daa)| BSc.CSIT (TU) Question Paper 2071 | Fifth Semester

## 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)

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)

(Visited 453 times, 1 visits today)

Posted By : | Comment RSS | Category : Fifth Semester, Old Question Collection
Subscribe Notes