Midterm: October 13, 2004

1. Write down the size and capacity of the Vector X after each of the following code fragments is executed. Recall that the capacity of the Vector is the length of array elementData, while the the size is the number of elements we have stored in it. Use the space next to the code to write your answers.

   Code fragment (a)
   

   		Vector X;
   		X = new Vector(2);
   
   		for(int i = 0; i < 50; i++)
   			X.add("hello");
   

   Answer: size = 50, capacity = 64.
   Justification: The default behavior of a Vector is to double in size each time it becomes full and has to perform another add.
   You did not have to provide a justification as part of your answers.

   Code fragment (b)
   

   		Vector X;
   		X = new Vector(2, 10);
   
   		for(int i = 0; i < 50; i++)
   			X.add("hello");
   

   Answer: size = 50, capacity = 52.
   Justification: The second argument to the Vector constructor call in the above code is the amount by which a Vector will expand when it becomes full and has to perform another add. Therefore, the Vector will expand from 2 to 12 to 22 to 32 to 42 and finally to 52.

2. Here is code from Bailey's Matrix class for the removeRow and the removeCol functions. Assuming the height and width of the matrix are both n, what is the running time of each of these functions (in Big-Oh notation, as a function of n). Also provide a 1 sentence explanation for each of your answers.

       public Vector removeRow(int r)
       {
           Assert.pre(0 <= r && r < height,"There is a row to be removed.");
           Vector result = (Vector)rows.get(r);
           height--;
           rows.remove(r);
           return result;
       }
   

   Answer: O(n)
   Explanation: Except for the line of code rows.remove(r), the other lines of code take O(1) time each. The code rows.remove(r) takes O(n) in the worst case because removing an element right at the beginning of the Vector rows involves moving the rest of the elements to the left and this takes approximately n steps.

       public Vector removeCol(int c)
       {
           Assert.pre(0 <= c && c < width,"There is a column to be removed.");
           Vector result = new Vector(height);
           width--;
           for (int r = 0; r < height; r++)
           {
               Vector theRow = (Vector)rows.get(r);
               result.add(theRow.get(c));
               theRow.remove(c);
           }
           return result;
       }
   

   Answer: O(n^2)
   Explanation: The body of the for-loop executes n times. The first two lines of code inside the body of the for-loop take O(1) time each while the last line takes O(n) time in the worst case (for the reason mentioned in the previous answer). Therefore the total time is n times O(n) which is O(n^2).

3. In the problem of "Computing Change in Postage Stamps", we assumed that the denominations were 1, 21, and 37. Now let us drop this assumption and write a function called generalStampCount that takes as input (i) an arbitrary set of denominations and (ii) an amount and computes the size of smallest change for amount using the given denominations. The set of denominations is provided in an int array. For example, if the denominations were {1, 21, 37}, then we would have an int array, let us call this denominations, such that denominations[0] = 1, denominations[1] = 21, and denominations[2] = 37. To simplify our task let us assume (i) that all denominations are positive integers and (ii) one of the denominations is 1, thereby ensuring that we will always be able to make change for any given amount. Here is most of the code for generalStampCount. This is just a modification of the code given in the textbook (page 88). 2-3 lines of code are missing in the if-statement; the first of these is the recursive call. Supply these lines of code.

   protected static int generalStampCount(int amount, int[] answer, int[] denominations)
   {
           int minStamps = Integer.MAX_VALUE;
           int possible;
           Assert.pre(amount >= 0, "Reasonable amount of change.");
                                                                                                                          
           if(amount == 0) return 0;
           if(answer[amount] != 0) return answer[amount];
           int k = denominations.length;
           for(int i = 0; i < k; i++)
           {
                   if(denominations[i] <= amount)
                   {
   			//Here is the missing code.
   
   			possible = generalStampCount(amount-denominations[i], answer, denominations);
   			if (possible < minStamps)
   				minStamps = possible;
                   }
           }
                                                                                                                          
           answer[amount] = minStamps;
           return minStamps;
   }
   
   

4. Consider the following recursive function, called recursiveFoo. Assume that the running time of the function call mystery(n) is O(n).
   1. recursiveFoo is very similar in overall structure to a recursive function that we have studied and analyzed in class. What is that function?

      Answer: recursiveMergeSort

   2. What is the running time of recursiveFoo as a function of n?

      Answer: O(n log(n))

      		void recursiveFoo(int  n)
      		{
      			if(n == 1)
      				System.out.Println("Done!);
      			else
      			{
      				recursiveFoo(n/2);
      				recursiveFoo(n/2);
      				mystery(n);
      			}
      		}