[Instructions] [Search] [Current] [Syllabus] [Links] [Handouts] [Outlines] [Labs] [More Labs] [Assignments] [Quizzes] [Exams] [Examples] [Book] [Tutorial] [API]
Our old pals, Carl and Carla Caffeinated, have decided to branch out. Now, not only do they craft code, they also analyze algorithms. They've come up with the following equations for the running time of an algorithm, where f is ``the number of steps the algorithm takes''.
They've lost the original algorithm, so you'll have to take their word that they've come up with the correct equations.
Carl observes that this pair looks a lot like the equations we had for binary search:
He therefore concludes that the algorithm takes O(log2n) steps.
Carla says that this pair looks a lot like the equations we had for merge sort:
She therefore concludes that the algorithm takes O(nlog2n).
Is either of them right? Precisely determine the behavior of f1.
The correct answer is O(n). Here's why.
We start with the two basic equations.
Note that the second says ``f1 of any positive value is c2 times that value plus f1 of that value over two''. Hence, we can do some precomputation of some values we may need.
Now we're ready to expand the general equation.
Expand f1(n/2):
Expand f1(n/4):
Expand f1(n/8):
Regroup the initial terms:
Rephrasing in terms of powers of 2:
Generalizing:
Let k = log2n:
Simplify the final term:
And again:
What can we do about the sum? We can observe that there's a pattern.
This sum quickly approaches (but never exceeds) 2n.
Hence
For Big-O analysis, the constants no longer matter. Hence f1(n) is in O(n).
Note that it might be helpful to consider the two parts of the recursive definition of f1(n):
The biggest problem I saw was that many of you were unsure as to when we can ``ignore constants''. You can't drop the constants until right at the end, when you have f(n) expressed as a combination of values with no recursive call. (I'd tried to suggest that in the question, since both Carl and Carla had analyzed the problem by dropping or adding different constants.) In some cases, but not all, it's okay to replace a constant by 1. This example suggests that it's not okay if the constant is a multiplicand of the recursive component.
Grading:
Times: 5 minutes, 15 minutes, 20 minutes, 30 minutes (x4), 45 minutes (x2), 1 hour (x3), 1.5 hours, 2 hours (x6), unspecified (x5)
Carla and Carl have decided to write a program to determine the greatest difference between any two values in an array of integers. They recall seeing a similar formulation on assignment 3:
To find the smallest difference between any two
different numbers in a collection ...
Set estimate to ``infinity''
For each value, v, in the collection
For each value, u, not equal to v
If |u-v| < estimate then
Set estimate to |u-v|
Return estimate
They rewrite this as:
To find the greatest difference between any two
different numbers in a collection ...
Set estimate to 0
For each value, v, in the collection
For each value, u, not equal to v
If |u-v| > estimate then
Set estimate to |u-v|
Return estimate
They then implement both methods as follows.
/**
* Utilities for finding interesting facts about arrays of integers.
*
* @author Samuel A. Rebelsky
* @author Carla Caffeinated
* @author Carl Caffeinated
* @version 1.0 of October 1999
*/
public class DifferenceComputer {
/**
* Determine the greatest difference between any pair of values
* in the an array of integers.
* Pre: The array is nonempty.
* Pre: The greatest difference is less than the maximum integer.
* Post: Returns the largest |values[i]-values[j]|.
*/
public int greatestDifference(int[] values) {
int estimate = 0;
int difference;
// For each value, values[i], in the collection
for (int i = 0; i < values.length; ++i) {
// For each value, values[j], in the collection
for (int j = 0; j < values.length; ++j) {
// Determine the difference between the two values
difference = Math.abs(values[i]-values[j]) ;
// If it's bigger than the biggest difference so far then
if (difference > estimate) {
// Update our estimate of the biggest difference
estimate = difference;
}
} // for j
} // for i
return estimate;
} // greatestDifference(int[] values)
/**
* Determine the greatest difference between any pair of values
* in the an array of integers.
* Pre: The array is nonempty.
* Pre: The greatest difference is less than the maximum integer.
* Post: Returns the largest |values[i]-values[j]|.
*/
public int leastDifference(int[] values) {
int estimate = Integer.MAX_VALUE;
int difference;
// For each value, values[i], in the collection
for (int i = 0; i < values.length; ++i) {
// For each value, values[j], in the collection
for (int j = 0; j < values.length; ++j) {
// If the two values are not the same
if (values[i] != values[j]) {
// Determine the difference between the two values
difference = Math.abs(values[i]-values[j]) ;
// If it's smaller than the least difference so far then
if (difference < estimate) {
// Update our estimate of the least difference
estimate = difference;
}
} // if the two values are different
} // for j
} // for i
return estimate;
} // leastDifference(int[] values)
} // class DifferenceComputer
They even go so far as to build a test class and their program seems to work.
import SimpleOutput;
/**
* Test our amazing and clearly marketable difference computer. Thanks
* to our beloved teacher, Sam Rebelsky, for giving us the initiative
* to create such a great product.
*
* Usage:
* ji TestDC value1 value2 ... valuen
*
* @author Carl "Creative Code" Caffeinated
* @author Carla "Clearly Clever" Caffeinated
* @version 1.0 of October 1999
*/
public class TestDC {
public static void main(String[] args) {
// Prepare for output.
SimpleOutput out = new SimpleOutput();
// The array of integers.
int[] values = new int[args.length];
// An index into that array;
int numValues = 0;
// Did the user screw up? Assume not.
boolean badInput = false;
// Create something that can compute differences.
DifferenceComputer computer = new DifferenceComputer();
// Convert each value to an integer. Let the user know if (s)he
// screwed up.
for (int i = 0; i < args.length; ++i) {
try {
values[numValues++] = Integer.parseInt(args[i]);
}
catch (NumberFormatException nfe) {
out.println("'" + args[i] + "' is not a number");
badInput = true;
}
} // for
// If the user gave bad input, we need to update the array
if (badInput) {
int[] tmp = values;
values = new int[numValues];
for (int i = 0; i < numValues; i++) {
values[i] = tmp[i];
} // for
} // if (badInput)
// Find the biggest difference
out.print("The greatest difference between values is: ");
out.println(computer.greatestDifference(values));
// And the least.
out.print("The least difference between values is: ");
out.println(computer.leastDifference(values));
} // main(String[])
} // class TestDC
Because they'd done the homework assignment (or at least checked the answer key), they know that the running time of this algorithm is O(n2), were n is the number of elements in the array.
They are bragging about their solution to Mable and Myron Mathemagician when their friends observe ``You should be able to find the greatest difference in many fewer steps, perhaps even O(n)!'' Help the Caffeinateds write a better solution. The Mathemagicians suggest that you think about how the greatest difference differs from the least difference.
You need not write working Java code. An algorithm in understandable pseudocode is fine.
This is an O(n) algorithm, since finding the smallest value is O(n), finding the largest value is O(n) and computing the difference is O(1).
As many of you realized, part of the intent of this problem was for you to realize that an apparantly slight change in the phrasing of a problem can have a large impact on the code you write.
A number of you failed to include the running time of your algorithm. I checked, and the problem did not require you to do so. Hence, I gave a few extra points to those who gave a running time with some analysis.
Grading:
Times: 5 minutes (x3), 10 minutes, 20 minutes (x3), 45 minutes (x2), 1 hour (x5) 1-2 hours, 1.5 hours (x2), 2 hours (x2), unspecified (x5)
Mable and Myron Mathemagician have decided to implement Quicksort. Here's what they've come up with so far.
import Array;
import Comparator;
import IncomparableException;
import Sortable;
/**
* Arrays that can be sorted using the amazing Quicksort routine. Note
* that we violate Java's method naming conventions because Quicksort is
* a proper name.
*
* @author Samuel A. Rebelsky (general structure)
* @author Mable Mathemagician
* @author Myron Mathemagician
* @version 1.1 of October 1999
*/
public class Quicksortable
extends Array
implements Sortable
{
// +--------------+--------------------------------------------
// | Constructors |
// +--------------+
/**
* Build a new sortable array of a particular size.
*/
public Quicksortable(int n) {
super(n);
} // Quicksortable(int)
/**
* Build a new sortable array with a particular set of elements.
*/
public Quicksortable(Object[] elements) {
super(elements);
} // Quicksortable(Object[])
// +-----------------------+-----------------------------------
// | Methods from Sortable |
// +-----------------------+
/**
* Sort an array using Quicksort.
* Pre: All elements in the array can be compared to each other.
* Post: The array is sorted (using the standard meaning).
*/
public void sort(Comparator compare)
throws IncomparableException
{
sort(compare, null);
} // sort(Object[])
/**
* Sort an array using Quicksort. If observer is non-null,
* prints out pithy notes about the sorting.
* Pre: All elements in the array can be compared to each other.
* Post: The array is sorted (using the standard meaning).
*/
public void sort(Comparator compare, SimpleOutput observer)
throws IncomparableException
{
Quicksort(0, size()-1, compare, observer);
} // sort(Object[])
// +----------------+------------------------------------------
// | Helper Methods |
// +----------------+
/**
* Sort part of an array using Quicksort.
* Pre: All elements in the subarray can be compared to each other.
* Pre: 0 <= lb <= ub < size()
* Post: The array is sorted (using the standard meaning).
*/
protected void Quicksort(int lb, int ub,
Comparator compare,
SimpleOutput observer)
throws IncomparableException
{
if (observer != null) {
observer.println("lb = " + lb + "; ub = " + ub);
}
// Variables
Object pivot; // The pivot we select. Must be part of the subarray.
int mid; // The position of the pivot
// Base case: size one arrays are sorted.
if (lb == ub) return;
// Pick a pivot and put it at the front of the array.
swap(lb,pickPivot(lb,ub));
// Determine the position of the pivot, while rearranging the array.
mid = partition(lb,ub,compare);
// Recurse on nonempty subarrays.
if (lb<=mid-1) Quicksort(lb,mid-1, compare, observer);
if (mid+1<=ub) Quicksort(mid+1,ub, compare, observer);
} // Quicksort
/**
* Split the subarray given by [lb .. ub] into ``smaller'' and
* ``larger'' elements, where smaller and larger are defined by
* their relationship to a pivot. Return the index of the pivot
* between those parts. Uses the first element of the array
* as the pivot.
* Pre: All the elements in the subarray can be compared.
* Post: Returns n such that for all i between lb and n inclusive
* and j between n+1 and ub inclusive, get(i) <= pivot < get(j).
*/
protected int partition(int lb, int ub, Comparator compare)
throws IncomparableException
{
// STUB. Can you figure it out?
return lb;
} // partition(int, int, Comparator)
/**
* Pick a pivot in a subarray.
* Pre: 0 <= lb <= ub < size()
* Post: returns the index of the pivot (a value between lb and ub inclusive).
*/
protected int pickPivot(int lb, int ub) {
// Simple implementation: pick the last element. Might be extended
// to do something more interesting, such as pick a random element
// in the subarray.
return ub;
} // pickPivot(int,int)
} // Quicksortable
They've even convinced me to write them a test class.
import IncomparableException;
import StringComparator;
import Quicksortable;
import SimpleOutput;
/**
* A test of the Quicksortable class. Sorts the strings on the command
* line and then prints them out.
*
* @author Samuel A. Rebelsky
* @version 1.0 of October 1999
*/
public class TestQS {
/** Do the testing.
*
* @exception IncomparableException
* Never, since StringComparator never throws one, but it's
* easier to claim that we might throw one since it seems that
* the sort method might.
*/
public static void main(String[] args)
throws IncomparableException
{
// Prepare for output.
SimpleOutput out = new SimpleOutput();
// Build the array for sorting.
Quicksortable stuff = new Quicksortable(args);
// Sort!
stuff.sort(new StringComparator(),out);
// And print it out.
for (int i = 0; i < stuff.size(); ++i) {
out.println(i + ": " + stuff.get(i));
} // for
} // main(String[])
} // class TestQS
Unfortunately, they haven't figured out how to write the
partition method. They've asked their friends Carl and
Carla to help. However, Carl and Carla are too busy raking in cash from
their code to help. So Mable and Myron have turned to you.
Write the partition method for them.
Make sure to test your code.
I decided to rewrite partition without referring to my
notes from Java Plus Data Structures.
/**
* Split the subarray given by [lb .. ub] into ``smaller'' and
* ``larger'' elements, where smaller and larger are defined by
* their relationship to a pivot. Return the index of the pivot
* between those parts. Uses the first element of the array
* as the pivot.
* Pre: All the elements in the subarray can be compared.
* Post: Returns n such that for all i between lb and n inclusive
* and j between n+1 and ub inclusive, get(i) <= pivot < get(j).
*/
protected int partition(int lb, int ub, Comparator compare)
throws IncomparableException
{
// Strategy: split the array into three parts: the stuff known to
// be less-than-or-equal to the pivot, the stuff known to
// be greater than the pivot, and the stuff of unknown
// character.
// Initially (and at every repetition of the main loop),
// Smaller or equal stuff is in get(lb) .. get(lower)
// Bigger stuff is in get(upper+1) .. get(ub)
// Unknown stuff is in get(lower+1) .. get(upper)
int lower = lb;
int upper = ub;
// Get the pivot
Object pivot = this.get(lb);
// Keep going until we hit the middle element.
while (lower < upper) {
// Try to expand the upper range. Stop when you find a
// small element or run out of things to look at
while ( (compare.lessThan(pivot, this.get(upper)))
&& (lower < upper) ) {
upper--;
} // expand the upper range
// Try to expand the lower range. Stop when you find a
// large element or run out of elements.
while ( ( (compare.lessThan(this.get(lower),pivot))
|| (compare.equals(pivot, this.get(lower))) )
&& (lower < upper) ) {
lower++;
} // expand the lower range.
// If lower is not the same as upper, we've found a small
// element in the upper range and a large element in the
// smaller range, so swap 'em
// of place.
if (lower != upper)
this.swap(lower,upper);
} // while
// We want to put the pivot in the middle. lower gives
// the position of the last "small" element. Put the
// pivot there.
this.swap(lb,lower);
// The pivot is now at position lower.
return lower;
} // partition(int, int, Comparator)
Another way to test for ``X is less than or equal to pivot'' is to use
!compare.lessThan(pivot,X)).
Just for the fun of it, I also tried to work from the code in Java Plus Data Structures.
/**
* Split the subarray given by [lb .. ub] into ``smaller'' and
* ``larger'' elements, where smaller and larger are defined by
* their relationship to a pivot. Return the index of the pivot
* between those parts. Uses the first element of the array
* as the pivot.
*
* Based on the partition method given on pp. 54-55 of the
* 31 March 1999 draft of Java Plus Data Structures by Nell Dale,
* Sam Rebelsky, and Chip Weems. Changes are typically marked with X.
* The most common change was to use get(i) instead of A[i]. Since
* our comparators lack lessEqual, I needed to implement that with
* both (lessThan(..) or equal(..)). At Nell's urging, I also
* switched preincrement and predecrement (++x and --x) to
* postincrement and postdecrement (x++ and x--). I also changed
* the swap for last and first to eliminate the test. I used
* this.swap rather than swap. I added braces around the bodies of
* loops to make them easier to read. Finally, since I was required
* to use slightly different parameters, I did so.
*
* Pre: All the elements in the subarray can be compared.
* Post: Returns n such that for all i between lb and n inclusive
* and j between n+1 and ub inclusive, get(i) <= pivot < get(j).
*/
protected int partition(int lb, int ub, Comparator compare)
throws IncomparableException
{
// Our pivot, used to determine "smaller" and "larger" elements.
Object pivot = this.get(lb); // X: A to get
// Elements get(lb) .. get(first) are <= pivot. Since // X: A to get
// the pivot is at the front, we can set first to lb.
int first = lb;
// Elements get(last+1) .. get(ub) are > pivot. Since // X: A to get
// we know nothing about the contents of the array, we set
// last to the end.
int last = ub;
// Keep going until we run out of out-of-place elements.
while (first < last) {
// COMMENTS DROPPED
// Skip over big elements on the right. // X: Rewrite
while ( (compare.lessThan(pivot, get(last))) && // X: A to get
(first < last) ) { // A: brace
last--; // X: postfix
} // while there are big elements on the right // ADDED
// COMMENTS DROPPED
// Skip over small elements on the left. // X: Rewrite
while ( ( compare.lessThan(get(first), pivot) // X: A to get
|| compare.equals(get(first), pivot) ) // and lessEquals
&& (first < last) ) {
first++;
} // while there are small elements on the left // ADDED
// COMMENTS DROPPED. NEW COMMENT FOLLOWS
// What do we know? We stopped the second loop when
// we hit a larger element or when first equaled last.
// In either case, we can safely swap first and last.
this.swap(first,last); // X: added "this."
} // while
// COMMENTS DROPPED.
// The element at postion first is <= pivot. // New
// Hence, we can safely swap it and the pivot so // New
// that the pivot is in the middle. // New
this.swap(lb,first); // X: added "this."
// Return the location of the pivot.
return first;
} // partition(int, int, Comparator)
Because I mistyped one line, I introduced an error that took me some time to correct. The copy-update-debug-correct cycle took me about 30 minutes. Note that there were two basic changes:
get(i) instead of A[i]. This has
to do with how we've set up the structure of our class.
(compare.lessThan(get(lower),pivot) ||
compare.equals(get(lower,pivot))) instead of
compare.lessEqual(A[i],pivot) since
our comparators don't support lessEqual.
As many of you surmised, this question had a number of purposes,
particularly seeing how you did at combining concepts (Quicksort,
our Array class, inheritance, etc.). It was also
intended to give you the opportunity to discover the importance of
details in algorithm design without having too do too much design.
Many of you copied code fairly close to that from Java Plus Data Structures. If you did so, you must cite that code (as I said in the policies). `` If you find ideas in a book or on the Web, be sure to cite them appropriately. '' While it is a violation of Grinnell's academic conduct policy not to cite code, I am treating such violations as ``lack of craft'' rather than intentional misconduct.
One of the intents of object-oriented programming is that you focus on
the methods of the classes you use, and stay away from the underlying
implementation (including the fields). This is true not only for the
classes you use directly, but also for the classes that you inherit
from. Hence, I expected you to use this.get and
this.set rather than this.objects[].
Some common errors:
get(0) instead of get(lb).
The pivot is the first element of the subarray. Hence, it is
inappropriate to use the 0th element (since the 0th element might
not be in the subarray).
compare.lessThan(get(lower),pivot).
Unfortunately, in order for partitioning to work correctly, you need
to make sure that the pivot stays in position lb so that
the final swap puts the pivot in the middle. Unless
you made other changes to the code, you would end up putting something
else in the lb position and then into the middle.
Grading:
objects[] directly, rather than get,
set, and/or swap: -2 points
Times: 2 hours (x6), 2-4 hours, 3 hours (x2), 3-4 hours, 4 hours (x3), 6 hours (x3), 7 hours, 10 hours (x2), unspecified (x5)
Carl and Carla have become so enamored of divide-and-conquer that they use it for almost every algorithm they write. Last week, they needed to write a search method for unsorted lists, and decided to use divide-and-conquer. Of course, since they don't know which half to look in if the object is not in the middle, they search in both halves. Here's their code (yes, they still need to work on their commenting).
import Comparator;
/**
* Utilities for searching in arrays.
*
* @author Carl Caffeinated
* @author Carla Caffeinated
*/
public class Searcher {
/**
* Determine if a value is in the array.
*/
public boolean search(Object lookForMe, Object[] lookHere, Comparator compare)
throws IncomparableException
{
return search(lookForMe, lookHere, 0, lookHere.length-1, compare);
} // search(Object, Object[])
/**
* Determine if a value is in a subarray.
*/
protected boolean search(Object lookForMe, Object[] lookHere,
int lb, int ub,
Comparator compare)
throws IncomparableException
{
// Is the subarray empty? If so, the object can't be there.
if (ub < lb) return false;
// Otherwise, it must be in the middle, left half, or right half.
int mid = (lb + ub) / 2;
return ( compare.equals(lookForMe, lookHere[mid]) ||
search(lookForMe, lookHere, lb, mid-1, compare) ||
search(lookForMe, lookHere, mid+1, ub, compare) );
} // search(Object, Object[], int, int)
} // class Searcher
Unfortunately, Carla and Carl have realized that they just don't get running time analysis and ask for your help. Determine the running time of this method.
We can begin by evaluating the running time informally. In the worst case, we need to look at each element (that is, in both halves), so we spend at least O(n) just looking at elements. Splitting seems to take less time, so we'll stick with that.
But how much time do we spend splitting? We split n elements into two sets of n/2 elements in 1 step. We split each set of n/2 elements into two sets of n/4 elements in 1 step, so both splits takes us 2 steps. We split each set of n/4 elements into two sets of n/8 elements in 1 step. For such splits take us 4 steps. Reaching the end: We split each set of 4 elements into two sets of 2 elements. There are n/4 sets of 4 elements, so this is n/4 splits. We split each set of 2 elements into two sets of 1 element. There are n/2 sets of 2 elements, so this is n/2 splits.
We need to evaluate the sum
We'll do it from back to front:
Generalizing:
As k gets large, this approaches n. So there are O(n) spilts.
Note that we ended up needing some semi-formal analysis to compute the number of splits. We also used a similar formula to one we used earlier in the exam. Two related formlations:
We can also do some more formal analysis of the running time, using our traditional recusive definitions of running time. In the worst case, we do both recursive calls. If the subarray has only one element, we spend a constant amount of time (we check the middle element and then do two failed recursive calls). Otherwise, we do some constant work and then two recursive calls, each of which uses about half the problem (it's slightly less, but we'll ignore that). If f(x) is the running time on a problem of size x, then we can write:
I've used x to indicate that we can plug in any positive value. Our eventual goal will be to plug in n and simplify. For now, we'll plug in lots of fractions of n.
We start with the basic equation:
Plug in the value for f(n/2):
Distribute:
Plug in the value for f(n/4):
Distribute:
Plug in the value for f(n/4):
Distribute:
Factor out c2:
Rephrase in terms of powers of 2:
Generalizing:
When k = log2n, we get
Simplifying:
And again:
What can we do about the sequence in parens? Let's consder some terms.
What's the pattern? Each value is one less than a power of 2.
Generalizing, we get
Hence
We can now elminate the constants as we move to Big-O form. f(n) is in O(n).
Grading:
Times: 5 minutes, 10 minutes, 30 minutes (x5), 40 minutes, 1 hour (x3), 1-2 hours, 1.5 hours, 2 hours (x2), a little more than two hours, 4 hours, 6-7 hours, unspecified (x5)
Each of these problems is worth up to five points of extra credit.
Update Quicksortable so that pickPivot
actually selects a random pivot value from within the range lb .. ub.
You will need to refer to the Java API to figure out how to generate
random values. Your code must work.
The best way to select random values is with an object of class
java.util.Random. We see that once we have one
of those objects, we can generate a ``random'' integer value using
nextInt. Of course, that's not likely to be in the
range lb .. ub. Hence, we need to
scale it appropriately. First, we make it positive with
Math.abs. Next, we reduce it to the range
0 .. (ub-lb) using the modulus operator, %.
Finally, we add lb to bring it to the range
lb .. ub.
Here are the new lines:
import java.util.Random;
...
// +--------+--------------------------------------------------
// | Fields |
// +--------+
/** A random number generator for use in picking pivots. */
Random generator;
...
public AltQuicksortable(int n) {
super(n);
generator = new Random();
} // AltQuicksortable(int)
...
public AltQuicksortable(Object[] elements) {
super(elements);
generator = new Random();
} // AltQuicksortable(Object[])
...
protected int pickPivot(int lb, int ub) {
// Pick a random number.
int pivloc = generator.nextInt();
// Make it positive.
pivloc = Math.abs(pivloc);
// Reduce it to 0 .. ub-lb.
pivloc = pivloc % (1+ub-lb);
// Shift to lb .. ub.
pivloc = pivloc + lb;
// That's it, we're done.
return pivloc;
} // pickPivot(int,int)
Of course, if I wasn't so concerned about documenting all the steps, I'd use the following.
protected int pickPivot(int lb, int ub) {
return lb + (Math.abs(generator.nextInt()) % (1+ub-lb));
} // pickPivot(int,int)
Your primary goal was to pick a value from the range lb .. ub. If you didn't do that (for example, if you picked a value between 0 and the number of elements in the complete array), you got very little credit (1 point).
A second goal was to produce an O(1) algorithm. I wasn't very pleased by algorithms that took an unspecified (or unclear) amount of time.
Times: 10 minutes, 15 minutes (x2), 30 minutes (x3), 45-60 minutes, 1 hour, 2 hours, not done (x13)
Mable and Myron, apparently frustrated at Carl and Carla's lack of help,
tell Carl and Carla ``not only is your
greatestDifference much too slow, so is your
leastDifference''. Determine a better way (in terms of
Big-O running time) to implement leastDifference. In
this case, working code is not necessary. All you need to do is
convince me that you've come up with the appropriate idea (and analyzed
the running time).
Unfortunately, we can't use the same elegant code as in problem B. However, we can note that smaller differences will occur between adjacent values in a sorted list. Hence, we can improve our computation if we sort the list first.
Sort the list For each pair of adjacent values Compute the difference Return the smallest computed difference
Sorting takes O(nlog2n). Looking at all the pairs and finding the smallest takes O(n). Hence, this is an O(nlog2n) algorithm.
The most common incorrect solution was to look at all the elements ``to the right of'' the value we picked first. Something like the following
for (int i = 0; i < values.length; i++) {
for (int j = i+1; j < values.length; j++) {
difference = Math.abs(values[i]-values[j]);
if (difference < estimate) {
estimate = difference;
}
}
}
Unfortunately, this is no better, at least in the Big-O sense. The running time is basically
As we discussed in class (and a footnote in the book), this is simply
And that is in O(n2).
Times: 15 minutes (x2), 20 minutes, 30 minutes (x2), 1 hour (x2), not done (x15)
A few of you expressed a desire to see a Comparator that
could compare string representations of integers. Why would you want
such a class? So that when you ran
% java TestQS 1111, 50, 400, 2
the result would be
2, 50, 400, 1111
rather than
1111, 2, 400, 50
I agreed to add such a comparator as an extra credit problem.
There is some question as to what types the comparator would expect.
It is most natural for it to look for Integers. However,
our program starts with Strings. What are the options?
We can make our comparator do the converting, or we can do the converting
ourselves before we call the sort method.
Here is a Comparator that does the conversion. Note
that it is probably somewhat more sophisticated in its error checking
than those that you wrote. The code is also annoyingly duplicated.
import Comparator;
/**
* Compares two objects by considering their values as integers.
* The objects should be Integers, Smarts that can be transformed
* to Integers, or ....
*
* @author Samuel A. Rebelsky
* @version 1.0 of October 1999
*/
public class SmartIntegerComparator
implements Comparator
{
/**
* Determines if the integer corresponding to the first object
* is the same as the integer corresponding to the second object.
* Pre: The two objects are initialized and can be converted to integers.
* Post: Returns true if they are equal and false otherwise.
*
* @exception IncomparableException
* If either or both canot be converted to integers.
*/
public boolean equals(Object first, Object second)
throws IncomparableException
{
// An error message. Becomes something other than the
// empty string if there is an error.
String error = "";
// The integers that correspond to the two parameters.
// Initialized to keep Java happy.
int firstInt = 0;
int secondInt = 0;
// Try to get the first integer.
try { firstInt = Integer.parseInt(first.toString()); }
catch (Exception e) {
error = error + "'" + first.toString() + "' is not an integer. ";
}
// Try to get the second integer.
try { secondInt = Integer.parseInt(second.toString()); }
catch (Exception e) {
error = error + "'" + second.toString() + "' is not an integer. ";
}
// If we've hit an error, tell the user.
if (!error.equals("")) {
throw new IncomparableException(error);
}
// Otherwise, do the normal comparison.
return firstInt == secondInt;
} // equals(Object,Object)
/* Determines if the integer corresonding to the first object
* is less than the integer corresponding to the second object.
* Pre: The objects must be convertable to integers.
* Post: Return true if the first precedes the second and
* false otherwise.
*
* @exception IncomparableException
* If either or both cannot be converted to integers.
*/
public boolean lessThan(Object first, Object second)
throws IncomparableException
{
// An error message. Becomes something other than the
// empty string if there is an error.
String error = "";
// The integers that correspond to the two parameters.
// Initialized to keep Java happy.
int firstInt = 0;
int secondInt = 0;
// Try to get the first integer.
try { firstInt = Integer.parseInt(first.toString()); }
catch (Exception e) {
error = error + "'" + first.toString() + "' is not an integer. ";
}
// Try to get the second integer.
try { secondInt = Integer.parseInt(second.toString()); }
catch (Exception e) {
error = error + "'" + second.toString() + "' is not an integer. ";
}
// If we've hit an error, tell the user.
if (!error.equals("")) {
throw new IncomparableException(error);
}
// Otherwise, do the normal comparison.
return firstInt < secondInt;
} // lessThan(Object,Object)
} // class SmartIntegerComparator
Here is the corresponding test class.
import IncomparableException;
import StringComparator;
import Quicksortable;
import SimpleOutput;
/**
* A test of the Quicksortable class. Sorts integer values presented
* on the command line and then prints them out. Based closely on
* TestQS.java by Samuel A. Rebelsky (version 1.0 accessed 15 October
* 1999 in the CS152 Web site).
*
* Changes:
* * Class name
* * Type of comparator used
* * Note about what kind of exception is thrown
*
* @author Samuel A. Rebelsky
* @version 1.0 of October 1999
*/
public class TestQS2 {
/** Do the testing.
*
* @exception IncomparableException
* When the command line parameters are not all integers.
*/
public static void main(String[] args)
throws IncomparableException
{
// Prepare for output.
SimpleOutput out = new SimpleOutput();
// Build the array for sorting.
NewQuicksortable stuff = new NewQuicksortable(args);
// Sort!
stuff.sort(new SmartIntegerComparator());
// And print it out.
for (int i = 0; i < stuff.size(); ++i) {
out.println(i + ": " + stuff.get(i));
} // for
} // main(String[])
} // class TestQS2
Here is some output. Note that the line numbers may be different in
the current version of NewQuicksortable.java. I used
a version which had not yet changed the mechanism for identifying the
pivot.
% ji TestQS2 5 4 3 2 100 32 18
0: 2
1: 3
2: 4
3: 5
4: 18
5: 32
6: 100
% ji TestQS2 zebra aardvark 4 3 2 1 100 50 1000 85 camera
IncomparableException: 'camera' is not an integer. 'zebra' is not an integer.
at SmartIntegerComparator.lessThan(SmartIntegerComparator.java:82)
at NewQuicksortable.partition(Compiled Code)
at NewQuicksortable.Quicksort(NewQuicksortable.java:91)
at NewQuicksortable.sort(NewQuicksortable.java:62)
at TestQS2.main(Compiled Code)
An alternate solution is to assume that the values we receive are, in
fact, Integers (or at least Numbers).
We then do conversions and throw exceptions when we're wrong. I've
used a common helper function here to ease the process.
import Comparator;
/**
* Compares two objects by considering their values as integers.
* The objects should be Integers or Numbers.
*
* @author Samuel A. Rebelsky
* @version 1.0 of October 1999
*/
public class SimpleIntegerComparator
implements Comparator
{
// +-----------+-----------------------------------------------
// | Constants |
// +-----------+
/** Used by compare to indicate the first param is smaller. */
protected static final int SMALLER = -1;
/** Used by compare to indicate the two params are equal. */
protected static final int EQUAL = 0;
/** Used by compare to indicate the first param is larger. */
protected static final int LARGER = 1;
/**
* Determines if the integer corresponding to the first object
* is the same as the integer corresponding to the second object.
* Pre: The two objects are initialized and can be converted to integers.
* Post: Returns true if they are equal and false otherwise.
*
* @exception IncomparableException
* If either or both canot be converted to integers.
*/
public boolean equals(Object first, Object second)
throws IncomparableException
{
return (compare(first,second) == EQUAL);
} // equals(Object,Object)
/* Determines if the integer corresonding to the first object
* is less than the integer corresponding to the second object.
* Pre: The objects must be convertable to integers.
* Post: Return true if the first precedes the second and
* false otherwise.
*
* @exception IncomparableException
* If either or both cannot be converted to integers.
*/
public boolean lessThan(Object first, Object second)
throws IncomparableException
{
return (compare(first,second) == SMALLER);
} // lessThan(Object,Object)
/**
* Determine the relative value of two objects that should
* be Integers.
* Pre: Both objects are Integers or Numbers.
* Post: Returns SMALLER if the integer corresponding to the first is
* smaller than the integer corresponding to the second.
* Post: Returns EQUAL if those two values are the same.
* Post: Returns LARGER if the first is greater than the second.
*
* @exception IncomparableException
* if either or both are not numbers.
*/
protected int compare(Object first, Object second)
throws IncomparableException
{
// An error message. Becomes something other than the
// empty string if there is an error.
String error = "";
// The Numbers that correspond to the two parameters.
// Initialized to keep Java happy.
Number firstInt = null;
Number secondInt = null;
// Try to get the first integer. Note that "(type) exp"
// tells Java to try to treat "exp" as the given type.
try { firstInt = (Number) first; }
catch (Exception e) {
error = error + "'" + first.toString() + "' is not a number. ";
error = error + "It is in " + first.getClass().toString() + ". ";
}
// Try to get the second integer.
try { secondInt = (Number) second; }
catch (Exception e) {
error = error + "'" + second.toString() + "' is not a number. ";
error = error + "It is in " + first.getClass().toString() + ". ";
}
// If we've hit an error, tell the user.
if (!error.equals("")) {
throw new IncomparableException(error);
}
// Otherwise, do the normal comparison.
if (firstInt.intValue() < secondInt.intValue())
return SMALLER;
else if (firstInt.intValue() == secondInt.intValue())
return EQUAL;
else
return LARGER;
} // compare(Object,Object)
} // class SimpleIntegerComparator
Here is the corresponding test class:
import IncomparableException;
import StringComparator;
import Quicksortable;
import SimpleOutput;
/**
* A test of the Quicksortable class and the SimpleIntegerComparator.
* Sorts integer values presented on the command line and then
* prints them out.
*
* @author Samuel A. Rebelsky
* @version 1.0 of October 1999
*/
public class TestIQS {
/** Do the testing.
*
* @exception IncomparableException
* When the command line parameters are not all integers.
*/
public static void main(String[] args)
throws IncomparableException
{
// Prepare for output.
SimpleOutput out = new SimpleOutput();
// Convert the Strings to Integers. Since this is a test
// program, we allow it to crash and burn if any of the
// conversions fail.
Integer[] ints = new Integer[args.length];
for (int i = 0; i < args.length; i++) {
ints[i] = new Integer(args[i]);
}
// Build the array for sorting.
NewQuicksortable stuff = new NewQuicksortable(ints);
// Sort!
stuff.sort(new SimpleIntegerComparator());
// And print it out.
for (int i = 0; i < stuff.size(); ++i) {
out.println(i + ": " + stuff.get(i));
} // for
} // main(String[])
} // class TestIQS
And, just for the fun of it, some test cases.
% ji TestIQS 1 2 3 4 5 6 7 8 9
0: 1
1: 2
2: 3
3: 4
4: 5
5: 6
6: 7
7: 8
8: 9
% ji TestIQS 9 8 7 6 5 4 3 2 1
0: 1
1: 2
2: 3
3: 4
4: 5
5: 6
6: 7
7: 8
8: 9
% ji TestIQS 100 40 5 7 90 19 32 34 300 12 11
0: 5
1: 7
2: 11
3: 12
4: 19
5: 32
6: 34
7: 40
8: 90
9: 100
10: 300
% ji TestIQS 100 40 5 7 90 19 32 34 300 12 11 animal
java.lang.NumberFormatException: animal
at java.lang.Integer.parseInt(Integer.java)
at java.lang.Integer.<init>(Integer.java)
at TestIQS.main(Compiled Code)
Times: 10 minutes (x2), 20 minutes, not done (x18)
Friday, 15 October 1999
Sunday, 17 October 1999
Monday, 25 October 1999
[Instructions] [Search] [Current] [Syllabus] [Links] [Handouts] [Outlines] [Labs] [More Labs] [Assignments] [Quizzes] [Exams] [Examples] [Book] [Tutorial] [API]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/99F/Exams/examsoln.02.html
Source text last modified Mon Oct 25 09:26:07 1999.
This page generated on Mon Oct 25 09:29:51 1999 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu