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.
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).
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; }
Answer: recursiveMergeSort
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); } }