15-451 Algorithms		9/22/04
							RECITATION NOTES
=======================================================================
The plan for today is to do some amortized analysis plus practice for
the quiz by going over last year's.   Also, hand back homeworks.

=======================================================================

Problem 1:  Amortized Analysis

In lecture we discussed the "implementing a stack as an array"
problem, and decided that doubling the array whenever it gets full
does well in an amortized sense.  Now, what if we don't want to be
space hogs. If we do a lot of pops and the stack gets small, then we
want to resize the array to make it smaller.  

Say k = number of elements and L = size of array.

Strategy #1: when we pop from k = L/2, then cut the array size
in half.  Is this a good strategy?  Why or why not??

How about cutting in half when pop from k=L/4?

Claim: amortized cost is at most 3 per operation.

Proof: Consider the interval between successive array resizes.  The
important point is that after each resize operation, the array is
exactly half full.

If it's a double, then there must have been at least 
L/2 pushes since the last resize.  This can pay for the work.

If it's a halving, then there must have been at least
L/4 pops, and these can be used to pay for the resize.

If you want to use the bank-account method, you can think of each
push or pop as paying $1 to perform the operation and putting $2 in
the bank to pay for a possible future resizing.

==============================================================================

Last Year's Quiz 1.  You can go problem-by-problem, giving the
question and then giving students time to work it out, and then having
students present their solutions.

Problem 1: solve these recurrences (the actual quiz was multiple
choice just for grading purposes):

   T(n) = 4 T(n/4) + n.

   T(n) = 16 T(n/4) + n.

   T(n) = T(n-4) + n^3.

   T(n) = T(n/4) + T(n/2) + n.


Problem 2 (amortized analysis):

Suppose we're doing a sequence of operations (numbered 1, 2, 3,...)
such that the ith operation: 

     - costs 1 if i is *not* a power of 2, and
     - costs i if i *is* a power of 2.

For example, the following table shows the costs for each of the first
few operations: 

   operation number:   1   2   3   4   5   6   7   8   9 ...
   cost:               1   2   1   4   1   1   1   8   1 ...


Give the best upper bound you can on the amortized cost per operation.
[quiz was multiple-choice with choices 1,2,3,4,log(n),n]


Problem 3: Does there exist an algorithm that makes at most four comparisons
to sort any array of size 4?  Why or why not?


Problem 4: Consider a random permutation of the numbers 1,2,...,n.
Let's call a number in this permutation a Biggie if it's greater
than all the numbers to its left.  Note that the number that ends up
in the first position is definitely a Biggie.

a) What is the probability that a number in position i is a Biggie?
(The positions are numbered from left to right, starting from 1.)


b)Building on your answer above, what is the expected number of Biggies
in the whole array?


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

Answers:
1: n*log(n), n^2, n^4, n.
2: Answer is 3.  Two natural ways of analyzing are:

 (a) summing up the totals and dividing by n.  In this case, the
 powers of 2 give at most 1+2+4+8+...+n < 2n, and the non-powers-of-2
 give n - log(n) < n, so the total is < 3n, or amortized 3 per
 operation.

 (b) the piggy-bank method: if every operation since the last power of
 2 pays $2 extra, that produces enough money to pay for the expensive
 operation.  So, in this accounting, the cheap operations pay $3, and
 the expensive operations pay $2, for an amortized cost < $3.

 Also, the answer isn't $2 since we can see that the first 8 operations
 cost > 16.

3: No. 4 < lg(4!). [You did this on the mini].

4a: 1/i.
4b: H_n.