1. Propose an algorithm to sort a large ?le using only two tapes.

2. a. Show that a lower bound of N!/22N on the number of heaps is implied by the fact that buildHeap uses at most 2N comparisons.

b. Use Stirling's formula to expand this bound.

3. M is an N-by-N matrix in which the entries in each rows are in increasing order and the entries in each column are in increasing order (reading top to bottom). Consider the problem of determining if x is inM using three-way comparisons (i.e., one comparison of x with M[i][j] tells you either that x is less than, equal to, or greater than M[i][j]).

a. Give an algorithm that uses at most 2N - 1 comparisons.

b. Prove that any algorithm must use at least 2N - 1 comparisons.