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.