Computer Science
15-111 (Sections A & B), Spring 2007
Homework #6
Due: Wed
7-Mar-2007 at 10:30am (in-class and online submission).
Submit a
printed copy of your assignment as you enter class. Also, for your online submission (which must
be the same as your printed submission), place your programs in hw6.zip. Include the written work in a file hw6.doc (not hw6.txt) in the top level of the zip
file. Remember to just submit your .java
files, and not your .class files, random .jpg files, or miscellaneous Eclipse
or other IDE-related files.
- Do the following questions from “Java by Dissection”:
Ch 7 Review Questions, #1-8 and 10-13.
- Do the following question from “Java by Dissection”:
Ch 7 Exercises, #17
- Create a class,
DuplicatingArrayList, which extends ArrayList and which overrides one
method, add(Object). It should
operate by calling the superclass’s add method twice, giving this
behavior:
DuplicatingArrayList list = new
DuplicatingArrayList();
list.add("foo");
list.add(5);
out.println(list); // prints [foo, foo, 5, 5]
out.println(list.size()); // prints 4
Remember to turn
off the compiler’s warnings about unchecked operations by placing the
following before each class as necessary:
@SuppressWarnings(value={"unchecked"})
- In just a few words, explain
why it is unlikely that you would have a single class implement both the
Comparable and Comparator interfaces – what it is about the semantics of
these two interfaces that would make it peculiar to implement both in one
class? (You may wish to answer this
after completing the rest of this problem.)
Regardless of it probably being a bad idea, you still can have a single class implement
both the Comparable and Comparator interfaces. Do this as follows: Create a class Dog with two fields, a
String name and an Integer id (issued by the county, presumably). Dog should implement Comparable so that
an array of Dogs is sorted by the dogs’ names. But Dog should aso implement Comparator
so that if this Comparator is used, then the array of Dogs is sorted by
the dogs’ ids. Also, override
toString and include the appropriate constructor so that when you run the
following code:
Dog[] dogs = { new
Dog("skip",56),
new
Dog("fido",34),
new
Dog("lucy",12) };
out.println(Arrays.toString(dogs));
Arrays.sort(dogs);
out.println(Arrays.toString(dogs));
Arrays.sort(dogs,dogs[0]);
out.println(Arrays.toString(dogs));
You get the following output (exactly):
[skip-56, fido-34, lucy-12]
[fido-34, lucy-12, skip-56]
[lucy-12, fido-34, skip-56]
- Copy
your Dog class into a SmartDog class, which is the same except that it
does not implement the Comparator interface. Instead, create a Comparator called
dogIdSorter that uses an anonymous inner class as we did with Comparators in
class to achieve the same effect as the previous example. That is, the following code:
SmartDog[] dogs = { new SmartDog("skip",56),
new SmartDog("fido",34),
new SmartDog("lucy",12) };
out.println(Arrays.toString(dogs));
Arrays.sort(dogs);
out.println(Arrays.toString(dogs));
Comparator dogIdSorter = ... (you
fill this in!);
Arrays.sort(dogs,dogIdSorter);
out.println(Arrays.toString(dogs));
Should work just as in the previous problem, only now it is much clearer.
- Briefly describe how the 4-line
sort (over Comparables) in the class notes works, and why it is a bit less
efficient than insertionsort. Next,
create a final, non-instantiable (ie, private constructor) class,
Hw7Utils, which only contains public static methods (like the Math
class). In this class, define this
method:
public static void FourLineSort(Object[] a, Comparator c)
This method is just like the 4-line sort, only it takes a Comparator
rather than assuming the elements of the array are themselves
Comparables. Show that this code
works by testing it with the dogIdSorter from above and verifying the
results are as expected.
- Add the following method to
Hw7Utils:
public static int binarySearch(Object[] a, Object
key)
This method should work exactly according to the description of the method
of the same signature in the Arrays class, as described in the online API:
Searches the specified array for the specified object using the
binary search algorithm. The array must be sorted into ascending order
according to the natural ordering of its elements (as by Sort(Object[]), above) prior to
making this call. If it is not sorted, the results are undefined. (If the
array contains elements that are not mutually comparable (for
example,strings and integers), it cannot be sorted according to the
natural order of its elements, hence results are undefined.) If the array
contains multiple elements equal to the specified object, there is no
guarantee which one will be found.
Parameters:
a - the array to be
searched.
key - the value to be
searched for.
Returns:
index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion
point is defined as the point at which the key would be inserted into
the list: the index of the first element greater than the key, or list.size(), if all elements in the
list are less than the specified key. Note that this guarantees that the
return value will be >= 0 if and only if the key is found.
To implement the binary search algorithm, maintain a “lo” and a “hi” index
range – initially set to 0 and a.length-1, respectively – and on each
iteration try the “mid” index, where “mid” is the average of “lo” and
“hi”. If the value is found at a[mid],
return mid. Otherwise, set “lo” to
(mid+1) or “hi” to (mid-1) as called for (think about this). Note that we don’t set lo or hi to mid,
as we know that mid cannot be the final location (we just checked that, right?). This process continues until either we
find the item or until lo crosses hi, which indicates that the item is not
in the list. In this case,
carefully follow the prescribed logic to determine the return value.
- Add the following 4 methods to
Hw7Utils:
public static String[] instrumentedBubblesort(int[] x)
public static String[] instrumentedImprovedBubblesort(int[] x)
public static String[] instrumentedSelectionsort(int[] x)
public static String[]
instrumentedInsertionsort(int[] x)
Each of these methods should perform the specified sort, but should also
return an array of Strings describing each comparison and swap as
described in lecture. For example,
the following:
int[] x = { 4, 2, 1, 3 };
String[] ops =
Hw7Utils.instrumentedInsertionsort(x);
out.println(Arrays.toString(x));
out.println(Arrays.toString(ops));
Would produce the following output (exactly):
[1, 2, 3, 4]
[0c1, 0s1, 1c2, 1s2, 0c1, 0s1,
2c3, 2s3, 1c2]
Here, for example, 0c1 means “compare a[0] to a[1]” and 2s3 means “swap
a[2] and a[3]”. At the least,
verify that each of your methods match the class notes on the array { 4,
2, 1, 3}.
- Add 4 more methods to Hw7Utils:
public static int timedBubblesort(int[] x)
public static int timedImprovedBubblesort(int[]
x)
public static int timedSelectionsort(int[]
x)
public static int timedInsertionsort(int[]
x)
These not only sort the array using the given algorithm, but they also
return the time, in milliseconds, it takes to do the sorting. To do this, as you first enter each
method, include the line:
long time0 = System.currentTimeMillis();
This number is not very meaningful, really, except as a starting time. We don’t care what
it is, per se, as we’ll subtract it from the ending time to
find the running time. The last
thing to do in each method is call:
long time1 =
System.currentTimeMillis();
Now, you have:
int runningTime = (int)(time1 –
time0);
Test the runtimes of each of these methods by creating an array full of
random numbers that is large enough so that the runtimes of each of these
sorts are at least 10 seconds, then have each of these methods sort the
same array (be sure to copy the
array before each sorting, as the sorting itself modifies the array, and
be sure not to count the time creating and copying the arrays as spent
actually sorting them!). In your
written work portion, and also in the header above the Hw7Utils class,
include a table listing each method and its associated runtime on this
large random array (and include the size of the array). What conclusions can you draw from this?
- Though mergesort is much faster than the quadratic
sorts, there is a common error that can render it much slower than it
should be. The error: allocating the copy array on every
recursive call rather than allocating it once and reusing it on every
call. To see how damaging this is,
you will implement both approaches by adding the following 2 methods to
Hw7Utils:
public static int timedMergesortWithError(int[]
x)
public static int
timedMergesort(int[] x)
The first method
contains the over-allocating error, the second does not. Time these methods on variously-sized
arrays of random numbers. Comment (as
precisely as you can) on how severe the effect of the error is. Also, run timedMergesort (the good one)
on the same array you used in the previous problem Reflect on the efficiency of mergesort
versus the previous sorts.
- Bonus [3 pts]: Add the
following method to Hw7Utils:
public static String
findSharedSuperClass(Object obj1, Object obj2)
This method takes two objects and returns the name of the first class in
the class hierarchy of which both objects are an instance. As we did in class, you will need to use
both the getClass() method of Object, and the getName() and
getSuperclass() methods of the Class class. For example, the call:
Hw7Utils.findSharedSuperClass(new
Integer(1),new Double(1))
would return: "java.lang.Number"