CSE 17
In this assignment, we will explore recursion while developing a simple data structure to
represent the mathematical concept of a set. You should not use java.util.Set nor any of its
descendants when writing this program. The UML for your class is given below. You may create
any additional private methods that you see necessary.
RecursiveSet This class represents a collection of unique elements. Some
of its operations are implemented using recursion. This
class should implement the Cloneable interface.
-members: ArrayList The elements of the set. Any kind of object can be stored.
By definition, there can be no duplicates in this list.
+RecursiveSet() The constructor. Should initialize the object.
+add(e:Object):void Add an object e to the set. If e is already in the set (as
determined by its equals method), the operation is ignored.
+hasElement(e:Object):boolean Returns true if e is in the set, otherwise returns false.
+get(i: int):Object Returns the element at index i in the set.
+size():int Returns the number of elements in the set.
+toString(): String Returns a string of the form { e1, e2, ... , en} where each ei is
the toString of one element of the set.
+clone(): Object Makes a copy of the set and returns it. It is important that
this copy includes a clone of members. Otherwise, changes
to the clone may change the original. Hint: The preferred
way to implement clone is to call the clone method of the
superclass to create a copy of the object, and then set all
mutable instance variables of this object by calling clone
methods on their objects. You will have to declare or catch
the CloneNotSupportedException.
+intersect(set2:RecursiveSet):RecursiveSet
Uses recursion to calculate the intersection of this set with
set2. It should not modify either set, and should not
excessively create new sets. You should develop a recursive
helper method to solve this problem.
+union(set2:RecursiveSet):RecursiveSet
Uses recursion to calculate the union of this set with set2. It
should not modify either set, and should not excessively
create new sets. You should develop a recursive helper
method to solve this problem.
+equals(o: Object): boolean Returns true if o is equivalent to the current set. Remember,
two sets are equal if they have exactly the same elements.
Order, however, is inconsequential. e.g., {a,b} = {b,a}. CSE 17, Fall 2014
2
Note, it is essential that the names and types of all data fields and the names, return types and
parameter lists of all methods appear exactly as described. Otherwise, you will lose points on the
assignment. Although we will test your class with various combinations of method invocations,
as a basic test of your program, you must provide a main method that does the following:
• Create two sets A={“a”,”b”,”c”} and B={“c”,”d”,”b”}, where “a”,”b”,”c”, and “d” are
Strings. Print out the sets.
• Test if “b”∈A and if “d”∈A and print the results. Recall, ∈ is the set membership
operator.
• Let C = A ∩ B and D = B ∪ A and print the sets. Recall, ∩ stands for intersection, which
means the set of elements in common between the two sets, and ∪ stands for union which
means the set of elements that are in at least one of the two sets.
• Show that A and B are unchanged by these operations.
• Create a set E = {“c”, “b”} and print it.
• Test if E=C, E=A, or D=A and print the results of all three tests.
• Create two sets N1={1,3,5,7} and N2={2,4,8}. Here each number should be an Integer.
• Print out N1 ∩ N2 and N1 ∪ N2.
• Create a set MA that consists of the sets A and E from above: i.e., it is a set of sets:
{{“a”,”b”,”c”}, {“c”, “b”}}. Print it.
• Create a set MB that consists of the sets B, C and D from above: i.e., {{{“c”,”d”,”b”},
{“b”, “c”}, {“c”, “d”, “b”, “a”}}. Print it.
• Finally, Print out MA ∪ MB and MA ∩ MB.
The output should look something like the following, although the exact ordering of the elements
in the sets will not matter.
> java RecursiveSet
A = {a, b, c}
B = {c, d, b}
b is in A? true
d is in A? false
C = A intersect B = {b, c}
D = B union A = {c, d, b, a}
A = {a, b, c}
B = {c, d, b}
E = {c, b}
E = C? true
E = A? false
D = A? false
N1 = {1, 3, 5, 7}
N2 = {2, 4, 8}
N1 intersect N2 = {}
N1 union N2 = {1, 3, 5, 7, 8, 4, 2}
MA = {{a, b, c}, {c, b}}
MB = {{c, d, b}, {b, c}, {c, d, b, a}}
MA union MB = {{a, b, c}, {c, b}, {c, d, b, a}, {c, d, b}}
MA intersect MB = {{b, c}}
> CSE 17, Fall 2014
3
At a minimum provide a Javadoc comment explaining what each method does, and another one
that summarizes the class. Include additional comments for lines that are especially complicated.
At the top of the program include a comment with the following form:
/*
CSE 17
Your name
Your user id
[with assistance from tutor name (tutor e-mail address)] if tutor used
Homework #5 DEADLINE: November 4, 2014
Program: Recursive Sets
*/
Once the program functions properly, use SSH to connect to your account on
sunlab.cse.lehigh.edu. The name of your account is the same as your network server id. Create a
subdirectory of cse017.144 called Hw5, and transfer the file RecursiveSet.java to this
subdirectory (~/cse017.144/Hw5/ where ~ represents your home directory). Be very careful to
ensure that you have spelled the directories correctly and used the correct case for all letters in
directory names. At the time of the deadline, an email will be sent to you either confirming that
your homework has been collected or stating that it was not collected.