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

Download our Android App from Google Play Store and start reading Reference Notes Offline.

daa question paper 2071Fifth 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)question-7
8.) Write an algorithm for depth first search. Use depth first search to find a spanning tree of the following graph. (3+5)question-8
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)

Posted By : Digvijay | Comment RSS | Category : Fifth Semester, Old Question Collection
Tag :

Post a Comment

Your email is never published nor shared. Required fields are marked *


Wordpress DMCA
Community | Toolbar | Android App | Founder/Developer : Hari Prasad Chaudhary | CSIT Portal Manager : Digvijay Chaudhary