Home | | Programming and Data Structure II | Accounting Method

Chapter: Programming and Data structures : Advanced Non-Linear Data Structures

Accounting Method

Assign differing charges to different operations.

ACCOUNTING METHOD:

 

•         Idea:

 

–   Assign differing charges to different operations.

 

–   The amount of the charge is called amortized cost.

 

–   Amortized cost is more or less than actual cost.

 

– When amortized cost > actual cost, the difference is saved in specific objects as credits.

 

–   The credits can be used by later operations whose amortized cost < actual cost.

 

•         As a comparison, in aggregate analysis, all operations have same amortized costs.

 

•   Conditions:

 

– Suppose actual cost is ci for the ith operation in the sequence, and amortized cost is ci',

 

–   Ã¥i=1n ci' ³åi=1n ci should hold.

 

•         Since we want to show the average cost per operation is small using amortized cost, we need the total amortized cost is an upper bound of total actual cost.

 

•         Holds for all sequences of operations.

 

–   Total credits is Ã¥i=1n ci' - Ã¥i=1n ci , which should be nonnegative,

 

•         Moreover, Ã¥i=1t ci' - Ã¥i=1t ci  ≥0 for any t>0.

 

 

Accounting Method: Stack Operations

 

•         Actual costs:

 

–   PUSH :1, POP :1, MULTIPOP: min(s,k).

 

•         Let assign the following amortized costs:

 

–   PUSH:2, POP: 0, MULTIPOP: 0.

 

•         Similar to a stack of plates in a cafeteria.

 

–   Suppose $1 represents a unit cost.

 

– When pushing a plate, use one dollar to pay the actual cost of the push and leave one dollar on the plate as credit.

 

– Whenever POPing a plate, the one dollar on the plate is used to pay the actual cost of the POP. (Same for MULTIPOP).

 

–   By charging PUSH a little more, do not charge POP or MULTIPOP.

 

 

•         The total amortized cost for n PUSH, POP, MULTIPOP is O(n), thus O(1) for average amortized cost for each operation.

 

•         Conditions hold: total amortized cost ≥total actual cost, and amount of credits never becomes negative.

 

 

Accounting method: binary counter

 

•         Let $1 represent each unit of cost (i.e., the flip of one bit).

 

•         Charge an amortized cost of $2 to set a bit to 1.

 

•         Whenever a bit is set, use $1 to pay the actual cost, and store another $1 on the bit as

 

credit.

 

•         When a bit is reset, the stored $1 pays the cost.

 

•         At any point, a 1 in the counter stores $1, the number of 1‟s is never negative, and so is the total credit.

 

•         At most one bit is set in each operation, so the amortized cost of an operation is at most $2.

 

•         Thus, total amortized cost of n operations is O(n), and average is O(1).

 

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Accounting Method |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.