Computer Science 15-111 (Sections A & B), Spring 2007

Quiz 2 Practice

This is optional. It will not be submitted and it will not be graded.

This practice sheet is meant to help you prepare for Quiz 2. While it is representative of the kinds of problems you can generally expect, it may not be comprehensive – the quiz may include questions related to any topic we have covered in class, in readings, or in homework, and include any types of questions.

I will review the answers tonight from 5-6pm in Wean 5419-D (before reviewing the hw3 solution set from 6-7pm). Attendance at either session is optional.

==============================

The following problems are to be solved without use of a calculator or a computer. Work them by hand. (This is what you will need to do on upcoming quizzes and tests!).

1. In a few words of plain English, what does the following method compute:
public static int foo(int x) {
if (x == 0) return 0;
else return (x & 1) + foo(x >>> 1);
}
Hint: the answer has something to do with the bits in the Two’s Complement representation of x.

2. In a few words of plain English, what does the following method compute:
public static int foo(int x, int y) {
if (y < 1) return 1;
else return x*foo(x,y-1);
}
Does it work when x==0 ? x<0 ? y==0 ? y<0 ?

3. In a few words of plain English, what does the following method compute:
public static int foo(int x, int y) {
if (y < 2) return 0;
else return 1+foo(x,y/x);
}
Does it work when x==0 ? x<0 ? y==0 ? y<0 ?

4. What will the following code print out?
public static int foo(int[] x, int y) {
if (y < 1) return x[0];
else return Math.max(x[y],foo(x,y-1));
}
public static double foo(int[] x) { return foo(x,x.length-1); }
public static void main(String[] args) {
int[] x = { 5, 2, 3, 7, 4, 1, 6 };
System.out.println(foo(x));
}

5. Consider the following method:
public static int foo(int x) {
if (x < 0) return foo(-x);
else if (x < 2) return x;
else return (foo(x-1) + foo(x-2) + 6*x - 5)/2;
}
This method computes x². Prove this fact by computing (x-1) ² and (x-2) ², summing these, and solving the resulting expression for x².

6. Write the following method:
public static char[][] makeBoard(ArrayList<String> list)
This method converts an ArrayList<String> to a 2d array of char’s. Here, you may not assume that the strings are all the same length – instead, your 2d array must have as many cols as the widest strings, with the other rows filled in on the right (the higher col’s) with the char ‘X’ as needed.

7. Consider the following code:
public static String foo() {
String x = "";
for (int i=0; i<10000; i++)
x += "foo";
return x;
}
public static String bar() {
StringBuilder x = new StringBuilder();
for (int i=0; i<10000; i++)
x.append("foo");
return x.toString();
}
These methods compute the same results (A string of 10,000 foo’s: “foofoofoo…”), but one of them is substantially slower than the other (run them yourself to see – one takes about 2400 ms on my machine, the other takes less than 1 ms). Which one is slower, and precisely why so?

Aside: if you want to run them yourself along with timing info, here’s how:
public static void main(String[] args) {
long time0 = System.currentTimeMillis();
String s1 = foo();
long time1 = System.currentTimeMillis();
String s2 = bar();
long time2 = System.currentTimeMillis();
System.out.println(s1.equals(s2));
System.out.printf("foo() took %d ms\n",time1 - time0);
System.out.printf("bar() took %d ms\n",time2 - time1);
}

8. When reading input lines as strings, state two advantages of using an ArrayList<String> versus an ArrayList<Object>.

9. What will the following code display?
int[][] pixels = loadPixels("sampleImage.jpg");
int width = pixels.length, height = pixels[0].length;
for (int x=0; x<width; x++)
for (int y=0; y<height; y++)
if (x > y) pixels[x][y] |= (0xFF << 8);
displayPixels(pixels);
Hint: a |= b is the same as a = a | b

10. Can we add an ArrayList<String> to an ArrayList<Object>? Vice versa?

11. Explain the general case where the following evaluates to true for Strings s1 and s2:
((s1.equals(s2)) && (s1 != s2))

12. Consider the following method:
public static Object[] removeElement(Object[] source, int index)
This method returns an array of size 1 less than the source array (which is unmodified), where the element source[index] is removed from the result. You may ignore the case when index is out of bounds.

Write this method in each of the following ways:

a. Using a traditional for loop

b. Using two calls to arraycopy (one for the low part, one for the high part)

13. The following code prints out true then false. Explain.
Integer[] a = new Integer[2];
a[0] = a[1] = 12345;
System.out.println(a[0] == a[1]);
a[0] = 12345;
System.out.println(a[0] == a[1]);