[SOLVED] CS314 Programming Assignment 8: 

Description

The purposes of this assignment are:

1. to practice implementing data structures
2. to use ArrayLists and Iterators
3. to implement sorting and searching algorithms by modifying pre-existing algorithms.
4. To develop code that makes use of encapsulation, inheritance, polymorphism, interfaces, and abstract classes.

---

Summary: Implement three classes: AbstractSet, UnsortedSet, and SortedSet. Recall that the elements of an a set have no definite order and duplicate items are not allowed. Link to the Wikipedia entry on Sets.

For more details on how to complete the assignment see the description of classes and files below as well as the tips section.

You may adapt the code for fast sorting (quicksort, mergesort) from the slides for use in your SortedSet class.

Very Important: On this assignment you must use an ArrayList as your internal storage container in the UnsortedSet and SortedSet classes.

Very Important: On this assignment you may not use any of the sorting or binary searching methods from the Java standard library. This includes, but is not limited to, the sorting and searching methods in the Arrays and Collections classes and the public void sort(Comparator<? super E> c) method from the ArrayList class. You may use the built in linear search methods such as the ArrayList contains and indexOf methods.

Very Important: For each method you write in UnsortedSet and SortedSet state the Big O of the method in a comment at the top of the method. To answer some of these questions you have to determine the Big O of methods from the ArrayList class. View the ArrayList documentation and think about how we implemented methods in our simple array-based list class (GenericList) to determine the Big O of methods from ArrayList. Use Piazza to discuss what you think the Big O of methods from ArrayList are.

Files

	File	Responsibility
Source Code	ISet.java. Interface for the classes you are developing. Do not alter.	Provided by me
Source Code	AbstractSet.java. Complete as many methods as possible in this class without any instance variables.	Provided by me and you. (Granted, mostly you.)
Source Code	UnsortedSet.java A set with elements in no particular order.	Provided by me and you. (Granted, mostly you.)
Source Code	SortedSet.java A set with elements in sorted ascending order.	Provided by me and you. (Granted, mostly you.)
Testing	SetTester.java A class with various tests. You must add your own tests as specified below.	Provided by me and you
Utility class	Stopwatch.java. A class for calculating elapsed time when running other code.	Provided by me.
Documentation	ISet.html. Javadoc page for the ISet interface. AbstractSet.html. Brief Javadoc page for the skeleton AbstractSet class. UnsortedSet.html. Brief Javadoc page for the skeleton UnsortedSet class. SortedSet.html. Brief Javadoc page for the skeleton SortedSet class.	Provided by me
Submission	Submit a zip file named a8.zip with your four source code files: AbstractSet.java, UnsortedSet.java, SortedSet.java, and SetTester.java.	Provided by you

Description of Classes and Files:

ISet: The interface for set classes. Do not alter this file.

AbstractSet: Complete a skeletal implementation of the Set interface in the AbstractSet class. 

• AbstractSet may not have any instance variables. Implement as many methods as you can in terms of other methods, regardless of efficiency. You are completing a skeletal implementation of a data structure, much like AbstractCollection or AbstractList in the Java standard library.
• You may not add any methods to AbstractSet that are not part of the ISet interface or the Object class. 
• Do not rely or assume any sub class implementations. In other words AbstractSet shall not make any explicit references to SortedSet, UnsortedSet, or ArrayList. (You will be making implicit references to call some methods such as iterator. If the implicit calls weren’t allowed you couldn’t get anything done in AbstractSet.)
• Do not add any new abstract methods to this class.
• AbstractSet can and should use the iterator method and Iterator objects. Assume the Iterator class implements the remove method.
• Recall you can use other methods besides iterator. For example cointainsAll could make use of contains. .
• Realize there are some methods that cannot be implemented in AbstractSet. Part of this assignment is figuring out which methods can be implemented in AbstractSet and which ones can’t. See the example below.
• Implement one of intersection, union, or difference without adding any new methods to any classes or making reference to UnsortedSet or SortedSet. You may not use the Java Classclass, either. Explain in the comment at the top of SetTester why it would be unwise to implement all three of intersection, union, or difference in the AbstractSet class.
•  For the purposes of this assignment, two objects that are both ISets are equal if they contain the same elements. The status of sorted or unsorted does not matter when checking for equality in AbstractSet. This means it is possible that an UnsortedSet will equal a SortedSet. This convention is used in much of the Java standard library. (Try it with TreeSet a kind of sorted set, and HashSet, a kind of unsorted set.) You shall implement the equals method in the AbstractSet class and will override it in SortedSet.
• I have included a toString method as another example of how to use an iterator. You can use this method to print out your set objects during testing.

UnsortedSet: The provided source file UnsortedSet.java is a skeleton file. This class extends AbstractSet. The elements in this set are not maintained in any particular order from the client’s point of view.  (“A client” is any other class that uses UnsortedSet.) Complete this class.

• Use an ArrayList<E> as the internal storage container. This class maintains the elements of the set it represents in unsorted order.
• Override methods from AbstractSet if you can implement them more efficiently. See the section below on target Big O’s for methods.
• Implement methods you did not implement in AbstractSet.
• For methods that return an ISet such as union, intersection, and difference, return an instance of UnsortedSet if the calling object is an UnsortedSet. (Which it must be to reach the code in UnsortedSet.).

