CSci 2101 Problem set 5:

Due Friday, March 24th at 11:59pm (by e-mail)

38 points

Problem 1 (8 points): equals method for OurLinkedList

Implement a method equals in OurLinkedList class that takes an object and returns true if that object is an instance of OurLinkedList and has the exact same elements (as given by calling equals method on the respective elements) in the same order and false otherwise. If two lists are of different size, the method returns false. You may assume that your list does not contain null elements.

You can use your own OurLinkedList implementation, or just the starting code here since you only need an add method to test equals.

Test your method well and submit all of your testing code.

Problem 2 (30 points): implementing a Set class

This problem is loosely based on Problem 14 on p. 239 and asks you to implement and test a class Set<E>. A set should work according to the mathematical definition of a set. A few requirements and details:

• A set should act as if each element in it appears once, i.e. if a set has an element 5, adding another 5 shouldn't change the behaviour of the set in any way. Two elements are considered the same if equals returns true for them.
• The internal storage of the elements is up to you, and you may use any of the Java classes except for predefined set classes.
• There should be no limit on the number of elements in a set.
• A set should be generic Set<E>, where E is the type of the elements in the set. For instance, you would be able to create Set<String> or Set<Integer>. All methods that take or return elements should take or return objects of type E.
• There must be a constructor that creates an empty set. Feel free to add other contstructors if you find them useful.
• You need to implement and test the following methods:
  1. isEmpty() that returns true if this set is empty and false otherwise,
  2. size() that returns the size of the set (the number of elements)
  3. add(E element) adds an element to a set (but be careful not to add elements that are already in the set).
  4. toString returns a string representation of a Set.
  5. contains(E element) returns true if an element is present in the set and false otherwise. Use equals to determine if two elements are the same.
  6. A void method union(Set<E> otherSet, Set<E> resultSet) which makes resultSet to be the union of the two sets. If resultSet isn't empty, it is first made empty, and then the elements of the union are added to it.
     The reason the resultSet is being passed in is that it's difficult to create a set of a concrete type (say, Set<String> or Set<Integer>) inside the Set class.
  7. A void method intersection(Set<E> otherSet, Set<E> resultSet) which makes resultSet to be the intersection of the two sets. If resultSet isn't empty, it is first made empty, and then the elements of the union are added to it.
  8. removeAll() removes all elements from the set.

How to submit

Submit your Java file(s) to me by e-mail. The subject must be Problem Set N, where N is the problem set number. If working in a group, CC your group partner.

CSci 2101 course web site.