Design and Analysis of Algorithm Model Question Solution | DAA bsc csit solution | csit 5th sem

Design and Analysis of Algorithm Model Question Solution | DAA bsc csit solution | csit 5th sem

bsc csit 5th sem DAA model question solution 

DOWNLOAD 

Tribhuvan University

Institute of Science and Technology

Model Question

Bachelor Level/Third Year / Fifth Semester/Science Full Marks: 60

Computer Science and Information Technology Pass Marks: 24

(CSc. 314- Design and Analysis of Algorithm) Time : 3 hours.

Section A

Attempt any two questions. (2 × 10 = 20)

1. Why do you need the algorithm analysis? Discuss about RAM model for analysis of

algorithms. Also discuss about Big Oh, Big Omega and Big theta with examples.

(2+3+5)

2. Discuss the order statistics. Explain about the worst case linear time selection algorithm

and analyze its time complexity. (2 + 8)

3. Explain in brief about the Dynamic Programming Approach for algorithm design. How it

differs with recursion? Explain the Floyd Warshall algorithm to compute the all pair

shortest path in graph and analyze its time complexity. (4 + 6)

Section B

Attempt any eight questions. (8 × 5 = 40)

4. Write the algorithm for Binary Search with divide and conquer approach and explain its

complexity. (5)

5. Solve the following recurrence relations using master method. ( 2.5 + 2.5)

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

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

6. What is prefix code? Explain Huffman algorithm to compute the prefix codes. (5)

7. Write the algorithm for insertion sort and explain its time complexity (5)

8. What do you mean by memoization strategy? Compare memoization with dynamic

programming (5)

9. Explain backtracking with suitable example. (5)

10. Explain the Euclid’s method to solve the modular linear equations with example (5)

11. Explain in brief about the complexity classes P, NP and NP Complete (5)

12. Write short notes on

a. Tractable and Intractable Problems

b. Approximation Algorithms