The purpose of this assignment is to practice Java programming with interfaces and generics, and to get acquainted with a simple but useful algorithm.
A simple way to implement a set of elements is to use a sorted array containing those elements. In this case one can use binary search to efficiently decide whether a given element is in the set.
Your first task is to implement a set of integers as a sorted array of integers. You should implement the interface
public interface MyIntSet {
public boolean member(int element);
}using a class:
public class MySortedIntArray implements MyIntSet {
...
}The member method must be implemented using binary search.
Your top-level program should read a file containing a sorted list of integers separated by spaces, use those numbers to create an instance of MySortedIntArray, and use the member method to determine if a given number is present in the file. If your program is invoked using the command java <class> <element> <file>, where <class> is the name of your top-level class, then the program should print true on standard output if <element> is in <file>, and false otherwise.
Binary search is described in the course text book. However, the implementation is actually not quite correct, and it returns an index rather than a boolean.
You must implement binary search on your own. Use a plain array, not an ArrayList. You are not allowed to use other people's programs or programs from standard libraries.
You can use the Scanner class to read the file. You are allowed to use an ArrayList in the main program.
The MyIntSet interface only contains a member method, so there is no requirement to implement an add method. A simpler solution is to just pass an array containing the elements read from the file to the constructor of the MySortedIntArray class. However, you are allowed to implement an add method, in which case you should use a dynamic array.
Your second task is to implement sets with elements of an arbitrary type E. You should implement the generic Java interface
public interface MySet<E> {
public boolean member(E element);
}using a generic class:
public class MySortedArray<E extends Comparable<? super E>> implements MySet<E> {
...
}The member method must be implemented using binary search.
In order to sort elements of type E we must have a way to compare them. You should use the elements' "natural ordering", i.e. the one provided by the Comparable interface. (The somewhat cryptic declaration <E extends Comparable<? super E>> is explained in the course text book: Section 1.5.5 in the second edition, and Section 1.5.6 in the third edition.)
The top-level class, containing main, should not be generic. This class should instantiate E to the type of integers, for instance as follows: new MySortedArray<Integer>(...).
As in part A, if your program is invoked using the command java <class> <element> <file>, where <class> is the name of your top-level class, <file> is a file containing a sorted list of integers separated by spaces, and <element> is an integer, then the program should print true on standard output if <element> is in <file>, and false otherwise.
Follow the instructions for reporting programming assignments carefully. Include a discussion of the time complexity of your implementation of binary search.
Submissions which do not pass certain tests may be summarily rejected.
Implement union and intersection, according to the following extended interface:
public interface MySet<E> {
public boolean member(E element);
public void union(MySet<E> set);
public void intersection(MySet<E> set);
}These operations have linear-time implementations.
If you try to implement the interface above using sorted arrays, then you might encounter a problem when taking the union of the sorted array and an arbitrary object implementing MySet: the latter is not necessarily implemented as a sorted array. A simple solution is to assume that it is, and use a cast to convert it to the type of sorted arrays. However, one could argue that this is not very elegant.
If you add the requirement that MySet has an iterator which can iterate through the elements of the sets in sorted order, then you can use the iterator to implement union and intersection, thus obtaining a more abstract (but perhaps more complex) implementation. One part of this requirement can be expressed by stating that MySet extends the Iterable interface:
public interface MySet<E> extends Iterable<E> {
public boolean member(E element);
public void union(MySet<E> set);
public void intersection(MySet<E> set);
}