15-110 Sections M-Q / Fall 2009 / Midterm Exam #2
3 Parts / 75 Minutes

Note:  Unicode 'A' is 65, 'a' is 97, and '0' is 48.

Part I:  Short Answers  (3 pts each)
 

1.      Which quadratic (slow) sort may swap elements that are not adjacent (right next to each other)?
 

2.      Sort the array { 4, 2, 3, 1 } by mergesort.  Just list the array after each entire pass.
 

3.      Sort the array { 4, 2, 3, 1 } by insertionsort.  Just list the array after each entire pass.
 

4.      Write one line of code that draws a line from the left-top to right-bottom corners of the rectangle drawn by page.drawRect(a,b,c,d).  Assume “page” is initialized for you.
 

5.      In just a few words, state what effect the value 128 has in the call: page.setColor(new Color(255,0,0,128)).
 

6.      The following code compiles and runs, but throws an exception.  In just a few words, why?
   class Foo {
     private static Polygon[] a;
     public static void main(String[] args) {
       a[0] = new Polygon();
       System.out.println(a);
     }
   }
 

7.      The following code compiles and runs, but throws an exception.  In just a few words, why?
   class Foo {
     private static int[][] b = new int[10][20];
     public static void main(String[] args) {
       System.out.println(b[10][20]);
     }
   }
 

8.      Very briefly explain why selection sort is O(N^2).  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.

9.      Write a method that swaps two values in a two-dimensional array of doubles.
 

10.  Say selectionsort requires about 1/2 minute to sort a given list of random numbers on a specific computer.  Using the same computer, about how long would we expect selectionsort to take on a list 6 times as long?
 

11.  What will this code print?

    int[] a = { 4, 2, 6, 1, 5 };
    int j = 0;
    for (int i=a.length-1; i>=0; i-=2) {
      a[j] += a[i];
      j++;
      System.out.println(Arrays.toString(a));
    }

12.  What will this code print?
 

    int z = 121;
    String s = "z" + z;
    while (z > s.length()) {
      z /= s.length();
      s += z;
      System.out.println(z + "," + s);
    }

Part II:  Write the following methods  (10 pts each)
 

13.  Write a method that uses a version of binary search to find the square root of 7 to within 0.00001.  Your method may not call Math.pow or Math.sqrt.
Hint  we know that 2 is too low, because 2*2 == 4 and 4 < 7.
And…  3 is too high, because 3*3 == 9, and 9 > 7.

 

14.  Write a well-named method that takes an array of integers and returns true if the array is sorted in either  increasing or decreasing order.  So your method would return true for {1,2,3} and also for {3,2,1}, but would return false for {1,3,2}.  Return true for an empty array and false for a null array.

 

15.  Write a well-named method that takes a 2d array of integers and a 1d array of integers, and returns true if the second array occurs as a column (from top to bottom) in the first array.  For example, if the first array is:
   {  { 2, 4, 5, 6 },
      { 3, 8, 1, 9 }
   };
Then if the second array is {5,1}, your method would return true.  However, your method would return false if the second array was {2,8} or even {1,5} (wrong order).  Your method should return false if either array is null.

 

Part III:  Writing Classes.  (34 pts)

16.  On the next page, write the Car class so that the testCarClass method given here passes all its tests.  Do not worry about any test cases besides those given here.
 

public static void testCarClass() {
  System.out.println("Testing Car class... ");

  Car audi = new Car("Audi",20.0); // 20.0 miles-per-gallon (mpg)
  // toString indicates the car name, the mpg, and fuel in the tank
  assert(audi.toString().equals("Audi(20.0mpg,0.0gallons)"));
  assert(almostEqual(audi.getMpg(), 20.0)); // use "almostEqual" for doubles
  assert(almostEqual(audi.getFuel(), 0.0));
  assert(audi.tankIsEmpty() == true);

  // The drive method takes the distance in miles to drive, and consumes
  // as much fuel as required, if available.  It returns the distance
  // driven, which may be less than the requested amount if there is not
  // enough fuel.
   
  // now, we are out of gas, so our request to drive 10.0 miles results
  // in driving 0.0 miles
  assert(almostEqual(audi.drive(10.0), 0.0));
  assert(almostEqual(audi.getFuel(), 0.0)); // and we still have no gas!

  // add 5.0 gallons of fuel so we can drive 100.0 miles
  audi.addFuel(5.0);
  assert(audi.tankIsEmpty() == false);
  assert(almostEqual(audi.getFuel(), 5.0));
  assert(audi.toString().equals("Audi(20.0mpg,5.0gallons)"));

  // now, our request to drive 10.0 miles results in driving all 10.0
  // miles, and consumes 0.5 gallons of gas:
  assert(almostEqual(audi.drive(10.0), 10.0));
  assert(almostEqual(audi.getFuel(), 4.5));
  assert(audi.toString().equals("Audi(20.0mpg,4.5gallons)"));
   
  // if we try to drive 100.0 miles now, we'll only make it 90.0 miles on
  // the 4.5 gallons remaining
  assert(almostEqual(audi.drive(100.0), 90.0));
  assert(audi.tankIsEmpty() == true);
   
  // Construct a second car with the default mileage of 15 miles-per-gallon
  Car ford = new Car("Ford");
  assert(ford.toString().equals("Ford(15.0mpg,0.0gallons)"));
  assert(almostEqual(ford.getMpg(), 15.0));

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

Bonus/Optional

Answer the following:

a)  Why is the enhanced for loop especially useful when working with HashSets?

b)  Prove that mergesort is O(nlogn).

c)  Our array list implementation started with capacity 1, and doubled the capacity as needed.  With this approach, what is the total number of elements allocated to add N values to the array list?  If it helps, you may assume that N is a power of 2 (that is, N = 2^k for some integer k>0).
 

d)  What is the minimum amount of time (in big-O notation) required to sort an array of N boolean values?
 

e)  How does the preceding result not contradict the result we stated in class that O(nlogn) is optimal for comparison-based sorts over arbitrary domains?