AG/CSIT(CI)/IT-403 (GS) – Analysis and Design of Algorithm

B.Tech. IV Semester
Examination, June 2023
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 2023)

Q.1

a) Explain algorithm design technique? How do you measure the algorithm running time? (Unit 1)

b) Give the divide and conquer solution for binary search and analyze the time complexity for it. (Unit 1)
Q.2

a) Explain the quick sort algorithm, simulate it with the following data 20, 35, 10, 16, 54, 21, 25. (Unit 1)

b) Compute the optimal solution for job sequencing with deadlines using greedy method. $N=4$, profits $(p_1,p_2,p_3,p_4)=(100,10,15,27)$, deadlines $(d_1,d_2,d_3,d_4)=(2,1,2,1)$ (Unit 2)
Q.3

a) Consider the following instance of the knapsack problem and solve it using greedy method $n=7$, $m=15$, $(p_1, p_2, p_3, p_4, p_5, p_6, p_7)=(10,5,15,7,6,18,3)$ and $(w_1, w_2, w_3, w_4, w_5, w_6, w_7)=(2,3,5,7,1,4,1)$. (Unit 2)

b) Apply the kruskal algorithm for the following graph and explain.

An undirected weighted graph with 6 vertices labeled 1 through 6. The edges and their corresponding weights are as follows: Edge 1 to 2 with weight 10; Edge 1 to 4 with weight 30; Edge 1 to 5 with weight 45; Edge 2 to 3 with weight 50; Edge 2 to 5 with weight 40; Edge 2 to 6 with weight 25; Edge 3 to 5 with weight 35; Edge 4 to 6 with weight 20; and Edge 5 to 6 with weight 55.

(Unit 2)
Q.4

a) Solve the following $0/1$ Knapsack problem using dynamic programming $P=(11,21,31,33)$ $W=(2,12,23,15)$, $C=42$, $n=4$. (Unit 3)

b) Design a three stage reliability system with device types $d_1$, $d_2$ and $d_3$. The costs are $30, $15 and $20 respectively. The cost of the system is to be no more than $105. The reliability of each device is 0.9, 0.8 and 0.5 respectively. (Unit 3)
Q.5

a) On which type of problem we apply multi stage graph technique? Explain with example. (Unit 3)

b) Briefly explain 8-queen problem using backtracking with algorithm. (Unit 4)
Q.6

a) Identify the Hamiltonian cycle from the following graph.

An undirected graph with 5 vertices labeled v1, v2, v3, v4, and v5. The vertices v1, v2, v3, and v4 form a rectangle with crossed diagonals, and v5 forms a triangle attached to the side of v1 and v4. The edges are: (v1, v2), (v2, v3), (v3, v4), (v4, v1), (v1, v3), (v2, v4), (v5, v1), and (v5, v4).

(Unit 4)

b) Write an algorithm for traveling salesperson problem using check bounds. (Unit 4)
Q.7

a) Discuss the operations performed on the binary search tree for the following data: 20, 49, 41, 93, 69, 90, 76, 62, 81, 75, 10, 79, 87, 38 and delete 41 and 76. (Unit 5)

b) Differentiate between BFS and DFS. (Unit 5)
Q.8

Write short notes on any two of the following.

a) 2-3 trees (Unit 5)

b) Merge sort (Unit 1)

c) Optimal merge patterns (Unit 2)

d) Floyd Warshall algorithm (Unit 3)