CS3343, Spring 2012, Quiz 2, 9 Feb 2012, Answers              Your Name:                                      

  1. (6) (Recursion) Consider the program below, in Java and C:
    1. What will be printed if f is invoked with f(N)? (Just describe the output.)

    2. Write a recursive version of f that has the same output. Your function should not use a loop. (Don't copy or change the bottles function.)

    3. Write a second recursive version of this function, that that prints the same lines as the others, but in backwards order.

    public class Bottles2 {
   final int N = 15;
   void bottles(int n) {
      if (n < 10) System.out.print(" " + n +
         " bottle");
      else System.out.print(n + " bottle");
      if (n != 1) System.out.print("s");
      System.out.println(" of beer on the wall.");
   }
   void f(int n) {
      while (n > 0) {
         bottles(n);
         n--;
      }
   }
   void f0(int n) { // 15 down to 1
      if (n > 0) {
         bottles(n);
         f0(n - 1);
      }
   }
   void f1(int n) { // 1 up to 15
      if (n > 0) {
         f1(n - 1);
         bottles(n);
      }
   }
   void bottlestest() {
      f(N); System.out.println("Set 'em up!");
      f0(N); System.out.println("Set 'em up!");
      f1(N);
   }
   public static void main(String[] args) {
      Bottles2 b = new Bottles2();
      b.bottlestest();
   }
}

    #include 

#define N 15

void bottles(int n) {
   printf("%2i bottle", n);
   if (n != 1) printf("s");
   printf(" of beer on the wall.\n");
}
void f(int n) {
   while (n > 0) {
      bottles(n);
      n--;
   }
}
void f0(int n) { // 15 down to 1
   if (n != 0) {
      bottles(n);
      f0(n-1);
   }
}
void f1(int n) { // 1 up to 15
   if (n != 0) {
      f1(n-1);
      bottles(n);
   }
}
int main() {
   f(N); printf("Set 'em up!\n");
   f0(N); printf("Set 'em up!\n");
   f1(N);
}

  1. (3) Suppose you have a double r, 0 < r < 1, uniformly distributed on the interval from 0 to 1. Given an integer n, show how to produce an integer x satisfying 1 <= x <= n which is uniformly distrubuted on the integers from 1 to n inclusive. (Each of these n integers should be equally likely.) The range from 1 to n inclusive is n integers long. If r is a uniform random double between 0 and 1, then floor(n*r) is a uniformly distributed integer between 0 and n-1 inclusive. Then floor(n*r) + 1 is the answer, a uniformly distributed integer between 1 and n inclusive.
    floor(n*r + 1) also works, as well as ceil(n*r), which was the answer of Rossiter and of Tomsett.

  2. (6) Here is your text's partition algorithm, in C/Java (left) and text's pseudocode (right): 
    int partition(int[] A, int p, int r) {
   int x = A[r];
   int i = p - 1;
   for (int j = p; j < r; j++) {
      if (A[j] <= x) {
         i++;
         exchange(A,i, j);
      }
   }
   exchange(A, i+1, r);
   return i + 1;
}
    Partition(A, p, r)

    x = A[r]  // pivot
i = p - 1  // nothing small so far
for j = p to r - 1  // handle each elt
   if A[j] <= x  // one for small side
      i = i + 1  // find place for it
      exchange(A[i], A[j]) //put it in
exchange(A[i+1], A[r]) // move pivot
return i + 1  // return pivot location

    Trace step-by-step (using each iteration of the for loop) how partition acts on the array A = {8, 2, 7, 9, 4, 3, 6}; 
    
                 | p                       r
                 | 0   1   2   3   4   5   6    |
-----------------|------------------------------|-------------------------
before loop start| 8   2   7   9   4   3  |6    | j=, i: -1
               i |                              |
                 |                              |
end of 0th iter  | 8   2   7   9   4   3  |6    | j=0,i=-1 x=6 (pivot)
               i | j                            |
                 |                              |
end of 1st iter  | 2 | 8   7   9   4   3  |6    | j=1,i=0, exchange(i,j)
                 | i   j                        |
                 |                              |
end of 2nd iter  | 2 | 8 | 7   9   4   3  |6    | j=2,i=0
                 | i       j                    |
                 |                              |
end of 3rd iter  | 2 | 8   7 | 9   4   3  |6    | j=3,i=0
                 | i           j                |
                 |                              |
end of 4th iter  | 2   4 | 7   9 | 8   3  |6    | j=4,i=1, exchange(i,j)
                 |     i           j            |
                 |                              |
end of 5th iter  | 2   4   3 | 9   8 | 7  |6    | j=5,i=2, exchange(i,j)
                 |         i           j        |
                 |                              |
final exchange   | 2   4   3 | 6 | 8   7   9    | j=, i=2, exchange(i+1,r)
                 |         i                    |

return i+1 = 3 = pivot location