Create a class for a set of integers, similar to IntLinkedBag.java (given below), except that only one copy of a value can be stored (no duplicates). You may directly copy any appropriate code from IntLinkedBag.java. Include the following methods, and answer the given questions:

a. A main method creates two sets and demonstrates all of the methods below.

b. Modify the add method such that it does not add duplicate elements. Use the countOccurrences method to determine whether the element already exists.

QUESTION: What is the Big-O time for this entire algorithm, including the operations for countOccurrences? Briefly explain your answer.

c. A public print method prints all of the values in the set in the order in which they are stored (index #0 is first). Below is an example of calling print for a set with the values {3, 1, 0, 2}:

3 1 0 2

QUESTION: What is the Big-O time for this method? Briefly explain your answer.

d. A private get method receives an index for an item in the set and returns that element. For a set with the values 3, 1, 0, and 2, calling get(2) would return 2. Throw RuntimeException if the index is invalid (see the clone method in IntArrayBag.java for an example).

QUESTION: What is the Big-O time for this method? Briefly explain your answer.

e. A public static intersection method receives two sets and returns a new set that is the intersection (all common elements). Note that this is similar to the format of the union method in the sample program. For your algorithm, use the get method from above to get elements from one set and the countOccurrences method to determine whether that element is in the second set. For example, the intersection sets {3, 1, 0, 2} and {1, 3, 4} would consist of the values 1 and 3 (in any order). If there are no common elements, the returned set should be empty (size of zero).

QUESTION: What is the Big-O time for this entire algorithm, including the operations for get and countOccurrences? Briefly explain your answer.

IntLinkedBag.java:

public class IntLinkedBag implements Cloneable { private IntNode head; private int manyNodes; public IntLinkedBag( ) { head = null; manyNodes = 0; } public void add(int element) { head = new IntNode(element, head); manyNodes++; } public void addAll(IntLinkedBag addend) { IntNode[ ] copyInfo; // The precondition indicates that addend is not null. If it is null,  // then a NullPointerException is thrown here.  if (addend.manyNodes > 0) { copyInfo = IntNode.listCopyWithTail(addend.head); copyInfo[1].setLink(head); // Link the tail of copy to my own head...  head = copyInfo[0]; // and set my own head to the head of the copy.  manyNodes += addend.manyNodes; } } public void addMany(int... elements) { // Activate the ordinary add method for each integer in the  // elements array.  for (int i : elements) add(i); } public Object clone( ) { // Clone a nIntLinkedBag object.  IntLinkedBag answer; try  { answer = (IntLinkedBag) super.clone( ); } catch (CloneNotSupportedException e) { // This exception should not occur. But if it does, it would probably  // indicate a programming error that made super.clone unavailable.  // The most common error would be forgetting the "Implements Cloneable"  // clause at the start of this class.  throw new RuntimeException ("This class does not implement Cloneable"); } answer.head = IntNode.listCopy(head); return answer; } public int countOccurrences(int target) { int answer; IntNode cursor; answer = 0; cursor = IntNode.listSearch(head, target); while (cursor != null) { // Each time that cursor is not null, we have another occurrence of  // target, so we add one to answer and then move cursor to the next  // occurrence of the target.  answer++; cursor = cursor.getLink( ); cursor = IntNode.listSearch(cursor, target); } return answer; } public int grab( ) { int i; IntNode cursor; if (manyNodes == 0) throw new IllegalStateException("Bag size is zero"); i = (int)(Math.random( ) * manyNodes) + 1; cursor = IntNode.listPosition(head, i); return cursor.getData( ); } public boolean remove(int target) { IntNode targetNode; // The node that contains the target   targetNode = IntNode.listSearch(head, target); if (targetNode == null) // The target was not found, so nothing is removed.  return false; else  { // The target was found at targetNode. So copy the head data to targetNode  // and then remove the extra copy of the head data.  targetNode.setData(head.getData( )); head = head.getLink( ); manyNodes--; return true; } } public int size( ) { return manyNodes; } public static IntLinkedBag union(IntLinkedBag b1, IntLinkedBag b2) { // The precondition requires that neither b1 nor b2 is null.  // If one of them is null, then addAll will throw a NullPointerException.  IntLinkedBag answer = new IntLinkedBag( ); answer.addAll(b1); answer.addAll(b2); return answer; } }