Design and Analysis of Algorithm PYQ 2019-20 AKTU Question Paper

Design and Analysis of Algorithm AKTU syllabus

1. Unit 1: Introduction: Algorithms and Sorting
2. Unit 2: Advanced Data Structures
3. Unit 3: Divide and Conquer & Greedy Methods
4. Unit 4: Dynamic Programming, Backtracking & Branch and Bound
5. Unit 5: Selected Topics

Questions in Design and Analysis of Algorithm AKTU PYQ 2019-20

1. Q1a. How do you compare the performance of various algorithms? (2 marks, 2019-20)
2. Q1b. Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)). f1(n)=n^2.5, f2(n)=(sqrt(2))^n, f3(n)=n+10, f4(n)=10n, f5(n)=100n, and f6(n)=n^2 log n. (2 marks, 2019-20)
3. Q1c. What is advantage of binary search over linear search? Also, state limitations of binary search. (2 marks, 2019-20)
4. Q1d. What are greedy algorithms? Explain their characteristics? (2 marks, 2019-20)
5. Q1e. Explain applications of FFT. (2 marks, 2019-20)
6. Q1f. Define feasible and optimal solution. (2 marks, 2019-20)
7. Q1g. What do you mean by polynomial time reduction? (2 marks, 2019-20)
8. Q2a. (i) Solve the recurrence T (n) = 2T(n/2) + n² + 2n + 1 (ii) Prove that worst case running time of any comparison sort is Ω(nlogn) (7 marks, 2019-20)
9. Q2b. Insert the following element in an initially empty RB-Tree. 12, 9, 81, 76, 23, 43, 65, 88, 76, 32, 54. Now Delete 23 and 81. (7 marks, 2019-20)
10. Q2c. Define spanning tree. Write Kruskal’s algorithm for finding minimum cost spanning tree. Describe how Kruskal’s algorithm is different from Prim's algorithm for finding minimum cost spanning tree. (7 marks, 2019-20)
11. Q2d. What is dynamic programming? How is this approach different from recursion? Explain with example. (7 marks, 2019-20)
12. Q2e. Define NP-Hard and NP-complete problems. What are the steps involved in proving a problem NP-complete? Specify the problems already proved to be NP-complete. (7 marks, 2019-20)
13. Q3a. Among Merge sort, Insertion sort and quick sort which sorting technique is the best in worst case. Apply the best one among these algorithms to Sort the list E, X, A, M, P, L, E in alphabetic order. (7 marks, 2019-20)
14. Q3b. Solve the recurrence using recursion tree method: T (n) = T (n/2) + T (n/4) + T (n/8) + n (7 marks, 2019-20)
15. Q4a. Using minimum degree ‘t’ as 3, insert following sequence of integers 10, 25, 20, 35, 30, 55, 40, 45, 50, 55, 60, 75, 70, 65, 80, 85 and 90 in an initially empty B-Tree. Give the number of nodes splitting operations that take place. (7 marks, 2019-20)
16. Q4b. Explain the algorithm to delete a given element in a binomial Heap. Give an example for the same. (7 marks, 2019-20)
17. Q5a. Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach. (7 marks, 2019-20)
18. Q5b. What do you mean by convex hull? Describe an algorithm that solves the convex hull problem. Find the time complexity of the algorithm. (7 marks, 2019-20)
19. Q6a. Solve the following 0/1 knapsack problem using dynamic programming. P=[11, 21, 31, 33] w=[2, 11, 22, 15] c=40, n=4. (7 marks, 2019-20)
20. Q6b. Define Floyd Warshall Algorithm for all pair shortest path and apply the same on following graph. (7 marks, 2019-20)
21. Q7a. Describe in detail Knuth-Morris-Pratt string matching algorithm. Compute the prefix function π for the pattern ababbabbabbababbabb when the alphabet is Σ = {a,b}. (7 marks, 2019-20)
22. Q7b. What is an approximation algorithm? What is meant by P (n) approximation algorithms? Discuss approximation algorithm for Travelling Salesman Problem. (7 marks, 2019-20)

Design and Analysis of Algorithm previous year papers

• PYQ 2025-26
• PYQ 2024-25
• PYQ 2023-24
• PYQ 2022-23
• PYQ 2021-22
• PYQ 2020-21
• PYQ 2018-19
• PYQ 2017-18

More Design and Analysis of Algorithm resources

• Handwritten Notes: Unit 5 Handwritten Notes
• Important Questions: Unit 1 Important Questions
• Important Questions: Unit 2 Important Questions
• Important Questions: Unit 3 Important Questions
• Important Questions: Unit 4 Important Questions
• Important Questions: Unit 5 Important Questions
• Notes: Unit 1 Notes
• Notes: Unit 2 Notes
• Notes: Unit 3 Notes
• Notes: Unit 4 Notes
• Notes: Unit 5 Notes

Design and Analysis of Algorithm exam preparation

• Design & Analysis of Algorithm Important Topics
• Design & Analysis of Algorithm PYQ Analysis (unit-wise)
• Design & Analysis of Algorithm Predicted Paper
• Design & Analysis of Algorithm Important Questions