C 0300csT306052202

Reg No.: H
APJ ABDUL KATAM TECHNOLOGICAL UN
Sixth Semester B.Tech Degree Examination June 2022 ed

Course Code: CST306

Course Name: ALGORITHM ANALYSIS AND DESIGN
Max. Marks: 100 Duration: 3 Hours
PART A
Answer aII questions, eoch corries 3 morks. Marks

I Let f (n) :3n3 + 2nz + 3 for an algorithm, Let g(n) = n3. prove that f(n) of this (3)
algorithm is in O(n3)
2 Solve the recurrence T(n) :ta (;) * nlogn.using Master theorem. (3)

3 Discuss briefly the heuristics, union by rank and path compression, to improve the (3)
running time of disjoint set data structure.
4 consider the directed acyclic graph G=(v,E) given in the following figure. (3)

Find any topologicalordering of G.

5 Give the control abstraction of Greedy strategy. (3)
r6 Why Strassen's matrix multiplication algorithm is better than traditional divide (3)
and conquer algorithm for multilpying two square matrices? what is the
recurence for'the number of computational steps taken by Strassen's atgorithm
and its time complexity? :

!7 Discuss briefly the elements of dynamic g)gramming with a suitable example. ' (3)
8 Compare backtracking and branch-and-bound design techniques. (3)
9 domains.
Define P, NP and NP complete (3)
l0 Compare Las Vegas and Monte Carlo algorithms. (3)
PART B
" Answer onefull questionfrom eoch module, eoch carries 14 morks.
Module I
I I a) Illustrate best case, average case and worst-case complexity with insertion sort (9)
algorithm.

Page lof4
 0300csT3060s2202

b) Give the general idea oithe substitution method for solving recuffences. Solve the (5)
following recunence usingsubstitution method.
tTlt,
r(n)=zrf)+n
OR
12 a) Solve the following recurrence using recursion tree method (8)

D r@):r(;) +r(!)+cn
2) r@):zrO+n
b) Define Big Oh, Big Omega and Theta notations and illustrate them graphicatly. (6)
Module ll
13 a) Give Breadth First Search algorithm for graph traversal. Perform its complexity (7)
'f analysis.
b) Define AVL tree. Construct an AVL tree by inserting the keys: 44,17,32,78,50, (7)
88, 48, 62, 54 into an initially empty tree. Write clearly the type of rotation
performed at the time of each insertion.

OR
14 a) Give Depth First Serach algorith for graph traversal. Perform its time complexity (7)
analysis.
b) Perfiorm DFS traversal on the following graph starting from node A. When (7)
multiple nodes are available for next traversal choose nodes in alphabetical order.
Classiff the edges ofthe graph into different category.

Module lll
15 a) Illustrate the divide and conquer approach by applying 2 way mergO sort for the (7)
inptrt array: fl5,l2,l4,l7,ll,l3,l2,l6]. Write the recurrence for merge sort and
give the complexity.

5) Apply Dijkstra's algorithm for single source shortest path to solve the following (7)
graph.Assume the source as node A.

Page2of4
 0300csr306052202

OR

16 a) Consider the following instance of Fractional Knapsack problem with 3 objects. (7)
The capacity of the knapsack is 20 units. The weights and profits of the 3 items
resprctively are nepresented by the vectors (wl,w2,w3) : (18,15,10) and

$tl,p2,p3\125,24,15). Using a greedy strategy compute the optimal solution to

this instance.
b) Apply Kruskal algorithm to find minimum cost spanning tree for the following (7)
graph

Module lV
17 a) Discuss Floyd-Warshall algorithm for all pair shortest path problem. Solve the (8)
following instance using the algorithm.

b) Discuss the control abstraction used in backtracking design technique. Draw the .(6)
state space tree for 4-queens problem.

OR

18 a) Discuss the elements of dynamic programming by considering the matrix chain (5)
i'
I
l
multiplication problem.
I

I
Page 3of4
I

I
 --+2.

03*csT3ffitrnzs2

b) Define Travellint Satesnsr koblem (TSP).Apply hanch sd bound technique (9)

trlo*itqI i
to solve tlre oTTSP. Assume tha the st#ing vcrtex as A. Drarv
the stats s@ tiee futAcfi *p.

ltfodubV
: i.
I9 a) Prave that CLIQtIE troblem is NP Complete. (?)
b) Writ€ randqnizd quickset algorithm and perform its expeed
1ryrrrg
tirn€ (7)
analysis.

2t e) $fine appwhstbilt algori*m. Give an appnoximation a$uithm for bin .:

(7)
pac*ing usiry first fit heuristb and give its approxim*ion ralio.
b) Dircuss the dvantages of rardolnized algorithms over determinigb.tlgorithms. (7)
Discuss Las Vegas and Montc Car{o algorithms with a suitah c@.
rl ***

.r..

Pagp !*of4