Assignment #1
Advanced Data Structures and Algorithms- CS1114
Q1. If the set of stack operations included a MULTIPUSH operation, which pushes k items onto
the stack, would the O(1) bound on the amortized cost of stack operations continue to hold?
Ans : No the time complexity of such a series of operations depends on the number of
pushes(pops vice versa ) could be made since one MULTIPUSH needs Theta(k) time,
performing N-MULTIPUS operations, each with K elements would take Theta(kn) time, leading
to amortized cost of Theta(k).
Q2. Show that if a DECREMENT operation were included in the k-bit counter example, n
operations could cost as much as ɵ(n.k) time.
Ans : In the worst case, going from 1[k-10’s] (i.e 1000-> 0111) takes k flips. Could do any
sequence of increment and decrement from 1000 -> 0111-> (n times), which is theta(nk).
Q3. Suppose we perform a sequence of n operations on a data structure in which the ith operation
costs ‘i’ if ‘I' is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the
amortized cost per operation.
Ans: Look at a sequence of n operations. Let k = floor(lg(n)). All operations cost equal to 1+2*(1-
2^k)/(1-2) + n – k – 1 = 2*2^k + n – k – 2 = O(n), than each operation cost equal to O(n)/n = O(1).
Q4. Consider an ordinary binary min-heap data structure with n elements supporting the
instructions INSERT and EXTRACT-MIN in O(lg n) worst-case time. Give a potential function
such that the amortized cost of INSERT is O(lg n) and the amortized cost of EXTRACT-MIN is
O(1), and show that it works.
Ans: First look at what extraMin does ,
So it does - Extract the root,O(1) actual time;
- Replace it with the last element x in the heap and repair the heap by heap
down/ip.
- It takes O(log n ) time, which is the depth of the heap.
So now, for getting O(1) amortized time for extract -min, the last element x must have enough
“potential “ for repairing the heap . this potential of x must be in order of its depth.
Let us have K element and the weight of Kth element is Wk, in the heap as its depth, i.e so we can
say
Wk =log k ---- (1)
Now thus , the potential function Phi for the heap Hn of n element can be defined as : Phi(Hn) =
Sum of all Wk , k = 1,2,3…….n;
Here phi(H) >0.
So we can say Phi(Hn) = n log n.
Checking :- for insert :- “ pay” a cost of 2 log n for :-
1. Pay actual cost of insert (log n )
2. Raise potential for the new elements.
Then for Extract Min : - O(1) amortized, reports the heap use the potential Log n of the last element
c, as mentioned above.
In a nutshell, when insert, potential increases and this can be afforded by paying insert more, when
extract min, potential decreases by a right moment of the cost of repairing.
So clearly see that insert is O(log n ) amortized and Extract Min is O(1) amortized.
Q5. What is the total cost of executing n of the stack operations PUSH, POP, and MULTIPOP,
assuming that the stack begins with s0 objects and finishes with sn objects?
Ans : Let Theta be the potential function that returns the number of elements in the stack. We
know that for this potential function, we have amortized cost 2 for PUSH operation and amortized
cost 0 for POP and MULTIPOP operations.
The total amortized cost is
n∑ i=1 cˆi = n ∑ i=1 ci +Φ(Dn)−Φ(D0).
Using the potential function and the known amortized costs, we can rewrite the equation as
n ∑ i=1 ci = n ∑ i=1 cˆi +Φ(D0)−Φ(Dn) = n ∑ i=1 cˆi +s0 −sn ≤ 2n+s0 −sn,
Which gives is the total cost of O(n+(s0 -sn )). If sn ≥ s0, then this equals to O(n), that is , if the stack grwos,
then the work done is limited by the number of operations.
Submitted by : Jatin Jasaiwal
Roll : 2017BTECHCSE004
