No. of Pages: 4 ௦
AP} ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIRST SENIESTER M.TECH DEGREE EXAMINATION, DECENfBER 2018

Computer Science and Engineering

Stream(s):
1. Computer Science and Eggineering
2. Information Security

01 056105 Advanced Data Structures and Algorithms

Answer any twofull questions from each part
Limit answers to the required points.

Max. Marks: 60 Duration: 3 hours
PART A

1. 8. A sequence of Stack operations is performed on a Stack whose size never 4 exceeds (९.
After every k operations, a copy of the entire Stack is made for backup purposes. Show
that the cost of n Stack operations, including copying the Stack, is O(n) by assigning
suitable amortized costs to the various Stack operations.

b. A sequence n of operations is performed on a data structure. The i-th 5 operation
costs i if i is an exact power of 3, and | otherwise. Use potential method to
determine the amorazed cost per operation.

2. a. Show the binomial heap that results after each operation listed below: 4
i. Insert the following numbers, in order, into heap HI: 12, 7, 25, 15, 28,
33, 41 (show heap HI after each step).
ii. Insert the following numbers, in order, into heap H2: 18, 3, 37, 6 (show
heap 112 after each step). iii. Merge heaps HI and 112.
iv. Extract the minimum key from the merged heap.

1

b. Consider a tree implementation for the union/find problem in which the 5
smaller set is merged to the larger and the name of the set is taken to be the
element stored at the root of the tree. Suppose we initialize our sets so that each
integer between | and 8 (inclusive) is contained within its own set.