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

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

Q.1

a) Obtain the asymptotic bound using the substitution method for the recurrence relation $T(n) = 3T(n/3) + n$ and represent it in terms of $\theta$ notation. (Unit 1)

b) What is Merge sort? Sort the elements 20.30.15.11.35.19.12.11.55 using Merge sort. (Unit 1)
Q.2

a) Discuss Strassen's matrix multiplication and Classical O(n²) methods. Determine when Strassen's method outperforms classical method. (Unit 1)

b) Define spanning tree? Construct a minimal spanning tree for the given graph using Prim's algorithm.

An undirected graph with 6 vertices labeled 1 to 6 in circles. The edges and their weights are: edge between 1 and 2 with weight 6; edge between 1 and 3 with weight 1; edge between 1 and 4 with weight 5; edge between 2 and 3 with weight 5; edge between 2 and 5 with weight 3; edge between 3 and 4 with weight 5; edge between 3 and 5 with weight 6; edge between 3 and 6 with weight 4; edge between 4 and 6 with weight 2; edge between 5 and 6 with weight 6.

(Unit 2)
Q.3

Solve the following problem of job sequencing with deadlines using the Greedy method.
$n = 4, (p_1, p_2, p_3, p_4) = (100, 10, 15, 27)$ and $(d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$. (Unit 2)
Q.4

a) Apply the greedy method to solve the 0/1 Knapsack problem for $n = 3, m = 20, (w_1, w_2, w_3) = (18, 15, 10)$ and $(p_1, p_2, p_3) = (25, 24, 15)$. (Unit 2)

b) Construct a multistage graph for the given graph using the greedy method.

A directed multistage graph with 12 vertices. Stage 1 has vertex 1 (s). Stage 2 has vertices 2, 3, 4, 5. Stage 3 has vertices 6, 7, 8. Stage 4 has vertices 9, 10, 11. Stage 5 has vertex 12 (t). The directed edges and their weights are: from 1 to 2 with weight 9; 1 to 3 with weight 7; 1 to 4 with weight 3; 1 to 5 with weight 2; 2 to 6 with weight 4; 2 to 7 with weight 2; 2 to 8 with weight 1; 3 to 6 with weight 2; 3 to 7 with weight 7; 4 to 8 with weight 11; 5 to 7 with weight 11; 5 to 8 with weight 8; 6 to 9 with weight 6; 6 to 10 with weight 5; 7 to 9 with weight 4; 7 to 10 with weight 3; 8 to 10 with weight 5; 8 to 11 with weight 6; 9 to 12 with weight 4; 10 to 12 with weight 2; 11 to 12 with weight 5.

(Unit 3)
Q.5

a) Explain the Floyd Warshall algorithm for the given graph.

A directed graph with 4 vertices labeled 1, 2, 3, and 4 in circles. The directed edges and their weights are: from vertex 1 to vertex 2 with weight 4; from vertex 1 to vertex 3 with weight -2; from vertex 3 to vertex 2 with weight 3; from vertex 3 to vertex 4 with weight 2; and from vertex 4 to vertex 2 with weight -1.

(Unit 3)

b) Using branch and bound technique explain the 0/1 knapsack problem. (Unit 4)
Q.6

a) Give the solution to the 8-queens problem using backtracking. (Unit 4)

b) What is graph coloring? Explain graph coloring for the given graph.

An undirected graph with 6 vertices labeled a, b, c, d, e, f. Vertices a, b are on the left; c, d are in the center; e, f are on the right. The edges connect the following pairs of vertices: (a,b), (a,c), (a,e), (b,c), (b,d), (b,f), (c,d), (c,e), (d,e), (d,f), (e,f).

(Unit 4)
Q.7

a) Use the function OBST to compute $w(i, j), r(i, j)$ and $c(i, j), 0 \le i < j \le 4$ for the identifier set $(a_1, a_2, a_3, a_4) =$ (char, float, while, else) with $p(1) = \frac{1}{20}, p(2) = \frac{1}{5}, p(3) = \frac{1}{10}, p(4) = \frac{1}{20}, q(0) = \frac{1}{5}, q(1) = \frac{1}{10}, q(2) = \frac{1}{5}, q(4) = \frac{1}{20}$. Using $r(i, j)$'s construct the optimal binary search tree. (Unit 3)

b) Explain in detail about 2-3 Trees with an example. (Unit 5)
Q.8

Write short notes on any two of the following :

a) Binary search algorithm and its time complexity (Unit 1)

b) Single source shortest path algorithm (Unit 2)

c) Parallel algorithms (Unit 4)

d) NP Completeness (Unit 5)