Design and Analysis of Algorithms 2078(New Course)

Section A

Attempt any two questions: (2*10=20)

1. What are the elementary properties of algorithm ? Explain. Why do you need analysis of algorithm? Discuss about the RAM model for analysis of algorithm with suitable example. (2+2+6)

2. Explain about the divide and  conquer paradigm for a algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity. (4+6)

3. Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 knapsack problem using the dynamic programming approach and explain its complexity. (2+2+6)

Section B

Attempt any eight questions:(8*5=40)

4. Explain the recursion tree method for solving the recurrence relation. Solve following recurrence relation using using this method. T(n) = 2T(n/2)+1 for n>1, T(n) = 1 for n = 1 (2+3)

5. Write an algorithm to find the maximum element of an array and analyze its time complexity.(5)

6. Write the algorithm for bubble sort and explain its time complexity.(5)

7. What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems.(1+4)

8. Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.(5)

9. What do you mean by memoization strategy? Compare memoization with dynamic programming.(2+3)

10. Explain the concept of backtracking. How it differ with recursion?(2+3)

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

12. Write short notes on:(2*2.5)

a. NP Hard Problems and NP Completeness

b. Problem Reduction