CS410, Summer 1998
Homework 7 Answers (a bit brief to call a sample solution)
Dan Grossman

1. Several possible answers including:

* Sort each set. Have a finger walk through each set.  On each
  iteration, advance the finer pointing to the smaller element.  If the
  two elements are equal, add the element to the interesection.

* Sort one set.  For each element in the second set, do binary search on
  the sorted set to see if the element is in it.  If so, add to the
  intersection.

* Put one set in a balanced tree.  For each element in the second set, do a
  lookup in the tree.  If it succeeds, add to the intersection.

2. 
  1. (3n/2)log n
     30 million
  2. (n/2) log n
     10 million
  3. Find the length of the original list.  Add a parameter to recursive
     mergesort calls for the length of the smaller list.
     n + (n/2) log n 
     11 million

3. 
   a. Use an O(nlog n) sort (eg. mergesort).  List the i largest in time O(i).
      Total time O(i + nlog n).

   b. Use a heap, using build-heap since all elemnts known in advance,
      i deletions.
      Total time O(n + ilog n).

   c. Use "median of medians" to find ith largest in O(n).
      Partition in O(n).
      Use mergesort to sort i elements in O(ilog i).
      Total time O(n + ilog i).

4. quick-select2(array, i, j, low, high) =
   p = partition(array, low, high);
   if (i < p && j < p)
	quick-select2(array, i, j, low, p-1);
   else if (i > p && j > p)
	quick-select2(array, i, j, p+1, high);
   else {
	if (i == p)
	   print array[p];
	else if (i < p);
	   quick-select(array, i, low, p-1);
	else
	   quick-select(array, i, p+1, high);

	if (j == p)
	   print array[p];
	else if (j < p);
	   quick-select(array, j, low, p-1);
	else
	   quick-select(array, j, p+1, high);
   }

5. 
 1.
   for the w most significant digits in less to more significant order
      stable sort the elements on the digit
   for each group of elements with the same initial w digit
      insertion sort the group

 2. Otherwise we cannot assume that each group has (n/b^w) elements in it.

 3.         w          running time
           ------------------------
	    0	       10^10
	    1          10^7 + 10^9
	    2	       2*10^7 + 10^8
	    3          4*10^7
	    4          4*10^7 + 10^6
            5          5*10^7 + 10^5
     So w == 3 is best.

  4. The formula suggests that even though we did a full radix sort, we have
     to do b^w insertion sorts of 1 element.  We do not have to do these sorts
     so the second term could be eliminated.  This does not change the optimal
     answer for w, however.

6. Something expressing this idea.
  answer(Trie T, int t, key k) {
	i = 0;
	while (i < t && T != null) {
	   if (digit(i,k) == 0)
		T = T.left;
	   else
		T = T.right;
	}
        printAll(T);
   }
   printAll(Trie T) {
	if (T == null)
	  return;
	if (leaf(T))
	   print T;
	else {
	   printAll(T.left);
	   printAll(T.right);
	}
   }

  Remember in a trie that all data is at the leaves and the ith level
  branches on the ith bit.