GO LEARNERZ
Where Learnerz Meets progress
KTU BTECH ONLINE CLASSES
KTU CRASH COURSES| KTU MOCK TEST | KTU
PREVIOUS YEAR QUESTION PAPER SOLVED
[Link]
C 0300csT306052202
Reg No.: H
APJ ABDUL KATAM TECHNOLOGICAL UN
Sixth Semester [Link] 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 (;) * [Link] 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
[Link]
For More Lecture Videos: [Link]
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)
[Link] the source as node A.
Page2of4
[Link]
For More Lecture Videos: [Link]
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
[Link]
For More Lecture Videos: [Link]
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 [Link]. (7)
Discuss Las Vegas and Montc Car{o algorithms with a suitah c@.
rl ***
.r..
Pagp !*of4
[Link]
For More Lecture Videos: [Link]
WHERE LEARNERS
MEETS PROGRESS
ELEVATE YOUR EXPERIENCE
Easy To Use, Streamlined User
Anywhere, Anytime Interface
Personalized 24 Hours
Experience Support
Why Choose Us?
Top Faculties and Free Webinars on Subject wise community for
Mentor Support Exam preparation discussion and doubt solving
Well Formatted Solved Previous Year Subject Wise Materials
Recorded classes Questions With Detailed
Video
[Link]
Contact Us +918089464002
golearnerz