1. An array A[1_n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0_n] to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time. Show that if we use only this operation, we can still determine the missing integer in O(n) time.

2. Draw the recursion tree for the MERGE-SORT on an array of 16 elements. Explain why memoizationis ineffective in speeding up a good divide-and conquer algorithm such as MERGE-SORT. <Solution>

3. Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations on his route. The professor wishes to make as few gas stops as possible along the
way. Give an efficient method by which Professor Midas can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution. <Solution>