15-451/651 Algorithms 
9/9/14 Recitation problems

Splay Trees
------------------
Review lecture notes on splay trees

Extra splay tree topics
- Perform split(S,k) and Join(S,T) in O(log n). 
- Augmented BSTs

Ternary Counter
------------------
Suppose we have a binary counter
such that the cost to increment the counter is equal to the number of
bits that need to be flipped.  We saw in class that if the counter
begins at 0, and we increment the counter $n$ times, the amortized
cost per increment is just O(1).  Equivalently, the total cost to
perform all n increments is O(n).

Suppose that we want to be able to both increment and decrement the
counter.

- Show that even without making the counter go negative, it is
possible for a sequence of n operations starting from 0,
allowing both increments 
and decrements, to cost as much as Omega(log n) amortized per operation
(i.e., Omega(n log n) total cost).

- To fix the problem from part (a), 
consider the following redundant ternary number system.
A number is represented by a sequence of trits, 
each of which is 0, +1, or -1.
The value of the number t_{k-1}, ..., t_0
(where each t_i is a trit) is defined to be \sum_{i=0}^{k-1} t_i 2^i.

The process of incrementing a ternary number is analogous to that operation
on binary numbers.  You add 1 to the low order trit.  If the result is 2,
then it is changed to 0, and a carry is propagated to the next trit.  This
process is repeated until no carry results.  Decrementing a number is
similar.  You subtract 1 from the low order trit.  If it becomes -2
then it is replaced by 0, and a borrow is propagated.
 Note that
the same number may have multiple representations (e.g.,
(1)(0)(1) = (1)(1)(-1)).  That's
why this is called a redundant ternary number system.

The cost of an increment or a decrement is the number of trits that
change in the process.  Starting from 0, a sequence of n increments
and decrements are done.  Give a clear, coherent proof that with this
representation, the amortized cost per operation is O(1) (i.e., the
total cost for the n operations is O(n)).  Hint: think about a
``bank account'' or ``potential function'' argument.

Penny Jumper
--------------------
Consider a number line with a penny on every cell with index i<=0. 
You may 'jump' a penny over another penny in either direction, 
however the middle penny is then removed from the number line. 

How far can you get a penny to the right? 

Bonus: Expand this to a 2D grid, and let the initial pennies be on G[i][j] 
for all j<=0. What is the maximum height a penny can reach?

Adversarial Quicksort
--------------------
Give an lower bound argument for quicksort with fixed pivots. 
Hint: Be the adversary