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?
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.] [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.