Assignment 2
Due Date : 2/6 @ 11:59pm
Instructions
Each of you should have a repository in CCIS’s GitHub with the name
assignment2-ccisLogin
. Use this repository
and add all your work there. In order to clone the repositories
from CCIS GitHub to your machine (or watch this video video instructions):
-
Sign in to GitHub.
-
On your CCIS GitHub home page your Github Handle should appear on the left as a button/drop down menu. Click that button and from the drop down menu select
cs8674sp15-seattle
. The CCIS GitHub page will then navigate to the class' web page and to the contents that is available to you. -
On the right you should be able to see all repositories to which you have been given access. Find the repository whose name matches the pattern
assignment2-ccisLogin
, where ccisLogin is your CCIS login name, e.g,assignment2-john123
, and click on it. -
On the repositories home page look at the bottom right hand corner for a button with the text Clone in Desktop. By clicking on this button your browser will launch the GitHub client that we installed in Lab1 and ask for a location on your drive to store the repository.
If you are not using the GitHub client the clone URL is located above the Clone in Desktop button. Copy the URL and issue the following command on your shell
git clone URL
. - Create a file and save it under the folder on your drive that you selected in the preceding step.
Remember to push your changes to the CCIS GitHub repository often.
Rules
-
You are not allowed to use any JDK APIs other than
java.lang
. - You are not allowed to use Java arrays.
- You are not allowed to use Java lists of any kind.
- For any Java class that contains methods you are expected to provide tests using JUnit.
- For any Java class you are expected to provide valid Javadoc documentation. This means that running Javadoc on your your source code should successfully compile and generate documentation in HTML.
- For any images, e.g., for Class Diagrams, you are expected to provide a PDF version of the image.
Problem 1
All Java source code that is part of your solution to this problem must reside inside a java package with the name
edu.neu.ccs.cs8674.sp15.seattle.assignment2.problem1
You are asked to provide the design and implementation in Java for a Set, as in the mathematical notion of a set. Here is the specification given to you describing all the operations on Set. The specification uses
-
{}
to denote the empty set, -
{1,2,3}
to denote the set with the elements1
,2
,3
. -
∪ to denote union of two sets, i.e.,
a ∪ b
.
Operation | Specification | Comments |
---|---|---|
EmptySet(): Set
|
EmptySet() = {} |
Creates an empty set. |
isEmpty() : boolean
|
{}.isEmpty() = true {1,2,...}.isEmpty() = false |
|
add(Integer n) : Set
|
{}.add(n) = {n} aSet.add(n) = aSet, if aSet.contains(n) = true aSet.add(n) = {n} ∪ aSet, if aSet.contains(n) = false |
|
contains(Integer n) : boolean
|
{}.contains(n) = false aSet.contains(n) = true, if n ∈ aSet aSet.add(n) = false, if m ∉ aSet |
|
size() : Integer
|
{}.size() = 0 aSet.size() = n, where |aSet| = n |
|
You are also required to provide the following methods for Sets
-
equals(Object o)
should returntrue
if and only if the two sets have the same number of elements and for each element inthis
the same element exists ino
and for each element ino
also exists inthis
. -
hashCode()
ensure that your implementation ofhashCode()
andequals()
satisfies the contracts for both methods.
Problem 2
All Java source code that is part of your solution to this problem must reside inside a java package with the name
edu.neu.ccs.cs8674.sp15.seattle.assignment2.problem2
You are asked to provide the design and implementation
in Java of a Bag. A Bag is a container for a
group of data, in
our case a Bag can hold String
s. A Bag
can contain duplicates. The elements of a Bag have no
order. Here is the specification given to you describing
all operations on Bags. The specification uses
-
[]
to denote an empty Bag -
[a,b,s]
to denote a bag with three stringsa
b
,s
. The order of the elements does not matter, e.g.,[a,b,c]
is the same Bag as[b,c,a]
and[c,a,b]
etc., -
++
to denote the addition of an element in a Bag, e.g.,b ++ [a,b] = [a,b,b]
-
|aBag|
to denote the number of elements inaBag
.
Operation | Specification | Comments |
---|---|---|
EmptyBag() : Bag
|
EmptyBag() = [] |
Creates an empty bag. |
isEmpty() : boolean
|
[].isEmpty() = true aBag.isEmpty() = false, if aBag ≠ [] |
|
size() : Integer
|
[].size() = 0 aBag.size() = n, where |aBag| = n |
|
add(String s) : Bag
|
[].add(s) = [s] aBag.add(s) = anotherBag, where anotherBag = s ++ aBag |
|
contains(String s) : boolean
|
[].contains(s) = false aBag.contains(s) = true, if aBag = s ++ anotherBag aBag.contains(s) = anotherBag.contains(s), if aBag = x ++ anotherBag, and, x ≠ s |
|
You are also required to provide the following methods for Bags
-
equals(Object o)
that returnstrue
if the two bags have the same exact elements; exactly the sameString
and exactly the same number of times in the bag (if there are duplicates). Remember that the order of elements in the bag does not matter. -
hashCode()
ensure that your implementation ofhashCode()
andequals()
satisfies the contracts for both methods.
Now that you have completed your implementation of Bag, your users would like you to provide the design and Java implementation of a Bounded Bag. A Bounded Bag is very similar to a normal Bag but a Bounded Bag has a maximum number of elements that it can hold. We call this maximum the Bag's capacity. Here is the specification of Bounded Bag
Operation | Specification | Comments |
---|---|---|
EmptyBoundedBag(Integer max) : BoundedBag
|
EmptyBoundedBag(n) = [] |
Creates an empty bounded bag that can hold at most n elements.
|
isEmpty() : boolean
|
Same as Bag's specification for this method. |
Same as Bag's comments for this method. |
size() : Integer
|
Same as Bag's specification for this method. |
Same as Bag's comments for this method. |
add(String s) : Bag
|
aBBag.add(s) = anotherBBag, if aBBag.size() < max and anotherBBag = s ++ aBBag aBBag.add(s) = error, if aBBag.size() ≥ max |
|
contains(String s) : boolean
|
Same as Bag's specification for this method. |
Same as Bag's comments for this method. |
isFull() : boolean
|
aBBag.isFull() = true, if aBBag.size() = capacity aBBag.isFull() = false, if aBBag.size() < capacity |
|
You are also required to provide implementations for the methods equals(Object o)
and
hashCode()
. The requirements for these two methods are the same as those for Bag.
Problem 3
All Java source code that is part of your solution to this problem must reside inside a java package with the name
edu.neu.ccs.cs8674.sp15.seattle.assignment2.problem3
One of your team mates would like your help with one of his projects. He was given the following specification for a Queue and is asking you to provide a design and Java implementation. This Queue holds data in a first in first out (FIFO) order, thus the order by which the elements are added into the Queue matters. The specification uses
-
[| |]
to denote an empty Queue. -
[|a,b,s|]
to denote a queue with three integersa
b
,s
. -
| aQueue |
to denote the number of elements inaQueue
.
Operation | Specification | Comments |
---|---|---|
EmptyQueue() : Queue
|
EmptyQueue() = [| |] |
Creates an empty queue. |
isEmpty() : boolean
|
[| |].isEmpty() = true aQueue.isEmpty() = false if aQueue ≠ [| |] |
|
size() : Integer
|
[| |].size() = 0 aQueue.size() = n where |aQueue| = n |
|
add(Integer s) : Queue
|
[| |].add(n) = [| n |] [|x,y,...|].add(n) = [|n,x,y,...|] |
|
contains(Integer x) : boolean
|
[| |].contains(x) = false aQueue.contains(x) = true if aQueue = [| x,a,b,... |] aQueue.contains(x) = [|a,b,...|].contains(x) if aQueue = [| s,a,b,... |] and s ≠ x |
|
pop() : Queue
|
[| |].pop() = error [| x |].pop() = [| |] [| x,y,...,w,z |].pop() = [| x,y,...,w |] |
|
peek(): Integer
|
[| |].peek() = error [| x,y,...,w |].peek() = w |
|
You are also required to provide implementations for the
methods equals(Object o)
and hashCode()
.
For equals()
two queues are equal if and only
if they have the same exact elements and in the same order
(identical), i.e., [| 1,2,3,1,2,3 |]
is not
equal with [| 1,2,3,1,2, |]
or [|
2,1,3,1,2,3 |]
.