Design and Analysis of Algorithm PYQ 2020-21 AKTU Question Paper

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Session 2020-21 · PYQ

AKTU Design and Analysis of Algorithm previous year question paper 2020-21 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 2020-21

  1. Q1a. What is recurrence relation? How is a recurrence solved using master’s theorem? (2 marks, 2020-21)
  2. Q1b. What is asymptotic notation? Explain Omega (Ω) notation? (2 marks, 2020-21)
  3. Q1c. Write down the properties of binomial tree. (2 marks, 2020-21)
  4. Q1d. Differentiate Backtracking algorithm with branch and bound algorithm. (2 marks, 2020-21)
  5. Q1e. Solve the recurrence T (n) = 4T(n/2) + n² (2 marks, 2020-21)
  6. Q1f. Explain Fast Fourier Transform in brief. (2 marks, 2020-21)
  7. Q1g. Write an algorithm for naive string matcher? (2 marks, 2020-21)
  8. Q1h. Explain searching technique using divide and conquer approach. (2 marks, 2020-21)
  9. Q1i. Explain Skip list in brief. (2 marks, 2020-21)
  10. Q1j. Explain how algorithms performance is analyzed? (2 marks, 2020-21)
  11. Q2a. Write an algorithm for counting sort? Illustrate the operation of counting sort on the following array: A={4, 0, 2, 0, 1, 3, 5, 4, 1, 3, 2, 3} (10 marks, 2020-21)
  12. Q2b. Show the results of inserting the keys F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E in order into an empty B-tree. Use t=3, where t is the minimum degree of B- tree. (10 marks, 2020-21)
  13. Q2c. Discuss greedy approach to an activity selection problem of scheduling several competing activities. Solve following activity selection problem S = {A1, A2, A3, A4, A5, A6, A7, A8, A9, A10} Si = {1, 2, 3, 4, 7, 8, 9, 9, 11, 12} Fi = {3, 5, 4, 7, 10, 9, 11, 13, 12, 14} (10 marks, 2020-21)
  14. Q2d. What is sum of subset problem? Draw a state space tree for Sum of subset problem using backtracking? Let n=6, m=30 and w [1:6] = {5, 10, 12, 13, 15, 18} (10 marks, 2020-21)
  15. Q2e. Write KMP algorithm for string matching? Perform the KMP algorithm to search the occurrences of the pattern abaab in the text string abbabaabaabab. (10 marks, 2020-21)
  16. Q3a. Solve the following recurrence relation: i. T (n) = T (n-1) + n⁴ ii. T (n) = T (n/4) + T (n/2) + n² (10 marks, 2020-21)
  17. Q3b. Write an algorithm for insertion sort. Find the time complexity of Insertion sort in all cases. (10 marks, 2020-21)
  18. Q4a. Write an algorithm for insertion of key in the Red-Black Tree. Discuss the various cases for insertion of key in red-black tree for given sequence of key in an empty red-black tree- 5, 16, 22, 25, 2, 10, 18, 30, 50, 12, 1. (10 marks, 2020-21)
  19. Q4b. Explain and write an algorithm for union of two binomial heaps and also write its time complexity? (10 marks, 2020-21)
  20. Q5a. Define minimum spanning tree (MST). Write Prim's algorithm to generate a MST for any given weighted graph. Generate MST for the following graph using Prim's algorithm. (10 marks, 2020-21)
  21. Q5b. Explain Dijkstra's algorithm to solve single source shortest path problem with suitable example. (10 marks, 2020-21)
  22. Q6a. What is travelling salesman problem (TSP)? Find the solution of following TSP using dynamic programming. 0 1 15 6 2 0 7 3 9 6 0 12 10 4 8 0 (10 marks, 2020-21)
  23. Q6b. Discuss n queen's problem. Solve 4 queen's problem using backtracking method? (10 marks, 2020-21)
  24. Q7a. Write short notes on following: (i.) Randomized algorithm. (ii.) NP- complete and NP hard. (10 marks, 2020-21)
  25. Q7b. What is approximation algorithm? Explain set cover problem using approximation algorithm. (10 marks, 2020-21)

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