Assignment 05 Searching and Recursion

CSC220 Assignment05
Searching and Recursion
The goal of this week’s assignment is:
1. Practice searching
2. Continue learning the significance of special cases!
3. Learning how to write test to check your implementation
Things you must do:
1. There are many details in this assignment. Make sure you read the whole
thing carefully before writing any code and closely follow this instruction.
2. You must complete your assignment individually.
3. Always remember Java is case sensitive.
4. Your file names, class names, and package name must match
exactly as they are specified here.
5. Your project must include the methods you implemented in the lab.
Things you must not do:
1. You must not change the file names, class names, package names.
2. You must not change the signature of any of these methods (name,
parameters, …). Just fill in the missing code inside them. However, you are
more than welcome to create any helper methods you need as necessary.
Part 0
• You first must make sure that you have already finished the lab successfully
and have all methods in the lab instruction working properly.
• DO NOT start your assignment unless you have all the features in the lab
working. The tests we run on your assignment may fail if you have an
incorrect lab implementation.
Part 1 – SortedBinarySet Class Implementation
After making sure the methods you implemented during lab work properly, we will
extend the functionality of our class by adding new methods. Please implement the
methods in the order given and pay close attention to the notes:
● public boolean remove(double value)
○ This method should first make a call to findIndex() to find the location of
value, which for now still calls the private sequentialFind (this will change in the
next step). If the element is not present in the list (how do we know?), return
false. Otherwise, remove the element and return true because the list contained
the given value.
○ Be careful about which member variables should be updated before returning
true.
○ Be sure to test your remove method before moving forward.
● public boolean binaryFind(double target)
○ this method will return the index where the element target occurs. This method
must make use of binary search. If target is not present in the list, it should
return the index where it should be added. Use the same formula we learned
during the lab.
○ Change the boolean usesBinarySearch to be false so that findIndex now
calls this method instead. insert() and remove() now make use of binary search
:-)
● public boolean contains(double value)
○ this function returns true if this list contains the value
○ otherwise, it returns false
○ this method must take advantage of the list being sorted and use a binary search
to determine if an item is in the array. (Hint: try reusing your other methods.)
● public boolean containsAll(double[] elements)
○ this function returns true if all the input values (stored in elements) are in the list
○ otherwise, return false
○ this method must take advantage of the list being sorted and use a binary search
to determine if an item is in the array. (Hint: try reusing your other methods.)
● public SortedBinarySet(double[] input)
○ This is another constructor for your class that will accept an array and create an
object of SortedBinarySet that includes the values in the input array
○ Be careful of the following cases
■ the input might have duplicates (remember your list is not allowed to
contain duplicates)
■ the input might not be sorted. Hint: think whether you can reuse any of
the methods you have implemented to make your job easier.
Part 2 – Testing
Unlike previous assignments you are not given any tests as a starting point. You
must create your own tests to examine each method you implemented in the
previous part.
Part 3 – sequentialFind or binaryFind? 🤯
As we have seen this week during lecture, some algorithms are more efficient than
others. For Lab05 we implemented a search routine two ways: sequentialFind(),
and binaryFind().
● For the last part of this assignment, we would like you to think about which one
is more efficient. Remember that findIndex() will use either method based
on the boolean variable usesBinarySearch.
● When you think you have an answer, set the variable usesBinarySearch to
the appropriate value (either true or false) so findIndex() makes use of that
method.
○ For example, setting usesBinarySearch to false would indicate that
sequentialFind() is faster than binaryFind().
To test this out in your Tester, you may consider inserting 100,000 elements (using a
loop) into the sorted set and comparing the time it takes (using
System.nanoTime()) to complete the operation when using sequentialFind or
binaryFind.
Remarks
● Make sure to submit your assignment by (re-)uploading your Lab05 folder into
your csc220-cXXXX folder by the deadline (Tuesday @ 11:59pm)
● Be sure to include Tester.java in your submission to BOX. Remember that we
will not run your testing code; we will only confirm that you have done testing.
● For all your assignments, please start early and seek help early (either
from the instructor or the TAs).