Problem 4. (10 marks) Suppose you are given a set of small boxes, numbered 1 to n, identical in every aspect except that each of the first i contains a pearl whereas the remaining n i are empty. In the first part of this question, you are given two magic wands that can each test if a box is empty or not in a single touch, except that a wand disappears if you test it on a box that is empty. Show that, without knowing the value of i, you can use the two wands to determine all the boxes containing pearls using no more than O( n) wand touches.

a. We here sketch a solution for this part of the question. We will fix number k later. The idea is first use one wand on boxes 1, k, 2k, 3k, . . . . The smallest i for which the wand burns on box ik indicates that the first empty box is among (i 1)k + 1, . . . , ik. Now we use the second wand sequentially from (i 1)k + 1 to ik 1 to find it. The total number of 1 touches will be at most: n/k + k, where n/k is the number of boxes for the first wand and k for the second. Now, you are asked to complete this solution by describing how you choose the value of k and explaining why your choice leads to an algorithm that has the desired efficiency (i.e., to determine all the boxes containing pearls using no more than O( n) wand touches).

b. Now suppose you are given three magic wands. How would you extend the above algorithm to obtain an even more efficient one? Describe your algorithm, give an upper bound in running time (in terms of the number of wand touches) using the big-O notation, and provide a brief analysis.

c. We should all be familiar with binary search: Given a sorted list of items, it works by repeatedly dividing in half the portion of the list that could contain the item, until youve narrowed down the possible locations to just one. In this question, the given list of boxes can be considered sorted: non-empty boxes proceed empty boxes. Give an algorithm to find the first empty box in O(log n) time independent of how many magic wards may be used. Then, answer the following questions: by your algorithm, in the worst-case how many magic wards are required (express your answer using the big-O notation)? What about the best-case? Justify your answers briefly.