AI/AL/CD-402 (GS) – Analysis and Design of Algorithm

B.Tech./B.Tech. (Working Professional) IV Semester
Examination, June 2025
Grading System (GS)
Max Marks: 70 | Time: 3 Hours

Note:
i) Attempt any five questions.
ii) All questions carry equal marks.

Previous Year Questions (June 2025)

Q.1

a) Solve the following recurrence relation using recursion tree method:
$T(n)=2T(n/2)+n$
$T(1)=O(1)$ (Unit 1)

b) Show the following recurrence relation using Master's theorem:
$T(n)=2T(n/2)+n \log n$ (Unit 1)
Q.2

a) Find the number of comparisons made by the sequential search for the worst and best case. (Unit 1)

b) Apply Quick sort on the array given below:
15, 31, 1, 9, 80, 12, 14, 7, 24 (Unit 1)
Q.3

a) List various problems that can be solved using the Greedy algorithm approach. (Unit 2)

b) Write Kruskal's algorithm to find MST for a given graph. Also discuss about its time complexity. (Unit 2)
Q.4

a) Write Dijkstra's Algorithm for the solution of single source shortest path problem. (Unit 2)

b) Explain fractional Knapsack problem in detail. (Unit 2)
Q.5

a) What is 0/1 Knapsack problem? Is Greedy method effective to solve 0/1 Knapsack problem. (Unit 3)

b) Is there anything common between dynamic programming and divide and conquer? What is the main difference between the two? (Unit 3)
Q.6

a) Obtain any two solutions to 4-queens problem. Establish the relationship between them. (Unit 4)

b) Construct the minimum spanning tree for the given graph using Kruskal's Algorithm:

An undirected weighted graph with 7 vertices labeled 1 through 7. The edges and their corresponding weights are as follows: Edge between node 1 and 2 with weight 28; Edge between node 1 and 6 with weight 10; Edge between node 2 and 3 with weight 16; Edge between node 2 and 7 with weight 14; Edge between node 3 and 4 with weight 12; Edge between node 4 and 5 with weight 22; Edge between node 4 and 7 with weight 18; Edge between node 5 and 6 with weight 25; Edge between node 5 and 7 with weight 24.

(Unit 2)
Q.7

a) Write an algorithm for the implementation of binary search method. (Unit 1)

b) Solve the following instance of Knapsack problem by using the branch and bound technique:

Items W P
$I_1$ 9 15
$I_2$ 6 6
$I_3$ 7 5
$I_4$ 2 1

$W=16$ (Unit 4)
Q.8

a) Explain the class NP-complete with example. (Unit 5)

b) There are 8, 15, 13 and 14 number of nodes in 4 different trees. Which of them could have formed a Full Binary Tree? (Unit 5)