Design and Analysis of Algorithm PYQ 2022-23 AKTU Question Paper

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Session 2022-23 · PYQ

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

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

Questions in Design and Analysis of Algorithm AKTU PYQ 2022-23

Q1a. Discuss the basic steps in the complete development of an algorithm. (2 marks, 2022-23)
Q1b. Explain and compare best and worst time complexity of Quick Sort. (2 marks, 2022-23)
Q1c. Discuss Skip list and its operations. (2 marks, 2022-23)
Q1d. Discuss the properties of binomial trees. (2 marks, 2022-23)
Q1e. Illustrate the applications of Graph Coloring Problem (2 marks, 2022-23)
Q1f. Define principle of optimality. (2 marks, 2022-23)
Q1g. Differentiate Backtracking and Branch and Bound Techniques. (2 marks, 2022-23)
Q1h. Discuss backtracking problem solving approach. (2 marks, 2022-23)
Q1i. Define NP, NP hard and NP complete. Give example of each. (2 marks, 2022-23)
Q1j. Explain Randomized algorithms. (2 marks, 2022-23)
Q2a. Explain Merge sort algorithm and sort the following sequence {23, 11, 5, 15, 68,31, 4, 17} using merge sort. (10 marks, 2022-23)
Q2b. What are the various differences in Binomial and Fibonacci Heap? Explain. (10 marks, 2022-23)
Q2c. 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 Kruskal’s Minimum Spanning Tree in detail. (10 marks, 2022-23)
Q2d. Discuss LCS algorithm to compute Longest Common Subsequence of two givenstrings and time complexity analysis. (10 marks, 2022-23)
Q2e. Explain and Write the Naïve-String string matching algorithm: Suppose the given pattern p= aa b and given text T = a c a a b c. Apply Naïve-String Matching algorithm on above Pattern (P) and Text (T) to find the number of occurrences of P in T. (10 marks, 2022-23)
Q3a. Examine the following recurrence relation: (i) T(n) = T(n-1) + n^4 (ii) T(n) = T(n/4) + T(n/2) + n^2 (10 marks, 2022-23)
Q3b. Explain algorithm for counting sort. Illustrate the operation of counting sort on the following array: A={0,1,3,0,3,2,4,5,2,4,6,2,2,3}. (10 marks, 2022-23)
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}. Also show that a red-black tree with n internal nodes has height at most 2lg(n+1). (10 marks, 2022-23)
Q4b. Explain and write an algorithm for union of two binomial heaps and write its time complexity. (10 marks, 2022-23)
Q5a. Explain "greedy algorithm" Write its pseudo code to prove that fractional Knapsack problem has a greedy-choice property. (10 marks, 2022-23)
Q5b. What are single source shortest paths? Write down Dijkstra's algorithm for it. (10 marks, 2022-23)
Q6a. What is the sum of subsets problem? Let w={5,7,10,12,15,18,20} and m=35. Find all possible subsets of w that sum to m using recursive backtracking algorithm for it. Draw the portion of the state-space tree that is generated. (10 marks, 2022-23)
Q6b. Illustrate n queen's problem. Examine 4 queen's problem using back tracking method. (10 marks, 2022-23)
Q7a. What is string matching algorithm? Explain Rabin-Karp method with examples. (10 marks, 2022-23)
Q7b. Explain approximation algorithm. Explore set cover problem using approximation algorithm. (10 marks, 2022-23)

Design and Analysis of Algorithm PYQ 2022-23 AKTU Question Paper

Design and Analysis of Algorithm AKTU syllabus

Questions in Design and Analysis of Algorithm AKTU PYQ 2022-23

Design and Analysis of Algorithm previous year papers

More Design and Analysis of Algorithm resources

Design and Analysis of Algorithm exam preparation