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

Class (Recitation) Notes: 02-Mar-2007

Logistics:

1. Packages (Section 7.4) moved from Quiz 4 to Quiz 5

2. Required (free, online) Textbook: Javanotes by David Eck

3. Revised Quiz Policy: Minimum of 60 or 5 times your original score.

4. Revised Pair Programming Lite Policy:
The intention is that you and your partner will share the load roughly equally.  So:  by submitting an assignment with a partner, you are implicitly stating that you did in fact work roughly equal amounts.  If this is not the case, you must explicitly and clearly state so, both in your program and in a separate email (sent prior to the submission deadline) to your CA and instructor, clearly indicating what percentage of effort you contributed.  Note that you must do this whether your contribution was more or less than half, so in each such case we should receive two emails (one from each partner).  Further note that your grade will be adjusted accordingly in this case.  If you do not work in roughly equal amounts and you do not inform your CA and instructor of this situation, then you are in violation of academic honesty provisions.

5. Quiz 4 à Thursday

6. Reading:

a. Interfaces: Javanotes Section 5.7.1 on Interfaces and email

b. Mergesort: Wikipedia page on Mergesort

Topics:

1. How to Use ArrayList.toArray
Or: How to Create an Array of an Unknown Number of Strings (hw 6, #8):

a. A Simple Example:
ArrayList list = new ArrayList();
list.add("foo");
list.add("bar");
Object[] array = list.toArray();
out.println(Arrays.toString(array)); // [foo, bar]

b. A Problem Lurks…
ArrayList list = new ArrayList();
list.add("foo");
list.add("bar");
String[] array = list.toArray(); // Will not compile!
out.println(Arrays.toString(array));

c. Why? Java cannot convert Object[] to String[]

i. Cannot Assign Object[] to String[]
Object[] x = { "hi", "there" };
String[] y = x; // ß Compile-time: Incompatible types

ii. Cannot Cast Object[] toString[]
Object[] x = { "hi", "there" };
String[] y = (String[]) x; // ß Runtime: ClassCastException

d. Solution: Parameterized toArray
ArrayList<String> list = new ArrayList<String>();
list.add("foo");
list.add("bar");
String[] array = list.toArray(new String[0]);
out.println(Arrays.toString(array)); // [foo, bar]

e. Aside: Only Works with Parameterized ArrayList
ArrayList list = new ArrayList();
list.add("foo");
list.add("bar");
String[] array = list.toArray(new String[0]); // Will not compile!
out.println(Arrays.toString(array));

f. Refinement: Eliminate Wasteful Call to “new”:
ArrayList<String> list = new ArrayList<String>();
list.add("foo");
list.add("bar");
String[] array = list.toArray(new String[list.size()]);
out.println(Arrays.toString(array)); // [foo, bar]

2. Mergesort

a. Standard (Top-Down) Algorithm:

i. Algorithm:
Sort left half recursively;
Sort right half recursively;
Merge the two halves.

ii. Simulation:
See Stephen Chen’s Recursive Sorting Applets

b. Bottom-Up Variant:

i. Algorithm:
Merge pairs of singletons into ordered pairs
Merge pairs of ordered pairs into ordered 4-tuplets
Merge pairs of ordered 4-tuplets into ordered 8-tuplets
And so on

ii. Trade-offs:
Plus: Easier to visualize and understand.
Minus: Harder to code.

iii. Simulation:
See Stephen Chen’s Recursive Sorting Applets
Or see David Eck’s xSortLab Demo

c. Good properties:

i. Simple, clear, easy to code.

ii. “Fast” sort (n log n)

iii. Stable sort: Equal elements remain in the same order.
Q: How might you test this?
Q: Which, if any, are stable: bubblesort, insertionsort, selectionsort?

iv. Works well with sequential (non-random-access) data, like linked lists (why?).
Q: Which, if any, of bubblesort, insertionsort, or selectionsort also do so?

v. Parallelizable (why?)

d. Bad property:

i. Uses extra memory (the copy array)
Q: How much extra memory do bubblesort, insertionsort, and selectionsort use?

e. Let’s Write It!
Then Let’s Test it!