Design and Analysis of Algorithm PYQ 2018-19 AKTU Question Paper

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Session 2018-19 · PYQ

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

  1. Q1a. Rank the following by growth rate: n, 2^(lg √n), log n, log(log n), log^2 n, (lg n)^(lg n), 4, (3/2)^n, n! (2 marks, 2018-19)
  2. Q1b. Prove that if n>=1, then for any n-key B-Tree of height h and minimum degree t>=2, h<=log_t((n+1)/2). (2 marks, 2018-19)
  3. Q1c. Define principal of optimality. When and how dynamic programming is applicable. (2 marks, 2018-19)
  4. Q1d. Explain application of graph coloring problem. (2 marks, 2018-19)
  5. Q1e. Compare adjacency matrix and linked Adjacency lists representation of a Graph with suitable example/diagram. (2 marks, 2018-19)
  6. Q1f. What are approximation algorithms? What is meant by P(n) approximation algorithms? (2 marks, 2018-19)
  7. Q1g. What do you mean by stability of a sorting algorithm? Explain its application. (2 marks, 2018-19)
  8. Q2a. Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) + T((1 - α)n) + cn, where α is a constant in the range 0 < α < 1 and c > 0 is also a constant. (7 marks, 2018-19)
  9. Q2b. Define BNP, NP hard and NP Complete Problems. Prove that Travelling Salesman Problem is NP-Complete. (7 marks, 2018-19)
  10. Q2c. Consider the weights and values of items listed below. Note that there is only one unit of each item. The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked… (7 marks, 2018-19)
  11. Q2d. Insert the following keys in a 2-3-4 B Tree: 40, 35, 22, 90, 12, 45, 58, 78, 67, 60 and then delete key 35 and 22 one after other. (7 marks, 2018-19)
  12. Q2e. Prove that if the weights on the edge of the connected undirected graph are distinct then there is a unique Minimum Spanning Tree. Give an example in this regard. Also discuss Prim’s Minimum Spanning Tree Algorithm in detail. (7 marks, 2018-19)
  13. Q3a. The recurrence T(n) = 7T(n/3) + n^2 describes the running time of an algorithm A. Another competing algorithm B has a running time of S(n) = a S(n/9) + n^2. What is the smallest value of ‘a’ such that A is asymptotically faster than B.? (7 marks, 2018-19)
  14. Q3b. How will you sort following array A of elements using heap sort: A = (23, 9, 18, 45, 5, 9, 1, 17, 6). (7 marks, 2018-19)
  15. Q4a. Explain the different conditions of getting union of two existing binomial Heaps. Also write algorithm for union of two Binomial Heaps. What is its complexity? (7 marks, 2018-19)
  16. Q4b. Insert the elements 8, 20, 11, 14, 9, 4, 12 in a Red-Black Tree and delete 12, 4, 9, 14 respectively. (7 marks, 2018-19)
  17. Q5a. When do Dijkstra and the Bellman-Ford algorithm both fail to find a shortest path? Can Bellman ford detect all negative weight cycles in a graph? Apply Bellman Ford Algorithm on the following graph. (7 marks, 2018-19)
  18. Q5b. Given an integer x and a positive number n, use divide & conquer approach to write a function that computes x^n with time complexity O(logn). (7 marks, 2018-19)
  19. Q6a. Solve the Subset sum problem using Backtracking, where n=4, m=18, w [4] = {5, 10, 8, 13} (7 marks, 2018-19)
  20. Q6b. Give Floyd Warshall algorithm to find the shortest path for all pairs of vertices in a graph. Give the complexity of the algorithm. Explain with example. (7 marks, 2018-19)
  21. Q7a. What is the application of Fast Fourier Transform (FFT)? Also write the recursive algorithm for FFT. (7 marks, 2018-19)
  22. Q7b. Give a linear time algorithm to determine if a text T is a cycle rotation of another string T’. For example, ‘RAJA’ and ‘JARA’ are cyclic rotations of each other. (7 marks, 2018-19)

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