• DUE DATE: June 2nd @12:00pm (NOON)

Submission Criteria

Repository Contents

Your repositories must contain only the following

1. pom.xml file and
2. src folder with appropriate sub-folders with your code and test code only.

Code Criteria

1. Your solution for each problem should be in its own package. The package names should follow this naming convention edu.neu.ccs.cs5004.assignmentN.problemM where you replace N with the assignment number and M with the problem number, e.g., all your code for problem 1 for this assignment must be in a package named edu.neu.ccs.]s]s]s5004.assignment3.problem1.
2. Your project should successfully build using maven generating all the default reports.
3. Your Javadoc generation should complete with no errors or warnings.
4. Your Checkstyle report must have no violations.
5. Your JaCoCo report must indicate 75% code coverage per package for "Branches" and "Instructions" or more.
6. Your FindBugs report must have no violations (except for violations categorized as PERFORMANCE or SECURITY, you can ignore those).
7. Your PMD report should have no violations.

Problem 1

You are asked to design a Java program for list of strings. Your implementation must provide for the following operations on lists of strings.

1. isEmpty : to check if the list is empty or not.
2. size : to get the total number of elements in the list.
3. contains : consumes a string and checks if the string is in the list or not.
4. containsAll : consumes another list of string checks that all elements of this list are in the list passed as argument.
5. filterLargerThan : takes the maximum string length and returns a list with all list elements whose length is greater than the maximum length removed.
6. hasDuplicates : check if the list has at least one duplicate element.
7. removeDuplicates : returns the list with all duplicates removed.

Along with your implementation you are also required to provide

1. Templates for all your classes.
2. The UML Class Diagram for your final solution.
3. A sequence diagram for your implementation of removeDuplicates. The diagram should be based on an example of a list with at least 3 elements and at least 1 being a duplicate.

Problem 2

We are asked to extend our Shapes solution to accommodate for composite shapes. A composite shape is a collection of two or more Shapes. Our Shapes (including our new composite shape) must support the following operations

1. moveX : takes the amount of units to move the pin in the X direction. For a composite, all shapes that are part of the composite need to move by the amount provided.
2. moveY : takes the amount of units to move the pin in the Y direction. For a composite, all shapes that are part of the composite need to move by the amount provided.
3. area : returns the area of a shape. For a composite shape this is the sum of all areas of its shapes.
4. perimeter : returns the perimeter of a shape. For a composite shape this is the sum of all perimeters of its shapes.

Along with your implementation you are also required to provide

1. The UML Class diagram for your final solution.
2. A Sequence Diagram for the method moveX on a composite object. The composite object needs to be composed of at least 2 shapes.

Problem 3

You are asked to design a Java program for a list of list of integers that supports the following operations.

1. size : returns the number of list of integers inside this list, e.g., ((), (1), (2 3)) returns 3
2. length : returns the number of total integers inside this list, e.g., ((), (), (2, 3)) returns 2
3. sum : returns the sum of all integers inside this list, e.g., ((), (1), (2 3)) returns 6
4. isEmpty : check if this list is empty, e.g., () returns true, (()) returns false
5. add : takes a list of integers and prepends (adds) it to this list of list of integers
6. removeInteger : takes an integer and removes the first occurrence of this integer in the list
7. removeAllInteger : takes an integer and removes the all occurrence of this integer in the list

• DUE DATE: June 9th @12:00pm (NOON)

Submission Criteria

Repository Contents

Your repositories must contain only the following

1. pom.xml file and
2. src folder with appropriate sub-folders with your code and test code only.

Code Criteria

1. Your solution for each problem should be in its own package. The package names should follow this naming convention edu.neu.ccs.cs5004.assignmentN.problemM where you replace N with the assignment number and M with the problem number, e.g., all your code for problem 1 for this assignment must be in a package named edu.neu.ccs.cs5004.assignment4.problem1.
2. For each problem you should have
   1. Blackbox tests. These should be placed in a Java package that is different than the package that contains your solution's source code.
   2. Whitebox tests. These should be placed in the same Java package as your solution's source code.
