15-100 Sections S-V / Fall 2008
Quiz 5 / 4 Questions / 25 Minutes
Quiz Date:  Tue 21-Oct-2008

1.      Label each of the following sorts from the “before” and “after” snapshots taken at some point and then one pass later.  Label them “I” for insertionsort, “S” for selectionsort, “B” for bubblesort, or “M” for mergesort  Some responses may occur more than once, others perhaps not at all.  You may recall that black rectangles are in their final sorted position.

2.      Write selectionsort so it works over an array of Strings.  You may assume swap is already written.
Hint:  recall that you should use a String’s compareTo method in place of <, ==, and >.
 

3.      In general, and in just a few words of plain English, what does each of the following methods do?

a.    public static boolean g(int[][] a) {
  if ((a == null) || (a.length != a[0].length))
    return false;
  for (int i=0; i<a.length; i++) {
    int x = 0;
    for (int j=0; j<a[0].length; j++)
      if (a[i][j] != 0)
        x++;
    if (x == 0)
      return true;
  }
  return false;
}
 

b.    public static int[][] f(int n) {
  if (n < 1) return null;
  int[][] a = new int[n][n];
  for (int i=0; i<n; i++)
    a[i][i] = 1;
  return a;
}
 

4.      Fill in the blanks with the missing code fragments in each of the following methods:

a.     public static int binarySearch(int[] a, int key) {
    int lo = 0;
    int hi = a.length-1;

    while (___________________________________________________) {
      int i = (lo + hi)/2;
      if (a[i] < key)
        lo = i + 1;
      else if (a[i] > key)
        hi = i - 1;
      else
        return i;
    }
    return -1;
  }

 

b.   private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
  int n = a.length;
  if (mid >= n) return;
  if (hi > n) hi = n;
  int i = lo, j = mid;

  for (________________________________________________________) {
    if      (i == mid)    { aux[k] = a[j]; j++; }
    else if (j == hi)     { aux[k] = a[i]; i++; }
    else if (a[j] < a[i]) { aux[k] = a[j]; j++; }
    else                  { aux[k] = a[i]; i++; }
  }
  for (int k = lo; k < hi; k++)
    a[k] = aux[k];
}

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem