Hi, Im learning about amortized analysis and am not sure what accounting method is for b). Could you provide an example of accounting method or any hints on how to get started?

Transcribed Image Text:

2. [14] Suppose that we have an array A[1,2,...] (index starting at 1) that is sufficiently large, and supports the following two operations INSERT and PRINT-AND-CUT (where k is a global variable initially set to 0): 1 def INSERT (x): 2 k = k + 1 3 A[k] = 4 5 def 6 7 8 PRINT-AND-CUT (): for i from 1 to k: print A[k] k = k // 2 # integer division We define the cost of the above two operations as follows: The cost of INSERT is exactly 1. • The cost of PRINT-AND-CUT is exactly the value of k before the operation is executed. Now consider any sequence of n of the above two operations. Starting with k = 0, perform an amortized analysis using the following two techniques. (a) Use the aggregate method: First, describe the worst-case sequence that has the largest possible total cost, then find the upper-bound on the amortized cost per operation by dividing the total cost of the sequence by the number of operations in the sequence. (b) Use the accounting method: Charge each inserted element the smallest amount of "dollars" such that the total amount charged always covers the total cost of the operations. The charged amount for each insert will be an upper-bound on the amortized cost per operation. 2. [14] Suppose that we have an array A[1,2,...] (index starting at 1) that is sufficiently large, and supports the following two operations INSERT and PRINT-AND-CUT (where k is a global variable initially set to 0): 1 def INSERT (x): 2 k = k + 1 3 A[k] = 4 5 def 6 7 8 PRINT-AND-CUT (): for i from 1 to k: print A[k] k = k // 2 # integer division We define the cost of the above two operations as follows: The cost of INSERT is exactly 1. • The cost of PRINT-AND-CUT is exactly the value of k before the operation is executed. Now consider any sequence of n of the above two operations. Starting with k = 0, perform an amortized analysis using the following two techniques. (a) Use the aggregate method: First, describe the worst-case sequence that has the largest possible total cost, then find the upper-bound on the amortized cost per operation by dividing the total cost of the sequence by the number of operations in the sequence. (b) Use the accounting method: Charge each inserted element the smallest amount of "dollars" such that the total amount charged always covers the total cost of the operations. The charged amount for each insert will be an upper-bound on the amortized cost per operation.

Answer rating: 100% (QA)

Answer a In the aggregate method amortized cost of a operations must be an upper bound the actual co... View the full answer