3. Your project should successfully build using maven generating all the default reports.
4. Your Javadoc generation should complete with no errors or warnings.
5. Your Checkstyle report must have no violations.
6. Your JaCoCo report must indicate 75% code coverage per package for "Branches" and "Instructions" or more.
7. Your FindBugs report must have no violations (except for violations categorized as PERFORMANCE or SECURITY, you can ignore those).
8. Your PMD report should have no violations.

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.cs5004.assignment4.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 elements 1, 2, 3.
• ∪ to denote union of two sets, i.e., a ∪ b.

emptySet() = {}
                                        

{}.isEmpty()        = true

{1,2,...}.isEmpty() = false 

{}.add(n)   = {n}

aSet.add(n) = aSet,
    if aSet.contains(n) = true

aSet.add(n) = {n} ∪ aSet,
    if aSet.contains(n) = false
                                        

{}.contains(n)   = false

aSet.contains(n) = true,
    if n ∈ aSet

aSet.contains(n)      = false,
    if n ∉ aSet
                                        

{}.remove(x)   = {}
aSet.remove(x) = bSet,
     if aSet.contains(x) == true  
     then aSet = bSet.add(x)

aSet.remove(x) = aSet,
     if aSet.contains(x) == false
                                        

{}.size()   = 0
aSet.size() = n,  
     where |aSet| = n
                                        

You are also required to provide the following methods for Sets

1. equals(Object o) should return true if and only if the two sets have the same number of elements and for each element in this the same element exists in o and for each element in o also exists in this.
2. hashCode() ensure that your implementation of hashCode() and equals() 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.cs5004.assignment4.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 Strings. 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 strings a 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 in aBag.

emptyBag() = []
                                    

[].isEmpty()   = true

aBag.isEmpty() = false,
    if aBag ≠ []

                                    

[].size()   = 0

aBag.size() = n,
    where |aBag| = n

                                    

[].add(s)   = [s]

aBag.add(s) = anotherBag,
    where anotherBag = s ++ aBag
                                      

[].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

1. equals(Object o) that returns true if the two bags have the same exact elements; exactly the same String 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.
2. hashCode() ensure that your implementation of hashCode() and equals() satisfies the contracts for both methods.

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.cs5004.assignment4.problem3

One of your teammates 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 integers a b, s.
• | aQueue | to denote the number of elements in aQueue.

emptyQueue() = [| |]
                                    

[| |].isEmpty()  = true

aQueue.isEmpty() = false
    if aQueue ≠ [| |]
                                    

[| |].size()  = 0

aQueue.size() = n
    where |aQueue| = n
                                    

[| |].add(n)       = [| n |]

[|x,y,...|].add(n) = [|n,x,y,...|]
                                    

[| |].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()             = error

[| x |].pop()           = [| |]

[| x,y,...,w,z |].pop() = [| x,y,...,w |]
                                    

[| |].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 |].

• DUE DATE: June 16th @12:00pm (NOON)

Submission Criteria

Repository Contents

Your repositories must contain only the following

1. pom.xml file and
2. src folder with appropriate sub-folders with your code and test code only.

Code Criteria

1. Your solution for each problem should be in its own package. The package names should follow this naming convention edu.neu.ccs.cs5004.assignmentN.problemM where you replace N with the assignment number and M with the problem number, e.g., all your code for problem 1 for this assignment must be in a package named edu.neu.ccs.cs5004.assignment5.problem1.
2. For each problem you should have
   1. Blackbox tests. These should be placed in a Java package that is different than the package that contains your solution's source code.
   2. Whitebox tests. These should be placed in the same Java package as your solution's source code.
3. Your project should successfully build using maven generating all the default reports.
4. Your Javadoc generation should complete with no errors or warnings.
5. Your Checkstyle report must have no violations.
6. Your JaCoCo report must indicate 75% code coverage per package for "Branches" and "Instructions" or more.
7. Your FindBugs report must have no violations (except for violations categorized as PERFORMANCE or SECURITY, you can ignore those).
8. Your PMD report should have no violations.
9. You cannot use setter methods for this assignment.

