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

  1. (Recursion) Consider the program below, in Java and C: 
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--;
   }
}

#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--;
   }
}

    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.

  1. 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.)

  2. 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};