SortedSet: The provided source file SortedSet.java is a skeleton file. This class extends AbstractSet. The elements in this set are maintained in sorted order. To do this the generic data type E (data type parameter) must be a class that implements the Comparable interface. The class header for SortedSet modifies E so that we know all variables of type E in SortedSet will be data types that implement Comparable.

• Use an ArrayList<E> as the internal storage container.
• This class maintains the elements of the set it represents in ascending order. Override methods from AbstractSet if you can implement them more efficiently. See the section below for the target Big O’s of methods.
• Implement methods you did not implemented in AbstractSet.
• Complete a constructor to build a SortedSet out of an ISet<E>.
• The class adds methods to get the min and max values in the SortedSet.
• For methods that return an ISet such as union, intersection, and difference, return an instance of SortedSet.

SetTester: The provided source file SetTester.java contains some tests for the set classes. Delete the provided tests in the version of SetTester your turn in. Add at least 1 test per method per class that implements that method to this file. (In other words if there is a method in AbstractSet and you do not override it in UnsortedSet or SortedSet, you just need to write one test for that method. On the other hand if there is a method in AbstractSet that you do override in both UnsortedSet and SortedSet you have to write code for both versions.) Use the class discussion group to share new test cases.

When writing code that performs sorts and searches you may use code from the class slides as long as you document the source with a comment. For example:

// code for binary search from class slides
... binary search code

You will not be able to use the sorts and searches from the slides “as is”. You will have to adapt them to you classes. Recall your internal storage containers are ArrayLists not arrays.

---

Where to start: It may be difficult to know where to start with this assignment. You don’t want to write all the code and then try and test it. Tracking down the errors can be difficult. You may find it useful to change AbstractSet so that it does not implement ISet. UnsortedSet still extends AbstractSet so you can create instances of UnsortedSet and test the methods you wrote from AbstractSet. Just be sure to go back and have AbstractSet implement ISet.

---

Experiments:

When your classes are completed, run the method largeTest in the SetTester class. This method has you pick a file and then adds all of the words in the file to various Sets. The method uses the SortedSet, the UnsortedSet, the Java HashSet, and Java TreeSet. The time is displayed for the operation to execute. Test this method with a small file at first to ensure it works. Then files (again Project Gutenberg is a good source as is ) of various sizes. Use at least four different files. Report your results in a comment at the top of the SetTester class. Also answer the following questions in that comment: Include the change in file size, number of words, number of distinct words, and time. Express these as a factor (for example 1.5x, 3.7x) compared to the previous file. (Follow the format from the slides on Maps.)

• What do you think the order (Big O) of the two processText methods are for each kind of Set? Assume N = total number of words in a file and M = number of distinct words in the file. M = the size of the set when finished.
• What are the orders (Big O) of your add methods? What do you think the Big O of the HashSet and TreeSet add methods are?
• What are the differences between HashSet and TreeSet when printing out the contents of the Set?

---

Submission: Complete the header in all four class.  Replace <NAME> with your name. Note, you are stating, on your honor, that you did the assignment on your own or with a single partner.

Create a zip file name a8.zip with your SetTester.java, AbstractSet.java, UnsortedSet.java, and SortedSet.java files. The zip file must not contain any directory structure, just the required files.

See this page for instructions on how to create a zip via Eclipse. 

Turn in a8.zip via your Canvas account to programming assignment 8.

• Ensure you files are named SetTester.java, AbstractSet.java, UnsortedSet.java, and SortedSet.java.. Failure to do so will result in points off.

• Ensure SetTester.java, AbstractSet.java, UnsortedSet.java, and SortedSet.java are part of the default package. Do not add a package statement to either file.

• Ensure your zip has no internal directory structure. When the file is unzipped no directories (folders) are created. (Note, the built in unzip feature of some versions of Windows and Apple OS X “help” by adding a directory when you unzip with the same name as the file. The unzip we use on the CS Linux system does not do this. Neither do unzip programs such as 7zip.)

• Ensure you submit the assignment under Programming Assignment 8 in Canvas.

• We will compile and run our tester harness on the CS department Linux machines. To ensure you have no problems (strange imports, package statements) I suggest you move your files to a folder on your CS department account and compile and run them from the command line.

---

Checklist:  Did you remember to:

• review and follow the general assignment requirements?
• work on the assignment with at most, one other person in your same section?
• complete all the required classes?
• NOT add any instance variables to AbstractSet? (Also no references to  UnsortedSet, SortedSet, or ArrayList)s
• implement as many methods as you can in AbstractSet regardless of efficiency?
• override methods from AbstractSet in SortedSet and UnsortedSet if you can create a more efficient version?
• state the Big O of all your methods in UnsortedSet and SortedSet?
• pass the tests in SetTester.java and add your own tests? (Delete the original tests from the version of SetTester you turn in.)
• complete the experiments in the section named Experiments and place your answers in a comment at the top of the SetTester class? Answer the question about implementing intersection, union, and difference in AbstractSet
• fill in the header with your information in SetTester.java, AbstractSet.java, UnsortedSet.java, and SortedSet.java?
• Submit you a8zip to the correct assignment via Canvas by 11 pm, Thursday, April 8.

