Carnegie Mellon University, Computer Science Department
Graduate Algorithms 15-750, Spring 2004,  
Instructor: Manuel Blum
TA: Doru Balcan

  
Homework Assignment #4

Important Note: Each problem is worth 10 points. The solutions 
are expected by Friday, Feb 13, at the beginning of the class 
(IN CLASS). Any hand-ins after this deadline shall not be taken 
into consideration.

Another Note: Parts a) and b) of Problem 2 were taken from 
Jon Bentley's "Programming Pearls", 1986 (Problem A, page 11).
    Problem 3, part a) is adapted from the same source (Pb. 2, page 17).


1. Compute E_{n,n}, the expected depth of node n, in a treap with 
n elements, where the expectation is taken over random permutations 
of n elements (each of these permutations - equally likely).
   What is the variance of node n's depth?


2. Given a tape that contains at most 1,000,000 twenty-bit 
integers in random order, find a twenty-bit integer that isn't 
on the tape (and there must be at least one missing - Why?).
  a. How would you solve this problem with ample quantities of 
main memory? 
  b. How would you solve it if you had two tape drives, but
only a few dozen words of main memory?
  c. How would you solve it with only one tape drive (which contains 
the input), and only 48 words of main memory?


3. Given a tape containing 1,050,000 twenty-bit integers, how 
can you find one that appears at least twice? (Explain, first,
why this must happen.) You may assume:
  a. two tape drives
  b. one tape drive
   

4. a. Consider the following tree:

                          o 12                   
                         /
                      1 o
                S        \
                          o 11
                         /
                      2 o
                         \
                          o 10
                         /
                      3 o
                         \
                          o 9
                         /
                      4 o
                         \
                          o 8
                         /
                      5 o
                         \
                          o 7
                         /
                      6 o

  (The splay tree is a zig-zag chain, with 12 nodes.)
  How does this tree look like after performing splay(6)?
  
  b. What happens with the depth of the tree in general, i.e. when 
the initial zig-zag chain has n vertices, and we apply the "splay" 
operation on the element of maximum depth?



5. a. Give a sequence of splays that transform the tree on the top 
right-hand side, of page 61 (in Kozen), into the one on the top 
left-hand side, of page 60? 
  
   b. (Extra credit) Is the splay operation "invertible"? 
(By "invertible", we mean: if you can get from tree S_1 to tree S_2
by a sequence of splays, then you can get from tree S_2 to tree S_1
by a sequence of splays.)