Code No:R23210S3
R23
Examinations, November-
2024
Regular
II B. Tech ISemester
STRUCTURES AND
ALGORITHMS ANALYSIS
ADVANCED DATA
(C'oMmon tu
CSECSF(AlRML),CSE(A),.CSEDS)CSE(AI&DS),CSE(CS),CSE(TOT&CSTBCT),
C S E C S & B S ) , C S & B S , A J & D S , C S , A I & M L , C S & D , C O S )
Max. Marks: 70
Time: 3hours
two parts (Part-A and Part-bB)
Note: 1. Question Paper consists of
2. Answer ALL the question in Part-AQuestion from each unit
Questions, each
3. Answer any FIVE
from Part-B
4.AllQuestions carry Equal Marks
PART -A (10x 2Marks=2OM)
1. a) Define big Oh notation.
(2M)
b) Detine AVL tree.
(2M)
c) Define min-heap.
(2M)
d) What is convex hull?
(2M)
e) Define dynamic programming.
) Discuss briefly about Travelling Sales man Problem. (2M)
g) Define LIFO branch and bound. (2M)
h) State and explain graph coloring problem. (2M)
i) Explain the concept of polynomial-time reduction between decisionproblems. (2M)
j) Define NP hard problem. (2M)
PART-B (5x10Marks=5OM)
UNIT-I
2. a) relation
The running time of an algorithm is represented by the following recurrence (1OM)
if ns3
Tin)=r4-cn otherwise
Find the time complexity of an algorithm
OR
b) Define Btree. Show how to insert and delete an element from B tree.
(1OM)
lof 2
, Jde No: R2321053 R23
UNIT-II
(10M)
a) Define Max-heap. Write Max-Heapify algorithm that maintain max-heap
property.
OR
(10M)
b) DVide and conquer paradigm involves three steps at each level of recursion.
What are all they? Show that merge-sort algorithm closely follows these steps.
Mlustrate the operation of merge sort on the array A=(3,41,52,26,38,57,9,49}
UNIT-II
(10M)
a) What is Optimal Binary Search Tree? Explain in detail the implementation of
OBST With an example.
OR
Find an optimal sequence
(10M)
b) State the Job - Sequencing with deadlines problem.
(20,15,10,5, J)anddeadlines
tothe n=5 Jobs where profits (P1.P2.P3.P4.P5) =
(d1,d2,d3,d4,d5) =(2,2,1,3,3).
UNIT-IV
algorithm. Explain how to find (10M)
a) Give the 0/1 K napsack Branch and Bound
optimal solution using variable tuple sized approach.
OR
state space (10M)
backtracking technique? Draw the
b) Solve the 8 queen problem using
tree?
UNIT-V
explain how to solve NPC problem
(10M)
). a) What is NP-complete problem and also
using reduction method.
OR
(10M)
theorem, indetail.
b) State and explain Cooks
R23
Examinations, November-
2024
Regular
II B. Tech ISemester
STRUCTURES AND
ALGORITHMS ANALYSIS
ADVANCED DATA
(C'oMmon tu
CSECSF(AlRML),CSE(A),.CSEDS)CSE(AI&DS),CSE(CS),CSE(TOT&CSTBCT),
C S E C S & B S ) , C S & B S , A J & D S , C S , A I & M L , C S & D , C O S )
Max. Marks: 70
Time: 3hours
two parts (Part-A and Part-bB)
Note: 1. Question Paper consists of
2. Answer ALL the question in Part-AQuestion from each unit
Questions, each
3. Answer any FIVE
from Part-B
4.AllQuestions carry Equal Marks
PART -A (10x 2Marks=2OM)
1. a) Define big Oh notation.
(2M)
b) Detine AVL tree.
(2M)
c) Define min-heap.
(2M)
d) What is convex hull?
(2M)
e) Define dynamic programming.
) Discuss briefly about Travelling Sales man Problem. (2M)
g) Define LIFO branch and bound. (2M)
h) State and explain graph coloring problem. (2M)
i) Explain the concept of polynomial-time reduction between decisionproblems. (2M)
j) Define NP hard problem. (2M)
PART-B (5x10Marks=5OM)
UNIT-I
2. a) relation
The running time of an algorithm is represented by the following recurrence (1OM)
if ns3
Tin)=r4-cn otherwise
Find the time complexity of an algorithm
OR
b) Define Btree. Show how to insert and delete an element from B tree.
(1OM)
lof 2
, Jde No: R2321053 R23
UNIT-II
(10M)
a) Define Max-heap. Write Max-Heapify algorithm that maintain max-heap
property.
OR
(10M)
b) DVide and conquer paradigm involves three steps at each level of recursion.
What are all they? Show that merge-sort algorithm closely follows these steps.
Mlustrate the operation of merge sort on the array A=(3,41,52,26,38,57,9,49}
UNIT-II
(10M)
a) What is Optimal Binary Search Tree? Explain in detail the implementation of
OBST With an example.
OR
Find an optimal sequence
(10M)
b) State the Job - Sequencing with deadlines problem.
(20,15,10,5, J)anddeadlines
tothe n=5 Jobs where profits (P1.P2.P3.P4.P5) =
(d1,d2,d3,d4,d5) =(2,2,1,3,3).
UNIT-IV
algorithm. Explain how to find (10M)
a) Give the 0/1 K napsack Branch and Bound
optimal solution using variable tuple sized approach.
OR
state space (10M)
backtracking technique? Draw the
b) Solve the 8 queen problem using
tree?
UNIT-V
explain how to solve NPC problem
(10M)
). a) What is NP-complete problem and also
using reduction method.
OR
(10M)
theorem, indetail.
b) State and explain Cooks
