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