---

UnsortedSet Target Big Os:

These are the Big O’s you should be able to achieve for the methods in the  UnsortedSet class. If a method is implemented in AbstractSet and it has this Big O then there is no need to override it in UnsortedSet. Assume there are already N elements in this UnsortedSet. For methods with another set assume there are N elements in that set as well.

• add -> O(N)
• addAll -> O(N^2)
• clear -> O(N)
• contains -> O(N)
• containsAll -> O(N^2) Worst case is this set does contain all of the elements of the other set and each set contains N elements.
• difference -> O(N^2)
• equals -> O(N^2) Worst case, assuming the sets are equal.
• intersection -> O(N^2)
• iterator -> O(1). Remember, your internal storage container is an ArrayList and ArrayList already has a method to get an Iterator.
• remove -> O(N)
• size -> O(1)
• union -> O(N^2)

SortedSet Target Big Os:

These are the Big O’s you should be able to achieve for the methods in the  SortedSet class. If a method is implemented in AbstractSet and it has this Big O then there is no need to override it in SortedSet. Assume there are already N elements in this SortedSet. For methods that involve two sets, the calling object and another ISet, these target Big Os apply only if the other set is also a SortedSet. if it is not your target Big O is the same as in the UnsortedSet class. If there is a method where the other set is not a SortedSet you should rely on the Big O targets from UnsortedSet.

• SortedSet(ISet otherSet) -> O(NlogN)
• add -> O(N)
• addAll -> O(N) if other set is also a SortedSet. Use an algorithm like merge from mergesort.
• clear -> O(N) You can do this with a single statement in SortedSet, but the Big O of that statement is O(N).
• contains -> O(logN)
• containsAll -> O(N) if other set is also a SortedSet. Worst case is this set does contain all of the elements of the other set and recall we are assuming the sets both contain N elements.
• difference -> O(N) if other set is also a SortedSet.
• equals -> O(N) Worst case, if other is a SortedSet and assuming the sets are equal.
• intersection -> O(N) if other set is also a SortedSet.
• iterator -> O(1). Remember, your internal storage container is an ArrayList and ArrayList already has a method to get an Iterator.
• remove -> O(N)
• size -> O(1)
• union -> O(N) if other set is also a SortedSet.

Tips: So how can you implement methods in AbstractSet when there isn’t an internal storage container and no instance variables?  By using other methods in the class!

Here is an example. The ISet interface has a method named contains that determines if a given element is in the set. There is also a method named iterator which provides an Iterator object to look at all the items in the set. So in AbstractSet we could do the following:

public boolean contains(E item) {
boolean found = false;
Iterator<E> it = this.iterator(); // get an iterator for this set.
// do a linear search using the iterator object
while (!found && it.hasNext()) {
E temp = it.next();
found = temp.equals(item); // which equals method is getting called?
}
return found;
}

You won’t be able to implement the iterator method in the AbtsractSet class. You need an internal storage container to do that. So you will be calling a method that will be implemented later. Note, the use of a temporary object in the above code is actually unnecessary and the code could be streamlined to this form.

public boolean contains(E item) {
Iterator<E> it = this.iterator(); // get an iterator for this set.
// do a linear search using the iterator object
while (it.hasNext()) {
if (it.next().equals(item)) {
return true; // found it. Done!
}
}
return false; // never found item
}

And there is an even simpler option. ISet extends the Java Iterable interface. This means it has a method that returns an Iterator object. It also means ISets  can be used as the set-expression in enhanced for loops. So the following works as well

public boolean contains(E obj) {
for (E val : this) {
if (val.equals(obj)) {
return true;
}
}
return false;
}

Use whatever form you are most comfortable with.

SortedSet tips:

In the SortedSet class when methods can be faster due to the fact that the data is sorted, you should make them faster. For example consider the contains method:

public boolean contains(E item)

This could be implemented in the AbstractSet class using an Iterator object from the iterator method. The expected run time would be O(N). However, in the SortedSet class this method should be overridden, because it can be accomplished in O(logN) time through a binary search.

There are many methods that have an explicit parameter of type ISet. If that ISet is a SortedSet we can perform some actions more efficiently. For example, the intersection method in SortedSetwill look something like this:

public ISet<E> intersection(ISet<E> otherSet) {
// we know E is a Comparable, but we don't know if
// otherSet is a SortedSet.

// local var of correct type so we only have to cast once
SortedSet<E> otherSortedSet;

// do we need to create a new SortedSet based on otherSet or is otherSet really a SortedSet?
if (!(otherSet instanceof SortedSet<?>))
otherSortedSet = new SortedSet<E>(otherSet); // should be O(NlogN)
else
otherSortedSet = (SortedSet<E>) otherSet;

SortedSet<E> result = new SortedSet<E>();

// fill result with modified merge algorithm, should be O(N)

return result;