Design and Analysis of Algorithm PYQ 2021-22 AKTU Question Paper

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Session 2021-22 · PYQ

AKTU Design and Analysis of Algorithm previous year question paper 2021-22 for B.Tech Semester 5. Covers Introduction: Algorithms and Sorting, Advanced Data…

Open the interactive reader to study this resource on AcademicArk.

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 2021-22

  1. Q1a. How analyze the performance of an algorithm in different cases? (2 marks, 2021-22)
  2. Q1b. Derive the time complexity of Merge sort. (2 marks, 2021-22)
  3. Q1c. Explain left rotation in RB tree. (2 marks, 2021-22)
  4. Q1d. Write down the properties of Fibonacci Heap. (2 marks, 2021-22)
  5. Q1e. Explain Greedy programming in brief. (2 marks, 2021-22)
  6. Q1f. What do you mean by convex hull? (2 marks, 2021-22)
  7. Q1g. Write down the Floyd Warshal algorithm. (2 marks, 2021-22)
  8. Q1h. Explain Branch and Bound method in brief. (2 marks, 2021-22)
  9. Q1i. Explain Randomized algorithm in brief. (2 marks, 2021-22)
  10. Q1j. Explain NP-complete and NP-Hard. (2 marks, 2021-22)
  11. Q2a. Solve the recurrence i) T (n) = 3T (n/4) + cn² using recursion tree method. ii) T (n) = n + 2T (n/2) using Iteration method. (Given T(1)=1) (10 marks, 2021-22)
  12. Q2b. What is Binomial Heap? Write down the algorithm for Decrease key operation in Binomial Heap also write its time complexity. (10 marks, 2021-22)
  13. Q2c. Write and explain the Kruskal algorithm to find the Minimum Spanning Tree of a graph with suitable example. (10 marks, 2021-22)
  14. Q2d. What is N queens problem? Draw a state space tree for 4 queens problem using backtracking. (10 marks, 2021-22)
  15. Q2e. Write Rabin Karp string matching algorithm. Working modulo q=11, how many spurious hits does the Rabin karp matcher in the text T= 3141592653589793, when looking for the pattern P=26. (10 marks, 2021-22)
  16. Q3a. Write Merge sort algorithm and sort the following sequence {23, 11, 5, 15, 68, 31, 4, 17} using merge sort. (10 marks, 2021-22)
  17. Q3b. What do you understand by stable and unstable sorting? Sort the following sequence {25, 57, 48, 36, 12, 91, 86, 32} using heap sort. (10 marks, 2021-22)
  18. Q4a. Discuss the various cases for insertion of key in red-black tree for given sequence of key in an empty red-black tree- {15, 13, 12, 16, 19, 23, 5, 8}. (10 marks, 2021-22)
  19. Q4b. What is skip list? Explain the Search operation in Skip list with suitable example also write its algorithm. (10 marks, 2021-22)
  20. Q5a. What is Knapsack problem? Solve Fractional knapsack problem using greedy programming for the following four items with their weights w = {3, 5, 9, 5} and values P = {45, 30, 45, 10} with knapsack capacity is 16. (10 marks, 2021-22)
  21. Q5b. Write down the Bellman Ford algorithm to solve the single source shortest path problem also write its time complexity. (10 marks, 2021-22)
  22. Q6a. What is travelling salesman problem (TSP)? Find the solution of following TSP using Branch & Bound method [[ 0, 20, 30, 10, 11 ], [ 15, 0, 16, 4, 2 ], [ 3, 5, 0, 2, 4 ], [ 19, 6, 18, 0, 3 ], [ 16, 4, 7, 16, 0 ]] (10 marks, 2021-22)
  23. Q6b. Explain the method of finding Hamiltonian cycles in a graph using backtracking method with suitable example. (10 marks, 2021-22)
  24. Q7a. Write and explain the algorithm to solve vertex cover problem using approximation algorithm. (10 marks, 2021-22)
  25. Q7b. Explain and Write the Knuth-Morris-Pratt algorithm for pattern matching also write its time complexity. (10 marks, 2021-22)

AKTU paper codes: BCS503, KCS503, RCS502

Design and Analysis of Algorithm previous year papers

More Design and Analysis of Algorithm resources

Browse all notes · Semester 5 notes · Design & Analysis of Algorithm notes