C 1200CST306052301

Reg NO. : Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY i
B.Tech Degree S6 (R,S) / S6 (PT) / (WP) Exam April 2025 (2019 Scl rat..`:ii+ji:..:.:ch;:::=:::.:
i.i%ffff,:.:,:4
?i,.-.r-*.ij``=``-`''

Course Code: CST306

Course Name: ALGORITHM ANALYSIS AND DESIGN

Max. Marks: loo Duration: 3 Hours

PART A
Answer all questions, each carries 3 marks.

Give the recurrence equation for the binary search algorithm. Solve the equation

using the Master's theorem.

|s 2(n+1) € a(27`) ? Justify your answer.

Define strongly connected component of a directed graph. Give one example.

Draw the linked list representation of UNION(2,6) of disjoint sets Si =

{1,2,3,4}and S2 = {8,12,6}where the funtion UNION(x,y) performs the union of sets

containing elements x and y.

Compare the time complexities of Strassen's matrix multiplication with ordinary matrix (3)

multiplication. Which algorithm run faster?

Give the control abstraction of greedy algorithm design strategy.

Explain the desirable characteristics of problems that can be solved using dynamic

programming

Give the recursive definition for the minimum cost of parenthesizing a matrix (3)
chain product 4.A(i+1). . 4/..

Define the complexity classes P, NP and NP-Hard.

Compare Las Vegas and Monte Carlo algorithms for randomized algorithms.

PART 8
Answer onofull question firom each module, each carries 14 marks.

Module I
11 a) Givie the mathematical definition of any three asymptotic notations.

b) Find the time complexity of given recurrence using recursion tree method.

Page lof4
 1200CST306052301

I(7t) = 3r (:) + c7'i2 when n > 1 and I(7t) = 0 otherwise.

OR
12 a) Solvethe recurrence equationusing Master'stheorem. (8)

(i) I(n)=3T(:)+n2

(ii, I(„,=T(¥)+1

b) Solve the recurrence equation by substi (6)

Module 11

13 a) Give Breadth First Search (BFS) algorithm for graph traversal. Perform its time (7)

complexity analysis.

b) Perforin Depth First search (DFS) traversal on the above graph starting from node A. (7)

Where multiple node choices may be available for next travel, choose the next node in

alphabetical order. Classify the edges of the graph into different category.

OR
14 a) ConstructAVLtreewithfollowingnodes. 50,20,60,10, 8,15,32,46,1l,48 (9)

Explain 4 cases of AVL Tree rotations?

-:±----: (5)

-:--_i, -::`±::::- :i-ij

!±i iif::-

Page 2of 4
 1200CST306052301

Give any topological ordering of the given graph?

Module Ill

15 a) Let G=(V,E) beagraphwithvertexset vandedge setE. Each edge in E is associated (7)

with a normegative weight. Give the K al's gredy algorithm for computing a

minimum spanning tree of G. What is its plexity? Justify your answer.

b) Find an optimal solution to the fraction problem for an instance with number (7)

of items 7, Capacity of the sack W=15, profit associated with the items (pl, p2, p3, p4,

p5, p6, p7)= (10, 5,15, 7, 6,18, 3) and weight associated with each item (wl, w2, w3,

w4, w5, w6,w7)= (2, 3, 5, 7,1, 4,1).

OR
16 a) Let G= (V, E) be a directed graph with vertex set v and edge set E. Each edge is (7)

associated with non-negative weight. Give Dijkstra's algorithm to find a shortest path

from a given vertex in V to all other vertices. What is its time complexity? Justify your

answer.

b) Give the Divide and conquer algorithm for 2-way merge sort and calculate its (7)

time complexity.

Module IV
17 a) Givenachainof4matrices<Al, A2, A3, A4>withdimensions <5x6>,<6x4>, (9)

<4 x 8>, and <8 x 10>. Fully parenthesisze the given matrices so that the number

of scalar multiplications required to compute their product is minimum. What is

the value of optimum number of scalr multiplications?

b) Let G= (V, E) be a directed graph with vertex set v and edge set E. Each directed (5)

edge in E is associated with real valued weights® Let W be the wieight adjacency

matrix of the given graph G. Give the Floyd-Warshall algorithm for computing

all pair shortest paths in G and analyse its time complexity.

OR
18 a) FindtheminimumTSptourforthegivengraph (8)

Page 3of 4
 1200CST306052301

b) Discuss the control abstraction used in backtracking design technique. Draw the (6)

state space tree for 4-queens problem

Module V

19 a) LetG=(V,E)begraphwithvertexsetvandedge . Prove that the CLIQUE (9)

problem, ie., whether there exist a clique of size k in G, is NP-complete.

b) What is meant by approximation ratio of an approximation algorithm? Define the (5)

notions of polynomial time approximation scheme and fully polynomial time

approximation scheme.

OR
20 a) Give the randomized version ofquicksolt algorithm and perform its expected running (9)

time analysis.

b) Define the Bin Packing problem and explain about the First Fit strategy for (5)

solving it.
****

Page 4of 4