[Instructions] [Search] [Current] [Syllabus] [Links] [Handouts] [Outlines] [Labs] [More Labs] [Assignments] [Quizzes] [Examples] [Book] [Tutorial] [API]
This page may be found online at
http://www.math.grin.edu/~rebelsky/Courses/CS152/99S/Handouts/examsoln.02.html.
deleteAll [15 points]
deleteAll [20 points]
findPlace [30 points]
findPlace [10 points]
Our old pals Carla and Carl Caffeinated are back, asking for your help
in writing Java code. They've been building an
ArrayBasedOrderedList class and have decided that they
should include a deleteAllCopies method that deletes
all copies of an element.
Here's what they've come up with
/**
* Delete all copies of elt from the current list.
*/
public int deleteAll(Object elt) {
// A count of the number of elements deleted.
int numDeleted = 0;
// Step through the array, finding equal elements and deleting them.
// Because this is an ordered list, we need to shift after deletion.
for (int i = 0; i < this.length; ++i) {
// Did we find an equal element?
if (elt.equals(this.elements[i])) {
// Shift left
for (int j = i; j < this.length; ++j) {
this.elements[j] = this.elements[j+1];
}
// Delete the last element.
this.elements[this.length] = null;
// Update the length.
this.length -= 1;
// Update the count.
this.numDeleted += 1;
} // if we found an equal element
} // for each element
// That's it.
return numDeleted;
} // deleteAll
deleteAll [15 points]Like many novice programmers, Carl and Carla have made a few subtle errors in writing this function. Identify those errors.
Hint: Some problems occur when the list is full. (Yes, others will occur in other situations.)
There are a number of ways you might have attempted to discern their errors.
delete in
simple ordered lists, taken from
outline 26.
/**
* Delete an element from the list. See the interface for
* preconditions and postconditions.
*/
public void delete(Object element) {
// Step through the list until we find an equal element
for (int i = 0; i < this.length; ++i) {
// Note that we use element.equal because some
// elements of the list may be null
if (element.equals(this.elements[i])) {
// Found it!
// Shift everything down.
for (int j = i; j < this.length-1; ++j) {
this.elements[j] = this.elements[j+1];
// Clear the last thing.
this.elements[this.length-1] = null;
// Update the length.
--this.length;
// And we're done.
return;
} // if found
} // for
// Nope, didn't find it. Nothing else to do.
} // delete(Object)
What have they done wrong? First of all, they haven't handled full
lists very well. In at least two separate instances, they refer
explicitly or implicitly to this.elements[this.length].
Since this.length gives the index of the first
free element, it seems odd to be working with it. In fact, if the
list is full, it will be an error to refer to it.
The lines that read
for (int j = i; j < this.length; ++j) {
this.elements[j] = this.elements[j+1];
}
should read
for (int j = i; j < this.length-1; ++j) {
this.elements[j] = this.elements[j+1];
}
Similarly, the line that reads
this.elements[this.length] = null;
should read
this.elements[this.length-1] = null;
At one point, the write this.numDeleted, but use
just numDeleted everywhere else. Since they have
a local variable called numDeleted, they should
make sure to use it.
// Update the count.
numDeleted += 1;
The last error is the most subtle. When they shift, they don't check the first element that they shifted (they shift an element into the ith slot, but increment i before checking for the next match). There are a number of ways to handle this. The simplest is to decrement i.
// Make sure that we check the first element we shifted.
--i;
Those should be the only errors. The new code looks like:
/**
* Delete all copies of elt from the current list.
*/
public int deleteAll(Object elt) {
// A count of the number of elements deleted.
int numDeleted = 0;
// Step through the array, finding equal elements and deleting them.
// Because this is an ordered list, we need to shift after deletion.
for (int i = 0; i < this.length; ++i) {
// Did we find an equal element?
if (elt.equals(this.elements[i])) {
// Shift left
for (int j = i; j < this.length-1; ++j) { // Fixed
this.elements[j] = this.elements[j+1];
}
// Delete the last element.
this.elements[this.length-1] = null; // Fixed
// Update the length.
this.length -= 1;
// Update the count.
numDeleted += 1; // Fixed
// Make sure we reconsider the first element
// that we shifted.
i -= 1; // Fixed
} // if we found an equal element
} // for each element
// That's it.
return numDeleted;
} // deleteAll
Carl and Carla never learned about preconditions and postconditions. They've hired you to write them for them, because their client has required them. They note ``our client is as extreme as Dr. Rebelsky, so you need to be particularly careful''.
There's a chance you can find an answer to this in one of our course web pages (I didn't check carefully).
Here is one possible solution (somewhat overkill). You may have thought of others.
/** * Delete all values equal to elt from the list. * * Precondition: The list is initialized and has not been * ``damaged'' by improper operations. * Precondition: The list does not contain null. * Precondition: The element to be deleted is not null. * Precondition: The element can be compared to all the elements * of the list using equals (given, since it's an object, but * it doesn't hurt to restate it). * Postcondition: The list contains no elements equal to elt. * Postcondition: No other elements are deleted. * Postcondition: The remaining elements are in the same order * (if x preceded y and neither x nor y was deleted, then * x still precedes y). * Postcondition: The position of the cursor is unspecified. * Postcondition: Returns the number of elements deleted from the list. */
The most common errors were to neglect to key issues: you didn't
talk about ordering after deletion (since it's an ordered list, the
elements that remain have to be in the same order) and you didn't
talk about the effect on iteration (iteration is broken until the
next call to reset; I wrote ``cursor'' on your papers).
Some of you talked about the array in your preconditions or postconditions. Since this is an operation on lists, and arrays are only one way to implement lists, it's best not to mention them.
Some of you went even more overboard than I did. That's understandable, given how picky I seem to be. At some point, you'll find a happy medium.
While Carl and Carla understand big-O analysis, they're not very good at it.
They think that the running time of deleteAll is O(n), but they're
wrong. What is the worst-case running time, and why?
At worst, every element in the array is equal to the specified element. The first time, we need to shift n-1 elements. The next time, we shift n-2 elements. The next time, we shift n-3 elements. Overall, we shift (n-1) + (n-2) + ... + 1 elements, which is (n*(n-1))/2, which is O(n2).
Hence, this is an O(n2) method.
deleteAll [20 points]
Rewrite deleteAll so that it has running time of O(n).
The strategy we'll use will be to use two passes. On the first pass,
we put nulls in the deleted spaces. On the second pass,
we shift things into the blank spaces (using two cursors, one on the
``place to shift into'' and one on the ``place to shift from''.
/**
* Delete all copies of an element. See the accompanying
* documentation for preconditions and postconditions.
*/
public int deleteAll(Object elt) {
// A count of the number of elements deleted.
int numDeleted = 0;
// A cursor for ``place to shift into''
int dest;
// A cursor for ``place to shift from''
int source;
// Pass one. Step through the array, finding equal elements
// and clearing them in preparation for pass two.
for (int i = 0; i < this.length; ++i) {
// Did we find an equal element?
if (elt.equals(this.elements[i])) {
// Clear it.
this.elements[i] = null;
}
// Update the count.
this.numDeleted += 1;
} // for each element
// Pass two: Step through the array, finding spaces and
// filling them in.
for (dest = 0; dest < this.length; ++dest) {
// Is there a space?
if (elements[dest] == null) {
// Find the first nonspace after it.
// Start after the source (if we're already after the source
// we stay where we are.
if (source <= dest) source = dest + 1;
// Look forward until we find a nonblank element or run
// off the end of the list.
while ( (source < this.length) &&
(elements[source] == null) )
++source;
// Have we found something? If so, move it.
if (source < this.length) {
elements[dest] = elements[source];
elements[source] = null;
}
} // if there's a space
} // pass two
// Update the length.
length -= numDleeted;
// That's it.
return numDeleted;
} // deleteAll
Why is this O(n)? The first pass takes O(n) steps, since we need to look at every element. In the second pass, moving the source cursor takes O(n) steps (at worst, we move it all the way through the list) and moving the destination cursor takes O(n) steps. We can do at most O(n) copies. Hence, the total algorithm is O(n).
The above solution was the most common, although many of you chose to do both passes at once (certainly fine; I wrote mine for clarity more than efficiency).
A few of chose a particularly clever variant. You observed that the
thing I call dest is really just source
minus numDeleted, so you didn't need a second counter.
Another solution is to simply make a new array and copy the elements over. Here's that solution (not tested).
/**
* Delete all copies of an element. See the accompanying
* documentation for preconditions and postconditions.
*/
public int deleteAll(Object elt) {
// A new array of elements.
Object[] newElements = new Object[elements.length];
// The length of that new array.
int newLength = 0;
// The number of elements deleted.
int numDeleted = 0;
// Step through the original array, copying over any inequal
// elements.
for (int i = 0; i < length; ++i) {
// If it's equal to the target, just skip it.
if (elt.equals(elements[i])) {
++numDeleted
} // if it's equal to the target
// If it's different from the target, copy it.
else {
newElements[newLength] = elements[i];
++newLength;
} // if it's different from the taret
} // for
// Update to use the new length and elements
elements = newElements;
length = newLength;
// Return the number deleted.
return numDeleted;
} // deleteAll(Object)
A few of you copied the elements into a vector. While this is an interesting idea, unfortunately, it is not a correct one (at least in terms of running time; it's fine in terms of the function actually working). Why is it incorrect? Because you don't know that adding an element to a vector is O(1) time. In fact, in some cases, adding an element to a vector is O(length) time.
After their successes with ordered lists, Carl and Carla have moved on to
sorted lists. They've once again decided to implement lists using arrays,
They've also decided to keep the elements in order in the array. To simplify
things, they've decided that they'll only deal with sorted lists of integers.
Here's the add method they've written, as well as a sketch
of a findPlace method.
/**
* Add a value to this sorted list of integers.
* Pre: The list is initialized, and there have been no invalid
* operations on the list.
* Pre: There is space remaining in the list to add the new element.
* Post: Iteration may be invalidated.
* Post: The value is added, and will be returned in the proper
* order during iteration.
* Post: The length of the list increases by 1.
*/
public void add(int val) {
// Determine the correct position in the list.
int pos = findPlace(val, 0, this.length-1);
// Shift right to insert the element.
for (int j = this.length; j > pos; --j) {
this.elements[j] = this.elements[j-1];
}
// Insert the element.
this.elements[pos] = val;
// Update the length.
this.length += 1;
} // add(int)
/**
* Find the correct position for a value in a part of the
* array used to implement the list. Should be implementable
* using a technique like binary search.
* Pre: The list is initialized, and there have been no invalid
* operations on the list.
* Pre: The subarray lb..ub is sorted.
* Post: Returns a position, pos, such that (1) the element at position
* i is less than or equal to val, for all i less than pos; and (2)
* the element at position j is greater than or equal to val, for all
* j greater than or equal to pos. If no elements already in the subarray
* are greater than val, returns ub+1. If no elements already in the
* subarray are less than val, returns lb.
* Post: No elements are added, deleted, or moved.
*/
protected int findPlace(int val, int lb, int ub) {
// Help!
} // findPlace(int,int,int)
findPlace [30 points]
Implement findPlace using an appropriate variant of
binary search. Note that findPlace differs from
binary search in that when the element isn't in the array, it needs
to report the correct place in the array for the element to be inserted.
(If there's an equal element, that's the correct place to insert the
element.)
As you learned from assignment 6, searching is a subtle issue. Hence, I'd recommend an implementation with testing (but it was up to you).
I was somewhat careful about the preconditions (it would also be appropriate to have lb <= ub). In particular, I wanted to make sure that it was okay to have equal elements on both sides (otherwise, it gets harder to do).
Note that you need to be particularly careful in how you handled the empty list. Testing would quickly reveal that issue.
Here's the
SortedIntList.java
that I came up with. I decided to rewrite things slightly,
so that the initial call to findPlace took only the
value as the parameter (it was useful for testing). This allowed
me to make a simple improvement: the only time we use an index to
the right of the subarray is when we want to be to the right of the
whole array.
import SimpleOutput;
/**
* Sorted lists of integers. Intended for the answer key to
* exam 2 in Grinnell College's CSC152 99S. Also serves as
* its own simple tester: you can specify the elements to
* add/sort on the command line.
*
* @author Samuel A. Rebelsky
* @version 1.0 of March 1999
*/
public class SortedIntList {
// +--------+--------------------------------------------------
// | Fields |
// +--------+
/** The elements of the list. */
int[] elements;
/** The length of the list. */
int length;
/**
* The cursor, used for iteration (although perhaps not
* in this simplified implementation).
*/
int cursor;
// +--------------+--------------------------------------------
// | Constructors |
// +--------------+
/**
* Build a new list with specified capacity.
*/
public SortedIntList(int capacity) {
this.elements = new int[capacity];
this.length = 0;
this.cursor = 0;
} // SortedIntList(int)
/**
* Build a new list of default capacity.
*/
public SortedIntList() {
this(100);
} // SortedIntList
// +----------------+------------------------------------------
// | Public Methods |
// +----------------+
/**
* Add a value to this sorted list of integers.
* Pre: The list is initialized, and there have been no invalid
* operations on the list.
* Pre: There is space remaining in the list to add the new element.
* Post: Iteration may be invalidated.
* Post: The value is added, and will be returned in the proper
* order during iteration.
* Post: The length of the list increases by 1.
*/
public void add(int val) {
// Determine the correct position in the list.
int pos = findPlace(val);
// Shift right to insert the element.
for (int j = this.length; j > pos; --j) {
this.elements[j] = this.elements[j-1];
}
// Insert the element.
this.elements[pos] = val;
// Update the length.
this.length += 1;
} // add(int)
/**
* Clear the list.
*/
public void clear() {
this.length = 0;
} // clear()
/**
* Convert to a string in prepartion for printing.
*/
public String toString() {
if (length == 0) return "()";
String str = "(";
for (int i = 0; i < length-1; ++i) {
str += elements[i] + " ";
}
str += elements[length-1] + ")";
return str;
} // toString()
// +----------------+------------------------------------------
// | Helper Methods |
// +----------------+
/**
* Find the correct position for a value in the part of
* the array used for the list.
* Pre: The list is initialized, and there have been no invalid
* operations on the list.
* Pre: The array used to implement the list is sorted.
* Post: Returns a position, pos, such that (1) the element at position
* i is less than or equal to val, for all i less than pos; and (2)
* the element at position j is greater than or equal to val, for all
* j greater than or equal to pos. If no elements already in the subarray
* are greater than val, returns ub+1. If no elements already in the
* subarray are less than val, returns lb.
* Post: No elements are added, deleted, or moved.
*/
public int findPlace(int val) {
// Special case: empty array.
if (this.length == 0) return 0;
// Special case: After array.
if (val > this.elements[this.length-1]) return this.length;
// Everything else.
return findPlace(val , 0, this.length-1);
} // findPlace(int)
/**
* Find the correct position for a value in a part of the
* array used to implement the list.
* Pre: The list is initialized, and there have been no invalid
* operations on the list.
* Pre: The subarray lb..ub is sorted.
* Pre: lb <= ub
* Pre: val <= the element at position ub.
* Post: See above. Note that since we have that last precondition,
* we'll never return ub+1.
* Post: No elements are added, deleted, or moved.
*/
protected int findPlace(int val, int lb, int ub) {
// Base case: Empty subarray. Use lb.
if (ub < lb) return lb;
// Base case: To the left of lb.
if (val <= elements[lb]) return lb;
// Base case: To the right of ub. This is now not needed
// (because of the precondition and the change in the way
// this is called), but kept for clarity's sake.
// if (val > elements[ub]) return ub+1;
// Determine the middle of the list (won't work for
// really large lists, but c'est la vie).
int mid = (lb + ub) / 2;
// Recursive case: Left half
if (val <= elements[mid])
return findPlace(val, lb, mid);
// Recursive case: Right half
else
return findPlace(val, mid+1, ub);
} // findPlace(int,int,int)
// +------+----------------------------------------------------
// | Main |
// +------+
public static void main(String[] args) {
SimpleOutput out = new SimpleOutput();
int val;
// If the user supplies test values, we use them.
if (args.length != 0) {
SortedIntList ints = new SortedIntList(args.length);
for (int i = 0; i < args.length; ++i) {
out.println("The array is: " + ints.toString());
try {
val = Integer.parseInt(args[i]);
out.println("Adding " + val);
ints.add(val);
}
catch (Exception e) { }
} // for
out.println("The final array is: " + ints.toString());
}
// Otherwise, do some interesting testing. See the
// discussion of the testing of trinary search for
// more information.
else {
SortedIntList ints = new SortedIntList(20);
// For each length of list.
for (int length = 0; length < 20; ++length) {
// Clear the list
ints.clear();
// Fill in the elements 2,4,6,...,20
for (int i = 1; i <= length; ++i) {
ints.add(2*i);
} // for
// For each value between 1 and 2*length+1.
for (val = 1; val <= 2*length+1; ++val) {
// See if findPlace finds the right place.
// Odd numbers i belong in (i-1)/2. Even numbers
// i belong in i/2-1. Using integer division,
// both should be (i-1)/2.
if (ints.findPlace(val) != (val-1)/2) {
out.println("Error placing " + val + " in " +
ints.toString());
out.println(" Result is: " + ints.findPlace(val));
}
} // for each value
} // for each length
} // no command line
} // main(String[])
} // class SortedIntList
findPlace [10 points]
Upon studying the code for add and your O(log2n)
findPlace, Alvin and Althea Analyst declare ``that
findPlace method is needlessly complicated; it will have
no real effect on the running time if you implement it with sequential
search''. Explain why they might say this.
Since it takes O(n) time to shift elements, it doesn't matter whether it takes O(log n) or O(n) to find the proper place. Hence, an iterative version may be the best.
[Instructions] [Search] [Current] [Syllabus] [Links] [Handouts] [Outlines] [Labs] [More Labs] [Assignments] [Quizzes] [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/99S/Handouts/examsoln.02.html
Source text last modified Mon Apr 12 10:00:19 1999.
This page generated on Mon Apr 12 10:06:30 1999 by SiteWeaver. Validate this page's HTML.
Contact our webmaster at rebelsky@math.grin.edu