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

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

Q.1

a) Give the asymptotic bounds for the equation $f(n) = 2n^2 - 4n + 20$ and represent it in terms of $\theta$ notation. (Unit 1)

b) Define Quicksort? Sort the elements 22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3 using Merge sort. (Unit 1)
Q.2

a) Write an algorithm to find the matrix multiplication using Strassen's method. (Unit 1)

b) Construct a Huffman coding for the given data? Write the applications of huffman coding.

Characterabcdef
Frequency3815223346

(Unit 2)
Q.3

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

a) Solve the following 0/1 Knapsack problem using dynamic programming where $n = 4, m = 40, (w_1, w_2, w_3, w_4) = (2, 11, 22, 15)$ and $(p_1, p_2, p_3, p_4) = (11, 21, 31, 33)$. (Unit 3)

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

A directed multistage graph with 7 vertices labeled S, A, B, C, D, E, T. The stages are progressively laid out from left to right. The directed edges and their weights are: from S to A with weight 1; from S to B with weight 2; from S to C with weight 7; from A to D with weight 3; from A to E with weight 6; from B to D with weight 4; from B to E with weight 10; from C to E with weight 3; from C to T with weight 10; from D to T with weight 8; and from E to T with weight 2.

(Unit 2)
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 2 to vertex 4 with weight -1; from vertex 3 to vertex 2 with weight 3; and from vertex 3 to vertex 4 with weight 2.

(Unit 3)

b) Explain in detail about the FIFO branch and bound. (Unit 4)
Q.6

a) Write an algorithm for the 8-queens problem using backtracking. (Unit 4)

b) Draw the state space tree for 'm' coloring when $n=3$ and $m=3$. (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) =$ (double, int, for, if) with $p(1:4) = (3, 3, 1, 1)$ and $q(0:4) = (2, 3, 1, 1)$. Using $r(i,j)$'s construct the optimal binary search tree. (Unit 5)

b) Explain in detail Height balanced tree 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) Hamiltonian graph and cycle. (Unit 4)

d) Breadth First Search. (Unit 5)