My Journey Towards Emptiness!!: 03/01/2009

Accounting Method is an elegant technique for amortized analysis of the data structures. Most of us should have encountered Dynamic data structures (which need to expand and contract to maintain some invariant) at some point of time. A stack implementation is one example of a dynamic data structure. As we perform pop operation on the stack eventually it become full (over-flow), at this stage we might choose to increase (may be by doubling or some other heuristic) the size of the stack. We also want to handle the under-flows i.e. if the number of elements in the stack is too small we might want to relocate the elements into a new stack ( with smaller size ). In general the dynamic data structures have a parameter called the load factor $\alpha$ and our aim is to maintain that. One simple way to maintain this is to handle under-flows and over-flows on demand. Unfortunately this will not give us a $\Theta(1)$ amortized cost per operation on the stack. However we can still get $\Theta(1)$ amortized cost by avoiding this on demand expansion and compaction.

Let denote the number of elements present on the stack after operations (including push and pop). Let denote the allocated size of the stack after operations. We Define a potential energy function $\Phi$ as follows.

$\begin{displaymath} \Phi(i) = 2\times N_i - S_i \end{displaymath}$

Clearly $\Phi(0) = 0$ . The amortized cost of the push operation which does not require an expansion of the stack is as follows.

$\begin{displaymath} \begin{array}{rcl} & = & \mbox{actual cost} + \mbox{potenti... ...s N_i - S_i - (2\times (N_i - 1) - S_i) \\ &=& 3 \end{array}\end{displaymath}$

The amortized cost of the push operation which requires doubling of the array is as follows.

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{cost of copying} + \mbox{poten... ... S_i/2) \\ &=& S_i/2 + (0) - (S_i/2-2) \\ &=& 2 \end{array}\end{displaymath}$

The amortized cost of the pop

$\begin{displaymath} \begin{array}{rcl} c^{3}_{i} &=& 1 + (2\times (N_i - 1) - S_i) - (2\times N_i - S_i) \\ &=& -1 \end{array}\end{displaymath}$

From the above we can see that that amortized cost of all the operations is

when we use the doubling heuristic for the stack.

(b)

Let the load factor $\alpha = N_i/S_i$ and let $1-c = 1/2k, k\in \mathbb{R}, c \in (0,1)$ . We use the following heuristic to handle expansion and compaction of the array.

"When $\alpha=1$ (i.e. the array is full) increase the size of the array by times. When $\alpha \leq 1/2k$ (i.e. the array about to under flow) reduce the size of the array by half ()".

We define the following potential function and finally show that the amortized complexity of each of the operations push, pop is .

$\begin{displaymath} \begin{array}{rcl} \Phi(i) &=& \left\{ \begin{array}{rl} k\... ...1/2k \leq \alpha < 1/k$} \\ \end{array} \right. \end{array}\end{displaymath}$

We now prove that the amortized cost of each operation is bounded by a constant. From the previous problem (since the potential function is same as the previous problem when $\alpha \geq 1/k$ ) we can observe that push operation when $\alpha=1$ (expansion) has an amortized cost of . We can also observe that whenever expansion does not occur the amortized cost of the push operation is . So we will concentrate on the other possible situations. We use the notation $\alpha_i$ to indicate the load factor of the array after operations on the array.

Amortized cost of push when $1/2k \leq \alpha_i < 1/k$

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{actual cost} + \mbox{potential... ...+ (S_i/k - N_i) - (S_{i}/k - (N_{i} -1)) \\ &=& 0 \end{array}\end{displaymath}$

Amortized cost of push when $\alpha_i \geq 1/k$ , $\alpha_{i-1} < 1/k$

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{actual cost} + \mbox{potential... ...}{k} S_{i-1} - \frac{k+1}{k} S_{i-1} \\ &<& (k+1) \end{array}\end{displaymath}$

Amortized cost of pop when $1/2k < \alpha_{i},\alpha_{i-1} < 1/k$

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{actual cost} + \mbox{potential... ...) - (S_{i-1}/k - N_{i-1}) \\ &=& 1 + 1 \\ &=& 2 \end{array}\end{displaymath}$

Amortized cost of pop when $\alpha_{i},\alpha_{i-1} \geq 1/k$

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{actual cost} + \mbox{potential... ...S_{i-1}) - (k\times N_{i-1} - S_{i-1}) \\ &=& 1-k \end{array}\end{displaymath}$

Amortized cost of pop when $1/2k < \alpha_{i} < 1/k$ and $\alpha_{i-1} \geq 1/k$

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{actual cost} + \mbox{potential... ...ac{k+1}{k} S_{i} - \frac{k+1}{k} S_{i} \\ &<& k+1 \end{array}\end{displaymath}$

Amortized cost of pop when $\alpha_{i-1} \leq 1/2k$ with compaction

If the

operation is a pop and we find that the load factor $\alpha \leq 1/2k$ then we apply compaction. Compaction reduces the size of the allocated array by

. So after compaction $\alpha \geq 2(1/2k) = 1/k$ . The amortized cost of the pop and compaction is as follows.

$\begin{displaymath} \begin{array}{rcl} &=& \mbox{copying cost} + \mbox{potentia... .../2k\times S_{i-1} - k \\ &\leq& -k \\ &<& 1 \\ \end{array}\end{displaymath}$

We have proved that the amortized cost of both push and pop with all possible values of the load factor $\alpha$ to be .

Exponential function keeps popping up every where stochastic analysis. However it has a crucial property which is often exploited during the analysis. The property I'm referring to is R(X+Y) = R(Y)R(Y) (e.g. X and Y) could be random variables). Now I prove a strong statement " R(X+Y) = R(X)R(Y) If and Only If R(x) = e^-μt where μ is some constant. The reverse direction (<==) is trivial because we can easily verify the fact by substituting R(x) with e^-μt. In the following we prove that other direction (==>).

One may wonder how about function a^x which also satisfies the semi-group property by inspection. However the μ takes care of that observe that a^x = e^ln(a)x.

My Journey Towards Emptiness!!

Tuesday, March 10, 2009

[TECH] Maintaining a Load Factor (α) in Dynamic Data structures with constant (Θ(1)) amortized cost per operation.

(b)

Amortized cost of push when $1/2k \leq \alpha_i < 1/k$

Amortized cost of push when $\alpha_i \geq 1/k$ , $\alpha_{i-1} < 1/k$

Amortized cost of pop when $1/2k < \alpha_{i},\alpha_{i-1} < 1/k$

Amortized cost of pop when $\alpha_{i},\alpha_{i-1} \geq 1/k$

Amortized cost of pop when $1/2k < \alpha_{i} < 1/k$ and $\alpha_{i-1} \geq 1/k$

Amortized cost of pop when $\alpha_{i-1} \leq 1/2k$ with compaction

[TECH] Exponential function (e^-μt) is the only unique solution satifying R(x+t) = R(x)R(t)(semi-group property).

Blog Archive

My Quotes....