Consider a “superstack” data structure which supports four operations: create, push, pop, and superpop. The four operations are implemented using an underlying standard stack S as shown below. def create(): S = Stack.create() def push(x): S.push(x) def pop(): return S.pop() def superpop(k,A): // k is an integer, A is an array with size >= k i = 0 while i < k A[i] = S.pop() i = i + 1 Show that each of these operations uses a constant amortized number of stack operations. In your solution: • Define your potential function Φ. • State, for each operation, its actual time, the change in potential, and the amortized time. 3. Suppose we add a superpush operation to the superstack from Problem 2. The superpush operation is defined as follows: def superpush(k,A): // k is an integer, A is an array with size >= k i = 0 while i < k S.push(A[i]) i = i + 1 Is it still true that each of the superstack operations uses a constant amortized number of stack operations? Answer YES or NO. • If your answer is YES, give an amortized analysis as in the previous problem. (If you need to use a different potential function that is fine, just be sure to define it.) • If your answer is NO, explain why.
Consider a “superstack” data structure which supports four operations: create, push, pop, and
superpop. The four operations are implemented using an underlying standard stack S as shown
below.
def create():
S = Stack.create()
def push(x):
S.push(x)
def pop():
return S.pop()
def superpop(k,A): // k is an integer, A is an array with size >= k
i = 0
while i < k
A[i] = S.pop()
i = i + 1
Show that each of these operations uses a constant amortized number of stack operations. In your
solution:
• Define your potential function Φ.
• State, for each operation, its actual time, the change in potential, and the amortized time.
3. Suppose we add a superpush operation to the superstack from Problem 2. The superpush operation
is defined as follows:
def superpush(k,A): // k is an integer, A is an array with size >= k
i = 0
while i < k
S.push(A[i])
i = i + 1
Is it still true that each of the superstack operations uses a constant amortized number of stack
operations? Answer YES or NO.
• If your answer is YES, give an amortized analysis as in the previous problem. (If you need to
use a different potential function that is fine, just be sure to define it.)
• If your answer is NO, explain why.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
