COS 226 Homework #2
Due: Friday, February 18, 2005

Written Exercises

Follow the instructions on the assignments page on how and when to turn these in.  Numbers in brackets indicate the approximate number of points each problem is worth.  For the last two problems, note that although the Sedgewick text does not cover loop invariants or the sorting lower bound, these topics are covered in Sections 2.1 and 8.1 of the optional Cormen, Leiserson, Rivest & Stein text.

  1. [4] Show how the file 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 is partitioned using the partitioning algorithm given in class and provided below (with l set to the left end point of this file, and r set to the right end point).  Then show how the same file is partitioned if we replace the condition (i <= j) by (i < j) in both places where it appears in this algorithm.  Give the contents of the file and the values of i and j after partitioning is complete, in both cases.
     
  2. [6] How many operations does quicksort take if the input is an array of N copies of the letter A?  Use the version of quicksort presented in class (Program 7.1 in the book).
     
  3. [4] The largest element in a heap must appear in position 1, and the second largest element must be in position 2 or position 3. Give the list of all positions in a heap of size 15 where the k-th largest element can appear, for k = 3, 4, 5.  Assume all elements are distinct.
     
  4. [4] Give the sequence of heaps produced when the operations P R I O * R * * I * T * Y * * * Q U E * * * U * E are performed on an initially empty heap (where a letter means "insert" and an * means "delete maximum").
     
  5. [4] Is 2n+1 = O(2n)?  Is 22n = O(2n)?  Why or why not?
     
  6. [8] Consider the following recurrence: T(1) = 2, T(N) = T(N/2) + N if N >= 2.  Prove by mathematical induction that T(N) = 2N for all N which are powers of 2.  (That is, assume that N has the form 2k, and use induction on k.)
     
  7. [10] Give an O(N lg k)-time algorithm to merge k sorted lists into one sorted list, where N is the total number of elements in all the input lists.  Be sure to explain why your algorithm does what it is supposed to, and why it does so within the stated time bound.
     
  8. [10] Describe an O(N lg N)-time algorithm that, given a set S of N integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.  Be sure to explain why your algorithm does what it is supposed to, and why it does so within the stated time bound.
     
  9. [10] Consider the code for partitioning a segment of an array that was given in class, and provided again below.  This code returns a value m, and permutes the keys a[l],...,a[r] so that a[r] has been moved to position m, all entries smaller than a[r] have been moved to the left of position m, and all entries greater than or equal to a[r] have been moved to the right of position m.  In what follows, be sure to give careful arguments that are clear, precise and convincing.
    1. State loop invariants for the outer loop.
    2. Show that your loop invariant holds at the beginning of the first iteration.
    3. Show that if your loop invariant holds at the beginning of any iteration, then it must also hold at the beginning of the next iteration.
    4. Use the fact that your loop invariant holds on every iteration to show that the algorithm properly partitions the data.
       
  10. [10] Consider a computer program that plays a modified form of "20 questions" with a human user (let's call her Alice).  Before the game begins, Alice thinks of a number between 1 and N (where N is known ahead of time to both Alice and the computer).  The computer then proceeds to ask Alice yes-no questions about her number.  For instance, the computer might ask: "Is the number odd?" or "Is the number bigger than 15?" or "Is the number prime?"  Alice is not allowed to change her mind about which number she is thinking of, and must give honest answers to each question.  After asking Alice some number of yes-no questions, the computer must correctly print the number that Alice was thinking of.  Assume that the computer always prints the correct number at the end of the game.

    Prove carefully that for any such computer program, Alice can choose her number appropriately to force the computer to make at least lg N questions.  You can use a decision-tree argument similar to the lower bound proof for comparison-based sorting.
     

 

partition(a[], l, r)

i = l;
j = r - 1;
v = a[r];

while (i <= j) {

   while (i < r && a[i] < v)
      i++;

   while (j >= l && a[j] >= v)
      j--;

   if (i <= j) {
      t = a[i]; a[i] = a[j]; a[j] = t;
      i++;
      j--;
   }

}

m = i;
t = a[i]; a[i] = a[r]; a[r] = t;
return m;