CS/SD-402 (GS) – Analysis Design of Algorithm

B.Tech./B.Tech. (Working Professional) IV Semester
Examination, June 2025
Grading System (GS) / Working Professional
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 relations using the substitution method.
$$T(n) = \begin{cases} 1 & n \le 4 \\ 2T(\sqrt{n}) + \log n & n > 4 \end{cases}$$ (Unit 1)

b) The worst case time of procedure merge sort is $O(n \log n)$. What is its best case time? Can we say that the time for merge sort is $O(n \log n)$? (Unit 1)
Q.2

a) Obtain a set of optimal Huffman codes for message (M1, ... M7) with relative frequencies (q1, q2.....,q7) = (4, 5, 7, 8, 10, 12, 20). Draw the decode tree for this set of codes. (Unit 2)

b) Use algorithm shortest paths to obtain in non-decreasing order the lengths of the shortest paths from vertex 1 to all remaining vertices in the di-graph.

A directed graph with 6 vertices labeled 1 to 6 in circles. The directed edges and their corresponding weights are as follows: from vertex 1 to 2 with a weight of 2; from vertex 1 to 3 with a weight of 15; from vertex 2 to 4 with a weight of 30; from vertex 2 to 5 with a weight of 10; from vertex 3 to 4 with a weight of 4; from vertex 3 to 6 with a weight of 10; from vertex 4 to 5 with a weight of 4; and from vertex 4 to 6 with a weight of 10. The graph is laid out with vertex 1 on the far right. Vertices 2 and 3 are to the left of 1, with 2 above 3. Vertex 4 is to the left of 2 and 3, roughly in the center. Vertices 5 and 6 are to the far left, with 5 above 6.

(Unit 2)
Q.3

a) Give an example of a set of knapsack instances for which $|S^i| = 2^i, 0 \le i \le n$. The set should include one instance for each $n$. (Unit 3)

b) Explain Floyd Warshall algorithm with suitable example. (Unit 3)
Q.4

a) Given an $n \times n$ chessboard, a knight is placed on an arbitrary square with coordinates $(x, y)$. The problem is to determine $n^2-1$ Knight moves such that every square of the board is visited once if such a sequence of moves exists. Present an algorithm to solve this problem. (Unit 4)

b) Consider the traveling salesperson instance defined by the cost matrix.
$$\begin{pmatrix} \infty & 7 & 3 & 12 & 8 \\ 3 & \infty & 6 & 14 & 9 \\ 5 & 8 & \infty & 6 & 18 \\ 9 & 3 & 5 & \infty & 11 \\ 18 & 14 & 9 & 8 & \infty \end{pmatrix}$$ (Unit 4)
Q.5

a) Show that DFS visits all vertices in G reachable from V. (Unit 5)

b) Obtain a nondeterministic algorithm of complexity $O(n)$ to determine whether there is a subset of $n$ numbers $a_i, 1 \le i \le n$, that sums of $m$. (Unit 5)
Q.6

a) Write an algorithm to delete an element $x$ from a binary search tree $t$. What is the time complexity of your algorithm? (Unit 5)

b) What do you mean by balance factor in AVL tree? Give a suitable example to balance a AVL tree. (Unit 5)
Q.7

a) Suppose there are $n$ jobs to be executed but only $k$ processors that can work in parallel. The time required by jobs $i$ to $t_i$, write an algorithm that determines which jobs are to be run on which processors and the order in which they should be run so that the finish time of the last job is minimized. (Unit 4)

b) Find optimal solution for 0/1 knapsack problem (W1, W2, W3, W4) = (10, 15, 6, 9), (P1, P2, P3, P4) = (2, 5, 8, 1) and M = 30. (Unit 3)
Q.8

Write short notes on following. (any two)

a) B-Trees (Unit 5)

b) Tree Traversal (Unit 5)

c) Reliability Design (Unit 3)