Carnegie Mellon University, Computer Science Department Graduate Algorithms 15-750, Spring 2004, Instructor: Manuel Blum TA: Doru Balcan Homework Assignment #4 --- SOLUTIONS 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? Solution: [to be posted] 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? Solution: Here's the discussion + solution in Bentley's "Programming Pearls" [a.] Given a tape that contains at most one million twenty-bit integers in random order, we are to find one twenty-bit integer not on the tape. (There must be at least one missing, because there are 2^20 or 1,048,576 such integers.) With ample main memory, we could use the bit-vector technique [...] and dedicate 131,072 8bit bytes to a bitmap representing the integers seen so far. [b.] The problem, however, also asks how we can find the missing integer if we have only a few dozen words of main memory and several extra tape drives. To set this up as a binary search we have to define a range, a representation for the elements within the range, and a probing method to determine which half of a range holds the missing integer. How can we do this? We'll use as the range a sequence of integers known to contain at least one missing element, and we'll represent the range by a tape containing all the integers in it. The insight is that we can probe a range by counting the elements above and below its midpoint: either the upper or the lower range has at most half the elements in the total range. Because the total range has a missing element, the lesser half must also have a missing element. These are most of the ingredients of a binary search algorithm for the problem; try putting them together yourself before you peek at the solutions to see how Ed Reingold did it. These uses of binary search just scratch the surface of its applications in programming. A root finder uses binary search to solve a single-variable equation by successively halving an interval; numerical analysts call this the bisection method. When the selection algorithm in Solution 10.9 partitions around a random element and then calls itself recursively on all elements on one side of that element, it is using a "randomized" binary search. Other uses of binary search include tree data structures, data processing algorithms that run on card sorters (which use the corresponding decimal search), and program debugging (when a program dies a silent death, where do you place print commands to home in on the guilty statement?). In each of these examples, thinking of the program as a few embellishments on top of the basic binary search algorithm can give the programmer that all-powerful aha! [Ed Reingold's solution of b. -- book, page 165]: It is helpful to view this binary search in terms of the twenty bits that represent each integer. In the first pass of the algorithm we read the (at most) one million input integers and write those with a leading zero bit to one tape and those with a leading one bit to another tape. One Probe \ One of those two tapes contains at most 500,000 integers, so we next use that tape as the current input and repeat the probe process, but this time on the second bit. If the original input tape contains N elements, the first pass will read N integers, the second pass at most N/2, the third pass at most N/4, and so on, so the total running time is proportional to N. The missing integer could be found by sorting on tape and then scanning, but that would require time proportional to N log N. This problem and solution are due to Ed Reingold of the University of Illinois. c. Here is an elegant, randomized solution. In our 48 8-words of main memory, we have enough space to store 16 randomly, independently generated 20-bit words, sorted in increasing order (we only need a negligible time to sort these words). In the remaining 48*8-16*20 = 64 bits we can keep a 1-bit marker (initially 0) for the index of each random word (so we need 16 more bits). Pass once through the tape. For each word we read, we check if it is already among our randomly generated words. (For this, we just make a binary search in a 16-long sorted list - at most 5 comparisons). If we found that a word in memory is on the tape, we mark it, by making its bit equal to 1 (so, we do at most one write operation per tape word). After the pass, we check to see if there is a word among the 16 ones in memory, that was not found on the tape, by checking all the bits. If all bits are marked, we repeat. Otherwise, output one word whose corresponding bit is 0. Let's compute now the probability that all the 16 random words are on the tape. Pr(x1, x2, ..., x16 are all on the tape) = = Pr(x1 is on the tape)*P(x2 is on the tape)*...*P(x16 is on the tape) = Pr(x1 is on the tape) ^ 16 (since the words are independently, identically distributed - obviously uniform in the 20-bit word space) <= ( 10^6 / 2^20 )^16 = (5^6 / 2^14)^16 = (5^3/2^7)^32 ~ 0.468 So, the probability of success is more than 50%. Since the number of passes is geometrically distributed, the expected number of passes is then at most 2. 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 Solution: This problem is somehow similar to the previous one. a. [Solution in the book, page 165] Binary search finds an element that occurs at least twice by recursively searching the subinterval that contains more than half of the integers. My original solution did not guarantee that the number of integers is halved in each iteration, so the worst-case run time of its log2 N passes was proportional to N log N. Jim Saxe of Carnegie-Mellon University reduced that to linear time by observing that the search can avoid carrying too many duplicates. When his search knows that a duplicate must be in a current range of M integers, it will only store M + I integers on its current work tape; if more integers would have gone on the tape, his program merely discards them. Although his method frequently ignores input variables, its strategy is conservative enough to ensure that it finds at least one duplicate. b. We can do a traversal of the tape at most 4 times, first checking to see how many times does each 5-bit binary word appear in the last five bits of each word. At least one of them (call it "edcba") must have at least 1050000/32 > 2^15 appearances (this happens due to Dirichlet's/Pigeonhole Principle) Scan the tape a second time, looking only at the words ending in "edcba". This time, count for how many words does each 5-bit word appears as a "9-through-5" position substring. Obviously, also from Pigeonhole Principle, there must exist one 5-bit word "jihgf" having its counter strictly larger than 2^15 / 32 = 2^10. (Obviously, then, the number of words ending in "jihgfedcba" on the tape is the actual value of this counter.) Scan the tape two more times, looking at the other 5-long groups of bits of each of the "remaining" words, namely bits "14-through-10", and "19-through-15". (Note that we scan the tape completely every time, but we only check fewer words for substrings). 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? Solution: a. o 12 o 12 o 12 / / / 1 o 1 o 1 o S \ \ \ o 11 o 11 o 11 / / / 2 o 2 o 2 o \ \ \ o 10 o 10 o 10 / zig-zag / zig-zag / 3 o ----------> 3 o ---------> 3 o \ \ \ o 9 o 9 o 9 / / / 4 o 4 o 6 X \ \ / \ o 8 o 8 4 o o 8 / / \ / 5 o 6 X 5 o o 7 \ / \ o 7 5 o o 7 / 6 X o 12 o 12 / / 1 o 1 o \ \ o 11 o 11 / 6 / zig-zag 2 o zig-zag ________X______ ---------> \ ---------> / \ o 10 2 o o 10 / \ / 6 X 3 o o 9 ___/ \___ \ / / \ 4 o o 8 3 o o 9 \ / \ / 5 o o 7 4 o o 8 \ / 5 o o 7 o 12 6 / 6 _________X_________ __________X__________ zig-zag / \ zig / \ --------> 1 o o 11 ------> 1 o o 12 \ / \ / 2 o o 10 2 o o 11 \ / \ / 3 o o 9 3 o o 10 \ / \ / 4 o o 8 4 o o 9 \ / \ / 5 o o 7 5 o o 8 / o 7 b. We could prove by induction over n that the height of the splay tree obtained after splaying the deepest element in a zig-zag chain with n nodes, is the lower integer part of n/2. (We start with verifying the assumption for n=1 and n=2, and then knowing that the property holds for n, we prove it for n+2.) 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.) Solution: a. It is easy to see that, in general, when we have a splay tree with keys 1, 2, ..., n, and we perform the following sequence: splay(1), splay(2), ..., splay(n), the tree is transformed into a left chain, while if we perform the following sequence: splay(n), splay(n-1), ..., splay(1), the tree is transformed into a right chain. (In our particular case, we have n=10.) b. The splay operation is not, in general, invertible. To give a counterexample, we consider the case of splay trees with 3 nodes. A general formula for the number of the binary search trees with n nodes, is known 1 /2*n\ to be: ----- | | . In our case, there are 5 binary search trees with n+1 \ n / n nodes. Namely, these trees are: T1: 3 o T2: 2 o T3: o 1 / / \ \ 2 o 1 o o 3 o 2 / \ 1 o o 3 T4: o 3 T5: 1 o / \ 1 o o 3 \ / o 2 2 o We can build a transition matrix M, whose entries have the following significance: { k(<>0) iff splay(k, Ti) = Tj M_i_j = { { 0 otherwise In our case, 1<=k<=3, 1<=i,j<=5, and M looks like: / 3 2 1 0 0 \ | 3 2 1 0 0 | M = | 3 2 1 0 0 | | 0 2 0 3 1 | \ 0 2 0 3 1 / We can observe that we can't get from T1, T2, or T3, by any sequence of splays, to either T4 or T5, while the converse is possible. Therefore, we can conclude that the splay operation isn't invertible.