No. of Pages: 4

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIRST SEMESTER M.TECH DEGREE EXAMINATION, DECEMBER 2017

Branch: Computer Science and Engineering

Stream(s):
1. Computer Science and Engineering

2. Information Security

01056105: Advanced Data Structures and Algorithms

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

Max. Marks: 60 Duration: 3 hours
PART A

1. a.Let D be a data structure whose operations have an amortized
cost of at most 4
t.
i. Can you give a guaranteed bound on the cost of a
sequence of का operations on D? If 50, state this bound. Justify your
answer.

11 . Canyou give a guaranteed bound on the cost Of an individual operation
on D? If so, state this bound. Justify your answer.

b. Suppose we implement ‏و‎ [|೦ queue using two stacks called InStack and 5
OutStack as follows. An element is inserted into the queue by pushing it
into the InStack. An element is extracted from the queue by popping it from the OutStack. If the OutStack is
empty after an extraction operation, then all elements currently in the InStack are transferred to OutStack, but
inthe reverse order. Show that a sequence of I insertions and E extractions
requires only O(KE) time, using an appropriate potential function.

2. a.Startirtg from the empty binomial max--heap, perform the

following 4 operations

Insert 4, 12, 8, 24, 6, 18, and 16, in this order.

Explain how to delete the maximum from your resulting
max-—heap