Problem 1

Extend your implementation of Set from your previous assignment to include the following operations

1. union(Set s) : Set; calling s1.union(s2) where s1 s2 are both Sets returns a new Set that is the set union of s1 and s2.
2. intersection(Set s) : Set; calling s1.intersection(s2) where s1 s2 are both Sets returns a new Set that is the set intersection of s1 and s2.
3. difference(Set s) : Set; calling s1.difference(s2) where s1 s2 are both Sets returns a new Set that is the set symmetric difference of s1 and s2.
4. subset(Set s) : Boolean; calling s1.subset(s2) where s1 s2 are both Sets returns true if s1 is a subset of s2 and false otherwise.

Problem 2

You are asked to implement a Priority Queue (PQ). Each element of a PQ is made up of

1. a priority; typically an positive integer
2. a value associated with the priority; in our case the value will be a string

The PQ should have the following operations

1. add(Integer priority, String value) : PQ; adds the given value with its associated priority in PQ.
2. peek() : String; returns the value in PQ that has the highest priority. For two positive integers i,j such that i < j then i has a lower priority than j. The PQ remains unchanged. Calling peek() on an empty PQ should signal an error.
3. pop() : PQ; returns the PQ without the element with the highest priority. Calling pop() on an empty PQ should signal an error.
4. isEmpty() : Boolean; returns true if the PQ is empty, returns false otherwise.

Problem 3

Design and implement in Java an Integer Binary Tree (IBT) and an Integer Binary Search Tree (IBST) whose nodes can hold Integer objects.

An IBT is one of

1. empty
2. a leaf that contains an integer value inside the leaf
3. a node that contains
   1. an integer value inside the node
   2. a left subtree that is itself an IBT,
   3. a right subtree that is iteself an IBT

An IBST is similar to an IBT with the following extra restriction

1. every node in an IBST contains
   1. an integer value inside the node
   2. a left subtree that is itself an IBST, and, all the integer values in the left-subtree are smaller than the value of this node
   3. a right subtree that is iteself an IBST, and, all the integer values in the right-subtree are larger than the value of this node.

Your design and implementation should support at a minimum the following operations on a IBT:

• create an empty IBT
• create a leaf for an IBT by providing the integer value to be stored in the leaf
• create a node for an IBT by providing
  1. an integer value to be stored in the node
  2. a left subtree which must be an IBT
  3. a right subtree which must be an IBT
• the ability to check if the tree is the empty tree
• the ability to know if a given Integer is already stored in the IBST inside a node/leaf

Your design and implementation should support at a minimum the following operations on a IBST:

• create an empty IBST
• add a given integer value to an IBST. The operation should return a new IBST that should contain a new node/leaf with the new integer value passed as an argument. Your operation must return a valid IBST. If the integer value provided as argument to add is already in the IBST, then you can return the IBST unchanged.
• the ability to check if the tree is the empty tree
• the ability to return the longest path starting at the root and terminating at a leaf node in the tree as a string, e.g, 3,5,1,2
• the ability to know if a given Integer is already stored in the IBST inside a node/leaf
• add the operation deleteNode to IBST; the operation takes in an Integer, element, and if there is a node/leaf with the value element in the IBST then remove that node/leaf from the IBST and return the new IBST, else if element is not in the IBST return the IBST unchanged. The IBST returned must be a valid IBST with all nodes/leafs connected as a tree (no dead nodes/leafs). Calling deleteNode on an empty IBST should signal an error.
• add the operation mirror to IBST; the operation returns a IBT which is the mirror image of the current IBST. Here is an example

  IBST Example	IBST Example's Mirror Image

Finally you should design the following operation for both IBTs and IBSTs

1. an operation called isBst() that returns true when called on an instance that satisfies the conditions for an IBST, and false otherwise. Calling isBst() on the return values of the operation mirror should return false. Calling isBst() on the return values of the other operations that return an IBST should return true.

NOTE: all IBSTs are IBTs but not all IBTs are IBSTs.