Home Page > > Details

CMPSCI 187 AssignmentHelp With , Java Course Assignment,Java Programming AssignmentDebug Statistics,,| Haskell Programming

CMPSCI 187 (Sec 02) / Fall 2020
Implementing Sets Using Linked Lists
CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists
Contents
Overview 3
Learning Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
General Information [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Problem 1 4
Review of the Concept of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Immutability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Iterators and the Iterable Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Import Project into Eclipse [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Starter Code and Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Useful Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Export and Submit [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Page 2 of 7
CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists
Overview
In this assignment you will build a class to represent a set; as in the mathematical concept of a set, a collection that has
no duplicates. The class will be immutable (more later), generic, and will use Iterators. It will be implemented
with linked lists. We will give you (in the support directory) the Set interface, and the LinkedNode class, and
(in the src directory) skeletons for the LinkedSet and LinkedNodeIterator classes which you will complete.
You will be starting from initial code provided to you, and adding to and modifying it. You should NOT create any
new classes or interfaces.
Learning Goals
• Continue to exercise your understanding of linked lists.
• Introduce the concept of generics and iterators.
• Show ability to write a class that implements a given interface, and read specifications in a Java interface.
• Continue to practice using JUnit tests and Java debugging tools.
Note: sections marked [Common] below are shared among all projects. We include them here for the completeness of
the description, but they present the same information across all projects.
General Information [Common]
Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty.
Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what
constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies
in detail and by submitting this project you have provided your virtual signature in agreement with these policies.
• For some projects, it may be useful for you to write additional java files. Any java file you write MUST be
placed in the provided src directory of your Eclipse project.
• When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause
the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!
In the test directory, we provide several JUnit tests that we refer to as the public tests. Each test checks a certain
aspect of your program, such as does it generate the expected output for a given input. We recommend you run the
tests often and use them as starting points to test your project. In addition, some of the java files come with their own
main functions. You can run them as Java applications to interact with the project.
Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your
project. These tests are hidden from you. We recommend that you actively think about your own test (by adding new
@Test) cases to your public test files to help you debug the program. In particular, you should consider:
• Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many
methods only accept arguments that are in a particular range.
• Does your code handle cases such as when an array or list is empty, or has reached full capacity?
More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out
the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.
Page 3 of 7
CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists
Problem 1
Review of the Concept of Sets
(This is just a simple review. To find out more, visit http://en.wikipedia.org/wiki/Set_(mathematics).)
Mathematically, a set Q represents a collection of distinct elements. For example:
Q = {a, b, c, d, e}
is a set with five elements: a, b, c, d, and e. Note that the elements are unordered, so the following sets are the same:
{a, b, c, d, e} = {a, e, c, b, d} = {c, b, e, d, a} = . . .
There are various operations on sets, such as the union, intersection, difference; as well as tests for membership, for
inclusion, and for equality. These are illustrated below:
Given:
A = {a, b, c, d, e}, B = {c, a}, C = {3, 1, 4, 5, 9}
then
a ∈ A membership (i.e. a is an element of A)
B ⊂ A subset (i.e. B is a subset of A)
A ⊃ B A is a superset of B
B ∪ C = {3, 1, c, a, 4, 9, 5} set union, include all elements from both sets
A ∪ A = A sets don’t have duplicates
A ∩ B = B ∩ A = B set intersection, those elements that are elements of both sets
A ∩ C = ∅ set intersection with no common elements gives the empty set
A − B = {b, d, e} set difference, those elements in A but not in B
We will be implementing all of these operations on our sets.
Immutability
Some classes represent immutable objects, i.e., objects whose state cannot be changed. You are already familiar with
at least one such class, the String class. Instances of that class cannot be changed in any way. If you look carefully
you will notice that any String method that could be construed as changing the String actually returns a new
String; the original is unchanged. Other immutable classes include Boolean, Integer, and Float. Immutable
objects have some nice properties, such as they are much safer to use in a multi-threaded environment.
The Set interface described in this project specifies an immutable class. Note that none of the methods allows one
to change an instance, they only return new instances. Your implementation of the Set interface must maintain that
immutability. Once an instance is created it never changes.
Generics
In class we covered generics, which provides a convenient way to create a family of classes by parametrizing the
data type. For example, you have learned to define LLStringNode and LLIntegerNode, which are linked list
nodes that store string and integer data respectively. What if you need to define other types of linked list nodes that
store other types of data, including custom data types such as Apple and Dog? Generics allows you to define the
entire family of such classes by replacing the specific data types with type variables. Figure 1 shows three different
classes, LLStringNode, LLDogNode, and LLNode, the last being a generic class. For simplicity we omitted
the method bodies to highlight the differences in data types. Figure 2 shows typical uses of the LLNode class.
Problem 1 continued on next page. . . Page 4 of 7
CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)
1 class LLStringNode {
2 String info;
3 LLStringNode link;
4
5 LLStringNode(String s){
6 info = s;
7 link = null;
8 }
9
10 String getInfo();
11
12 LLStringNode getLink();
13
14 void setInfo(String info);
15
16 void setLink(
17 LLStringNode link);
18 }
class LLDogNode {
Dog info;
LLDogNode link;
LLDogNode(Dog d){
info = d;
link = null;
}
Dog getInfo();
LLDogNode getLink();
void setInfo(Dog info);
void setLink(
LLDogNode link);
}
class LLNode {
T info;
LLNode link;
LLNode(T data) {
info = data;
link = null;
}
T getInfo();
LLNode getLink();
void setInfo(T info);
void setLink(
LLNode link);
}
Figure 1: Definitions of LLStringNode, LLDogNode, and LLNode classes.
1 LLNode dogNode = new LLNode(dog1);
2 dogNode.setInfo(dog2);
3 dogNode.setLink(new LLNode(dog3));
4 Dog dog = dogNode.getInfo(); // dog == dog2
5
6 LLNode sNode = new LLNode("abc");
7 sNode.setInfo("xyz");
8 sNode.setLink(new LLNode("xyz"));
9 String s = sNode.getInfo(); // s == "xyz"
Figure 2: Using the LLNode class.
The major change is the inclusion of in the LLNode definition. This declares that LLNode is generic, and
has a type variable named T. When you use the LLNode class, for instance by using LLNode, you
are specifying that you want a version of LLNode created by replacing the type variable with a specific data type
Strings. Thus LLNode together becomes the name of the class. It is perfectly possible, as Figure 2
shows, to have several different instantiations of the generic class.
Iterators and the Iterable Interface
In class we have also covered the Iterator and Iterable interfaces. An iterator is a object that allows
you to visit the elements of some collection one-by-one. For example, if array is an instance of a class that
implements the Iterable interface, you can use the following code to visit every element in it one-by-one:
1 Iterator iter = array.iterator();
2 while (iter.hasNext()) {
3 Type variable = iter.next();
4 ...
5 }
You can make it even simpler by using the following special for loop:
1 for (Type variable : array) { ... }
The Iterable interface specifies only one method, the Iterator iterator() method, which returns
an iterator object for the collection. This iterator object must belong to a class that implements the Iterator
Problem 1 continued on next page. . . Page 5 of 7
CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)
interface, which requires implementing three methods: boolean hasNext(), T next(), and void remove
(). For our purposes we are going to ignore the remove() method. The definition you are given will simply throw an
UnsupportedOperationException to indicate that this operation is not supported (because our set represents
an immutable collection).
Import Project into Eclipse [Common]
Begin by downloading the starter project and importing it into your workspace. It is very important that you do not
rename this project as its name is used during the autograding process. If the project is renamed, your assignment will
not be graded, and you will receive a zero.
The imported project may have some compilation errors, but these should not prevent you from getting started. Specifically,
we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests.
After completing your code, the compilation errors should be gone.
The project should normally contain the following root items:
src This is the source folder where all code you are submitting must go. You can change anything you want in this
folder (unless otherwise specified), you can add new files, etc.
support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You
must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder
to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the
menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions
check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive
changes”, and you should click on the “Yes” button.
test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.
JUnit 4 A library that is used to run the test programs.
JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.
If you are missing any of the above or if errors are present in the project (other than as specifically described below),
seek help immediately so you can get started on the project right away.
Starter Code and Tests
Requirements: for this project, you must implement linked list on your own. You may NOT use Java array of any
type, nor any Java class that implements the Collection interface (e.g. ArrayList, Vector etc.). The list of these
classes is included in the API documentation, available at: https://docs.oracle.com/javase/8/docs/
api/java/util/Collection.html. The autograder will assign you a grade of 0 if you use any of them. Also,
do NOT create new files as the autograder will ignore any new file you create.
In the support/sets directory you will find Set.java, which defines the Set interface. Read that file closely, as
it defines exactly what your implementation must do. You will also find LinkedNode.java, which defines the
LinkedNode class. It is an immutable, generic class, and is a generalization of the LLxxxNode classes you have
seen before. As with all files in the support directory you must NOT modify either of these files.
In the src directory you will find two files: LinkedSet.java and LinkedNodeIterator.java. Places that require
your work are clearly marked by //TODO. Note that the starter code you receive is NOT a working implementation.
Right at start you may see errors. You can run the tests, but most of which will fail. You must complete the implementation
as required in order to pass the tests.
Problem 1 continued on next page. . . Page 6 of 7
CMPSCI 187 (Sec 02) / Fall 2020 Implementing Sets Using Linked Lists Problem 1 (continued)
The version of LinkedSet we have given you has one attribute, head, which is intended to be the head of
a linked list of elements in the set. It also has three constructors; two public, one which creates an empty set, and
the other of which creates a set containing a single element; and one private which creates a set from a linked list
of LinkedNodes. This last constructor is the one that you will call from your methods to create the new
LinkedSet object to be returned. There are ten methods that you will need to supply implementations for. We
suggest that you start by implementing the iterator method; because many of the other methods can use it to good
effect; for an example see the hashCode() method.
To implement the iterator method you will need to finish the LinkedNodeIterator class. This class
has two methods you will need to complete, hasNext() and next(). You will also need to choose appropriate
data variables and build an appropriate constructor. If you remember that you are iterating over a linked list of
LinkedNodes you should not have too much difficulty with this.
Useful Tips
• Read the Set interface in Set.java carefully, as it specifies exactly what each method is supposed to do
• An appropriate parameter for the constructor of the LinkedNodeIterator class is a reference to the first
LinkedNode in the list;
• Once you have completed LinkedNodeIterator and the iterator() method, you can use it (in the
form of the special for loop) everywhere appropriate, such as the size, contains, isSubset, union,
intersect, subtract methods.
• Similarly, think about how to maximally reuse methods you’ve already written when implementing new method.
For example, you can easily implement isSuperset by using isSubset.
Testing
We provide public JUnit tests (in LinkedSetPublicTest.java) you should use to test your implementation. Feel
free to write additional tests yourself to make sure your code runs as expected. For full credit, you must correctly
implement each method in LinkedSet.java and LinkedNodeIterator.java. Make sure that you have done
everything that is clearly marked by //TODO in those files.
Export and Submit [Common]
When you have completed this project, you should export an archive file containing the entire Java project. To do this,
click on the sets-student project in the package explorer. Then choose “File → Export” from the menu. In the
window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination for the output
file. Be sure that the project is named sets-student (otherwise you may be exporting the wrong project!). Save
the exported file with the zip extension.
Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course
website and/or documentation explaining how to use the online autograder. If you have any questions please be
prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like
the autograder failed and not your project, please let the instructors know.

Contact Us - Email:99515681@qq.com    WeChat:codinghelp
Programming Assignment Help!