d) Using the accounting method, assign the lowest (integer) amortized cost possi
ID: 3570451 • Letter: D
Question
d) Using the accounting method, assign the lowest (integer) amortized cost possible to the enqueue operation and to the dequeue operation so that after any sequence of n1 enqueues and n2 dequeues, n1 > = n2, the amortized cost is > = the actual cost. Explain why this works. e) Show that the total amortized cost, which is an upper bound for the actual cost, over a sequence of n operations is 0(n). Consider a queue data structure, where the two operations of interest are enqueue (at the back of the queue) and dequeue (from the front of the queue). A queue is thus a FIFO (first in -first out) structure. Suppose we implement a queue by using two stacks, A and B, which support operations of push and pop, as follows: enqueue(x): push x onto stack A dequeue: if B is not empty return x = pop B if B is empty repeat until A is empty x = pop A push x onto stack B return x = pop BExplanation / Answer
Anwer 1: It's easy to see that this algorithm is correct. Here we'll just worry about the running time. (I'm going to ignore the cost of checking of stack2 is empty, and only measure the cost in terms of the number of PUSHs and POPs that are done.) Claim: the amortized cost of ENQUEUE is 3 and DEQUEUE is 1. Proof 1 (aggregate method): As an element flows through the two-stack data structure, it's PUSHed at most twice and POPPed at most twice. This shows that we can assign an amortized cost of 4 to ENQUEUE and 0 to DEQUEUE. To get the desired result, note that if an element is not DEQUEUED it's only PUSHED twice and POPPED once. So the cost of 3 is paid for by the cost of 3 per ENQUEUE. The last POP is paid for by the DEQUEUE (if it happens). Proof 2 (banker's method): Maintain a collection of tokens on stack1. In fact, keep 2 tokens for each thing in the stack. When we ENQUEUE, we have three tokens to work with. We use one to push the element onto stack1, and the other two are put on the element for future use. When we have to move stack1 into stack2, we have enough tokens in the stack to pay for the move (one POP and one PUSH for each element). Finally, the last pop done by the DEQUEUE is paid for by the 1 we allocated for it. QED. Answer 2: For each Enqueqe and Dequeue operation cost is function of a costant. so for n operations the total cose will be in terms of n only as n* some constant is always linear. so the total cost is O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.