Analysis & Design of Algorithms 2022 Question Paper — Government Coll…
The 2022 Analysis & Design of Algorithms previous year question paper (Government College of Engineering and Technology, Jammu), with every question and its marks.
- University: Government College of Engineering and Technology, Jammu
- Subject: Analysis & Design of Algorithms
- Course: ANALYSIS AND DESIGN OF ALGORITHM
- Branch: Comp. Sci. & Engg.
- Year: 2022
- Paper: end-term
- Duration: 180 minutes
- Total marks: 75
Instructions
- Attempt five questions in all, selecting at least two questions from each Section.
- All questions carry equal marks.
Questions
Section-A
- Q1. (a) Solve using Recursion Tree method $T(n) = 8T(n/2) + n^2$ (b) Solve the following recurrence using Master's Theorem Method : $T(n) = 4T\left(\frac{n}{2}\right) + n^2 \sqrt{n}$. (c) Explain the significance of asymptotic analysis of an algorithm. Discuss various notations used for asymptotic analysis of an algorithm.
- Q2. (a) Discuss various Collision resolution strategies along with advantages and disadvantages of each. (b) Illustrate the functioning of Heapsort on the following array : $A = (6, 14, 3, 25, 2, 10, 20, 7, 6)$
- Q3. (a) Draw the decision tree for Binary search on array of length 14 and show how we can get its lower bound. (b) Write a short note on Oracle and Adversary Arguments.
- Q4. (a) Define NP-Hard and NP-Complete Problems. (b) What are the steps used to show a given problem is NP-Complete ? (c) State and explain Cook's theorem.
Section-B
- Q5. (a) Write and explain merge sort algorithm using divide and conquer strategy. Write a descriptive note on its best case, average case, and worst-case time efficiency. (b) Specify the difference between divide and conquer strategy and dynamic programming.
- Q6. Which design techniques give optimal solutions to 0/1 Knapsack problem and Fractional Knapsack problem. Using those techniques find optimal solution for : 0/1 Knapsack problem Fractional Knapsack problem Where number of items are 3 with weights $(w1, w2, w3) = (2, 3, 3)$ and Profits $(P1, P2, P3) = (1, 2, 4)$ Given Knapsack capacity is 6. [15 marks]
- Q7. (a) Using Dynamic Programming find Longest Common Subsequence of the following two sequences X and Y showing all the steps : X : B, A, C, D, B Y : B, D, C, B (b) List and explain the characteristic properties associated with a problem that can be solved using dynamic programming.
- Q8. (a) Define Travelling Salesman Problem (TSP). Explain the basic steps that are to be followed to solve TSP using branch and bound. Illustrate with an example. (b) State and explain N Queens Problem. Write the backtracking algorithm for solving N Queens problem.