handout #3
CSE143—Computer Programming II
Programming Assignment #1
due: Thursday, 4/8/10,
9 pm
For your first programming assignment
you are to write a class called SortedIntList that is
a variation of the ArrayIntList class discussed in
lecture (handout #2). The primary
differences are that your new class must maintain the list of integers in
sorted (non-decreasing) order and that it will have an extra option to specify
that the numbers should be unique.
The new class should have the same
public methods as the old class except for the two-parameter
add method that adds a value at a particular index. Because we want to keep the list in sorted
order, we won’t allow the client to specify where something should go, so this
method should not be a public method of the new class.
Two of the methods should be
rewritten. The single-parameter add method should no longer add at the end of the list. It should add the value in an appropriate
place to keep the list in sorted (non-decreasing) order. The add method also has to pay attention to
whether the client has requested “unique” values, in which case it has to be
careful not to add any duplicates to the list.
Your add method should not re-sort the entire list (either by calling Arrays.sort or something you wrote yourself). Finding the correct position and inserting
the new element at that position is more efficient than resorting
the whole list.
In addition, the indexOf
method should be rewritten to take advantage of the fact that the list is
sorted. It should use the much faster
binary search algorithm rather than the sequential search algorithm that is
used in the original ArrayIntList class (more on this
later). We will also slightly change the
postcondition of indexOf. The ArrayIntList
version promises to return the index of the first occurrence of the search
value. Because we are using a binary
search, we will instead guarantee only that the index is for an occurrence of the search value (not
necessarily the first one).
The other methods from ArrayIntList like the remove method can be used without
modification in the new class. You
should comment each method in your class.
If you borrow the comments from the ArrayIntList
class, then be sure to comment the new methods in a similar manner.
Your new class will have an extra piece
of state information. Each SortedIntList will keep track of whether or not it is
limited to unique values. Think of it as
a sort of on/off switch that each list has.
If the unique switch is set to off (false), then the list adds everything,
even if that leads to duplicate values.
If the unique switch is set to on (true), then calls on add that pass
values already in the list have no effect (i.e., add ensures that no duplicates
are added). For example, if you start
with an empty list that has the unique switch off, then adding three
occurrences of the number 42 will generate the list [42, 42, 42]. Adding those same three occurrences of 42 to
an empty list that has the unique switch on will
generate the list [42].
This extra piece of state will require
the addition of several new methods. Your
class should keep the DEFAULT_CAPACITY constant and should have a total of four
constructors:
Method |
Description |
SortedIntList(boolean unique, int capacity) |
This
should construct a list with given capacity and with the given setting for
whether or not to limit the list to unique values (true means no duplicates,
false means duplicates are allowed) |
SortedIntList(int capacity) |
This
should construct a list with the given capacity and with unique set to false
(duplicates allowed) |
SortedIntList(boolean unique) |
This
should construct a list of default capacity with the given setting for unique
(true means no duplicates, false means duplicates are allowed) |
SortedIntList() |
This
should construct a list of default capacity with unique set to false
(duplicates allowed) |
Your class should include the following
two new methods:
Method |
Description |
boolean getUnique() |
This
method should return the current setting for unique (true means no
duplicates, false means duplicates are allowed) |
void
setUnique(boolean value) |
This
method allows the client to set whether or not to allow duplicates (true
means no duplicates, false means duplicates allowed) |
The setUnique
method presents a potential problem for us.
Suppose that the client has constructed a list and has added many
values, including duplicates. If the
client then tries to set unique to true, this is supposed to prevent
duplicates. But the duplicates are
already there. In this case, the setUnique method should remove the duplicates and should
guarantee that no additional duplicates are added unless the client changes the
setting back to false. If the client
changes the setting back to false, that will mean that duplicates can then be
added, but this doesn’t have to behave like an “undo” operation that would put
back duplicates that you previously removed.
You are required to use the built-in Arrays.binarySearch method discussed in section for all of
your location testing (Where is a value?
Where would I insert a new value?).
You can find the documentation for it in the Java API documentation that
is the first link under “useful links” on the class web page. Keep in mind that because this is a static
method, you have to use the class name in calling it. For example, to find the location of the
value 42 in an array called data when we want to explore the first twelve
elements, you’d say something like:
int index = Arrays.binarySearch(data, 0, 12, 42);
Remember that the “from index” is
inclusive, which is why we use 0, and the “to index” is exclusive, which is why
we use 12.
To get access to the Arrays class, you
should include this line at the beginning of your class:
import java.util.*;
In terms of correctness, your class must
provide all of the functionality described above and the execution time for indexOf must indicate that you are using a binary search
rather than a sequential search. In
terms of style, we will be grading on your use of comments, good variable
names, consistent indentation, and good coding style to implement these
operations.
You should name your file
SortedIntList.java and you should turn it in electronically from the
“assignments” link on the class web page.
Development
Strategy
One
of the most important techniques for software professionals is to develop code
in stages rather than trying to write it all at once (the technical term is iterative enhancement or stepwise refinement). It is also important to be able to test the
correctness of your solution at each different stage.
We have noticed that many 143 students
do not develop their code in stages and do not have a good idea of how to test
their solutions. As a result, for this
assignment we will provide you with a development strategy and some testing
code. We aren’t going to provide
exhaustive testing code, but we’ll give you some good examples of the kind of
testing code we want you to write.
We are suggesting that you develop the
program in three stages:
1. For this
version, we won’t worry about the issue of unique values. We just want a basic version of the class
that keeps a list in sorted order and that uses binary search to speed up
searching. This stage involves all of
the following (not necessarily in this order):
a. Copy
ArrayIntList.java to SortedIntList.java and change all occurrences of ArrayIntList to SortedIntList. That way you’ll have a new class that has the
same behavior as the old ArrayIntList class
(including the two constructors).
b. Make sure that
the two-argument add method is no longer a public method.
c. Modify the one-argument add method so that it preserves sorted order. You may need to use binary search if your
solution involves two steps (first locate, then insert).
d. Modify indexOf so that it uses the binary search method.
2. Modify your code
so that it keeps track of whether or not the client wants you to guarantee that
the list has unique values. Add the two
constructors that involve setting unique and modify add so that it doesn’t add
duplicates if unique is set to true.
3. Modify your code
to have getUnique and setUnique. Remember that if the client calls setUnique and sets the value to true, you have to eliminate
any duplicates that might be in the list.
We will be providing testing code for
each of these three stages and for this program only you are allowed to discuss
how to write testing code with other students.
Keep in mind that the tests are not guaranteed to be exhaustive. They are meant to be examples of the kinds of
tests you should perform. In particular,
you will want to do a lot of simpler testing before you try running any of
these high-powered tests that really push the limits.