15-110 Sections M-Q / Fall 2009 / Quiz 8

6 Questions / 30 Minutes

 

·         Unicode ‘A’ is 65, ‘a’ is 97, and ‘0’ is 48.

·         Keep “very briefly” answers to <15 words if at all possible.  Sentences not required.

·         Note:  The Tetris question (worth 30 points) will be covered Friday in recitation, using a compiler.

1.  [5pts]  Very briefly explain why selection sort is O(N²).  While you do not have to be very precise, you do  have to provide the most important parts of the math that we used to reach this conclusion.
    
2. [6pts]  Answer the following:
   1. About how many comparisons must binary search make to conclude that a given key is not in a list with roughly 32 thousand elements?
       
   2. Say bubble sort requires about 5 seconds to sort a given list of random numbers on a specific computer.  Using the same computer, about how long would we expect bubble sort to take on a list 4 times as long?
       
   3. True or False:   The “logN” part of the O(NlogN) nature of merge sort derives from the fact that a number N can only be divided by 2 a total of log₂N times.
       
3. [6pts]  Fill in the two blanks with the missing code fragments:
   
     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 _______________;
       }
       return -1;
     }
    
4. [10pts]  The inner loop of selection sort must find the index of the smallest remaining element from the outer loop’s index i to the end of the array.  Write a helper method that does exactly this (and no more – it does not do all of selection sort!).  Choose your method header (return type, name, parameters) wisely.

5. [35pts]  On the preceding page, write the Range class, which represents a range of integers, so that the following code passes all its tests.  Do not worry about any test cases besides those given here.
   
   All questions regarding Range behavior are answered by the test cases below!
    

  public static void testRangeClass() {

    System.out.print("Testing class Range...  ");

    Range r1 = new Range(5,8);

    assert(r1.toString().equals("Range(lo=5,hi=8)"));

    assert(r1.getLo() == 5);

    assert(r1.getHi() == 8);

    r1.setHi(13);

    assert(r1.toString().equals("Range(lo=5,hi=13)"));

    assert(r1.getLo() == 5);

    assert(r1.getHi() == 13);

    Range r2 = new Range();

    assert(r2.toString().equals("Range(lo=1,hi=10)")); // default range

    assert(r2.getLo() == 1);

    assert(r2.getHi() == 10);

    r2.expandToInclude(r1);  // void method (destructive)!

    assert(r1.toString().equals("Range(lo=5,hi=13)")); // unchanged

    assert(r2.toString().equals("Range(lo=1,hi=13)")); // expanded to include r1

    assert(r2.getLo() == 1);

    assert(r2.getHi() == 13);

    Range r3 = new Range(1,13);  // same range as r2

    assert(r1.equals(r3) == false);

    assert(r2.equals(r3) == true);

    System.out.println("Passed all tests!");    

  }