Elementary Data Structures and Algorithms  Assignment 4

Elementary Data Structures and Algorithms
 Assignment 4

Assignment 4 Skills
Designing an ADT
Creating an interface based on ADT
Implementing an ADT using an interface
Assignment 4 Background
For this assignment, we wish to implement a Set Data Structure. We will define our Set Abstract Data
Type (ADT) as: a Set is an unordered, finite collection of objects with no duplicates.
Our Set ADT is similar to our Bag ADT, with one notable difference: duplicates were allowed in bags,
but are not allowed in sets.
Assignment 4 Requirements
1. (25%) Write an interface called SetInterface. This interface will define required set operations.
This interface should have the following methods defined:
(a) Add, that adds an element to the set if able.
(b) Remove (random), that removes a (random) element from the set. This does not have to be
truly random.
(c) Remove (specified), that removes a specified element from the set if able.
(d) isEmpty, that determines the emptyness of the set.
(e) getCurrentSize, that returns the number of elements currently in the set.
(f) clear, that removes all elements from the set.
(g) contains, that determines whether a specified element is in the set.
(h) union, that returns a set with all of the elements of this set, and the specified set.
(i) intersection, that returns a set with all of the common elements in this set, and the specified
set.
(j) difference, that returns a set with all of the elements in this set, that are not in the specified
set.
2. (10%) Provide comments for the interface as necessary being sure to document:
(a) the expected behavior of each method.
(b) the return types, and expected return values (if any).
(c) the conditions for success/failure, and expected handling of such (if any).
(d) anything else of importance in your design choices.
3. (40%) Write a class called ArraySet that implements the SetInterface interface. This class should
include the following:
(a) an array to hold the set elements (use an array of Objects).
(b) implementations for all of the interface methods.
(c) a toString method for displaying the contents of the set.
4. (10%) Provide comments for the class as necessary being sure to document:
(a) how you chose to add elements to the array.
(b) how you chose to remove elements from the array.
(c) how you chose to track the size of the set.
(d) anything else of importance in your implementation choices.
5. (15%) Write a main method in a file called SetTest.java. Your main method should test your
implementation thoroughly. Be sure to document what you are testing at each point.
Assignment 4 Submission Submit on Blackboard:
1. SetInterface.java
2. ArraySet.java
3. SetTest.java
Required Each submitted file should include your name and a statement that this is your own work. This
should appear as a comment at the beginning of any code file.