TUTORIAL 8: Amortized analysis
==============================

--------------------------------------------------------------------------
Example 1:

operation           description                               actual cost
PUSH                pushes an item on to the stack            1
MULTIPOP(k)         pops k items from the stack               min(k,s)
where s is the number of items on the stack. Note: we cannot pop items if the
stack is empty.

What would be the worst-case sequence of operations? (Let the students guess).
One possible suggestion is push multipop(1) push multipop(1) ...
Here each operation has cost 1, so the total cost of n operations = n

Another suggestion is n-1 pushes followed by a multipop:
    push push push ...  multipop(n-1)
Each push has cost 1 and the multipop has cost n-1.
Thus the total cost is 2n-2.

This gives us some intuition into the expected amortized cost.

Method 1: Aggregate method
---------------------------

Consider the cost of the push and multipop operations separately.

cost of worst-case sequence = cost of all pushes in sequence + cost of all
multipops

The two keys things to notice here are:
1) In any sequence of n pushes and multipops, the total cost of pushes is at
most n.
2) An item cannot be popped from the stack without first being pushed on to the
stack, thus the cost of all multipops in any sequence <= cost of all pushes.

So, cost of worst-case sequence <= 2 x (cost of all pushes in sequence) <= 2n.
This gives us an amortized cost of 2n/n = 2 for each operation in the sequence.

Method 2: Accounting Method
---------------------------

Here we charge each operation as small cost as possible, but we *cannot* go
into debt by spending more than we have saved.

if actual cost < amortized cost, we credit the extra charge to the "bank"
if amortized cost < actual cost, we spend some savings in the bank... but we
cannot use more than we have saved.

Let amortized cost of push = 2, amortized cost of pop = 0.
When we push an item on to the stack, we use $1 to pay for the push operation,
and we put $1 in the bank. We use the saved $1 later when we pop the item from
the stack.


cost of worst-case sequence <= \sum amortized cost of pushes + \sum amortized
cost of multipops
                             = \sum (2) + \sum(0)
                            <= 2n
This gives us an amortized cost of 2n/n = 2 for each operation in the sequence.


-----------------------------------------------------------------------------

Example 2: Solve the following question with them
(see whether they can figure out the answer themselves):

\medskip\noindent
Suppose we implement \textsc{Min-Heap} as an array, as follows.

\medskip\noindent
To perform an \textsc{Insert} operation,
        if the array is not full, then we proceed as explained in class.
If the array is full,
        then we first move the elements of the heap from the current array
        into a new array of \emph{four} times the size of the current array,
        and we then perform the insertion in the new (quarter-full) array.

\medskip\noindent
To perform an \textsc{ExtractMin} operation,
        if the array is more than a $1 \over 8$-th full,
        then we proceed as explained in class.
If the array is only $1 \over 8$-th full,
        then we first move the elements of the heap
        from the current array
        into a new array of half the size,
        and we then perform the \textsc{ExtractMin}
        in the new (quarter-full) array.

\medskip\noindent
Suppose that the heap is initially empty, and we perform
        an arbitrary sequence of $n$ \textsc{Insert} and \textsc{ExtractMin}
        operations.
For each of the following two questions
	circle the correct answer.

The amortised cost per operation is:
------------------------------------

\begin{enumerate}
\item $\Theta(1)$
\item $\Theta(\log^* n)$
\item $\Theta(\log n)$		%this is the answer
\item $\Theta(\log^2 n)$
\item $\Theta(n)$
\item $\Theta(n\log n)$
\end{enumerate}

The worst-case cost for an individual operation in such a sequence is:
----------------------------------------------------------------------

\begin{enumerate}
\item $\Theta(1)$
\item $\Theta(\log^* n)$
\item $\Theta(\log n)$
\item $\Theta(\log^2 n)$
\item $\Theta(n)$		%this is the answer
\item $\Theta(n\log n)$
\end{enumerate}