Question 1)a) Define Amortized analysis and list all the techniques used in it. Determine the amortized cost per operation for a sequence of n decrement operation (which subtracts 1 from a binary number) on a counter containing all k bits equal to 1. Display also the counter value and total cost up to 16 decrement operations.
b) Describe potential method and use the same for discovering amortized cost for PUSH, POP and MULTIPOP operations.
Question 2)a) Show the results of inserting the keys B, Q, L and F in order, into an initial tree B-Tree, given below with minimum degree 3.
b) Write B-Tree insert non-full algorithm and also find the total CPU time for executing the same.
Question 3)a) Write and describe with the help of one example a decrease key algorithm in Binomial Heap. Determine the total time for its execution.
b)i) describe the relationship between inserting into a binomial heap and incrementing a binary number and the relationship between uniting two binomial heaps and adding two binary numbers.
ii) Write Binomial-Heap delete procedure with the following assumptions.
(a) There is no way to represent the key - ∞.
(b) Procedure for decrease key and extract minimum key already exists.