In this assignment you will complete work the a "utility" class, compsci61b.MyUtilities, by adding methods that search MyList objects for matching values. Two techniques will be implemented: "sequential" (or "linear") searching, which is O(n), and "binary" searching, which is O(log n).
To support binary algorithms, you will also create a new interface and 2 new classes that are like MyList and its implementations, except that they are sorted in order at all times. These are to be placed in the package compsci61b and named MySortedList (the interface) and the MySortedArrayList and MySortedLinkedList classes. You will also so some big oh determinations for the new search methods as applied to the sorted classes.
This assignment is worth 40 points, and consists of 8 exercises. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab6a.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.
In the interface, include one new method: public boolean remove(T value);.
Add comment lines in the file (anywhere you want -- they are just comments) that explain changes in the uses of some methods that appear in the MyList interface. Here are the changes:
Compile and test the interface as you did with "MyIntList" in lab 2a's exercise 1. Jar as lab6a.jar, but do not submit -- the program will be further developed in the following exercises.
Include a private method to convert a value into its index, like getIndex from the lecture notes for topic 5. Note that this method, and the one like it in the ch.13 of our Carrano textbook (getPosition), both modify the index to denote that the value was not actually found at the index, but if it existed at all, it would be at that index. Carrano's scheme makes the value negative -- the scheme from our lecture notes adds size()+1 instead.
In the main test method, create a "MySortedList" reference to a "MySortedArrayList" object, and exercise all of its methods. Make sure that the array expansion and shifting code works correctly. Your work will be scored using a separate testing program that is not provided to you. So make sure that your own testing is sufficient to assure yourself that the class works according to the specs. If you have any questions about the specs, ask in lab or use the online discussion group -- don't assume anything.
For public interface validation, use the same test.java as in lab 2a's exercise 2, but use these statements to create and validate the data structure object:
MyList<Integer> a = new MySortedArrayList<Integer>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.MySortedList));
System.out.println("Should be true: " + (a instanceof compsci61b.MyArrayBasedDataStructure));
System.out.println("Should be true: " + (a instanceof compsci61b.MyArrayList));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));
Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
In the main test method, create a "MySortedList" reference to a "MySortedLinkedList" object, and exercise all of its methods.
For public interface validation, use the same test.java as in lab 2a's exercise 2, but use these statements to create and validate the data structure object:
MyList<Integer> a = new MySortedLinkedList<Integer>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.MySortedList));
System.out.println("Should be true: " + (a instanceof compsci61b.MyLinkedDataStructure));
System.out.println("Should be true: " + (a instanceof compsci61b.MyLinkedList));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));
Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
public static <T> int finds(MyList<T> a, T value)
{
statements go here...
}
Expand main to test this new method.
Your test should include finding of values that you know exist, and a value that does not exist.
Use getEntry to see the values stored in the first, last, and middle locations of the MyList.
Confirm that your method finds the indexes of these values at their correct locations, and that the correct index value is returned for the failed search.
Note that in the case of duplicates, the index returned may be less than the one you expect. So to prevent this problem, replace the values at the locations of interest (first, last, and middle) with values that you know are not in the rest of the MyList, and then search for them.
Here is a way to fill a data structure of Double values with n random numeric values between 0 and 1:
a.clear();
while (a.size() < n)
a.add(Math.random()); //...or for Integer values from 1 and 1000 inclusive, use (int)(1 + 1000 * Math.random())
Hint: you know that the above will never add negative values, so replace the values at the locations of interest with negatives.
Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
public static <T extends Comparable<? super T>> int finds(MySortedList<T> a, T value)
{
statements go here...
}
Expand main to test this new method.
Note that it requires a MySortedList reference instead of a MyList.
Even if a MyList reference variable refers to an object that implements MySortedList, the MyList version of finds gets called.
Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
Use the following code block shell.
public static <T extends Comparable<? super T>> int findb(MyList<T> a, T value)
{
statements go here...
}
You may use either a recursive solution, or an iterative one -- it's your choice.
If you choose recursive, use the findb method to call a private recursive method.
Expand main to test this new method. Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
Perform timing tests on each to confirm your determination of the big oh. Individual searches are fast, so you may want to use "repetitions". Use the spec from lab 4's exercises 5-8, with nicely-aligned columns and 2 decimal digits in the last column's values. Report your determination of the big oh in the output heading, where you see O(?) in the example below.
successful sequential search of a compsci61b.MySortedArrayList, O(?)
n big oh elapsed time in millis elapsed time / big oh norm
----- --------- ---------------------- --------------------- ----
10000 ? ? ? 1.00
20000 ? ? ? ?
40000 ? ? ? ?
80000 ? ? ? ?
Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
Perform timing tests on each to confirm your determination of the big oh. Use the spec from lab 4's exercises 5-8, with nicely-aligned columns and 2 decimal digits in the last column's values. Report your determination of the big oh in the output heading, where you see O(?) in the example below.
successful search of a compsci61b.MySortedLinkedList, O(?)
n big oh elapsed time in millis elapsed time / big oh norm
----- --------- ---------------------- --------------------- ----
10000 ? ? ? 1.00
20000 ? ? ? ?
40000 ? ? ? ?
80000 ? ? ? ?
Compile, jar as lab6a.jar, and run, but do not submit -- the program will be further developed in the following exercises.
Create your final version of lab6a.jar, with files from this and all previous labs.
Post your lab6a.jar file to your student UNIX account for grading and credit.
[ Home | Contact Prof. Burns ]