Assignment 5: Maps, Sets, MultiSets

This is assignment is to be completed and submitted individually. You may not work with anyone else.

Due: Tuesday, April 2, 11:59:59 PM EST.

Download the assignment project

For this assignment, download the following zip file: Assign5.zip. Save the file somewhere on your computer and unzip it. This will create a directory called Assign5 with an IntelliJ project inside. It contains all the libraries you will need and some code to get you started.

Open IntelliJ and select "Open". Navigate to the Assign5 directory and select it.

This should open up the project and place you inside the Assign5.java file. The first thing you should do is edit the authors line (which should be selected when you open the project) to be your and your partner’s directory ID.

The project has a "Test" configuration in the top right corner. Press the "Run" (green triangle) button to run the test suite. The test suite comes with a few tests to get you started, but running the tests will result in an null pointer error because it is missing implementations.

1 Implementing a Library of Data structures

For this assignment, you must implement a library of data structures for maps, sets, and multisets.

In the code given to you, you will find interfaces for all of the data structures (plus lists, which are already implemented). You must implement classes that correctly implement all of these operations and write a test suite to validate your design.

Maps represent finite functions between keys and an associated value (similar to dictionaries on the midterm). The idea of a map is that keys are unique, values may or may not be. Two maps are the same if they map the same keys to the same values. If you add a new key-value to a map that already has an association for that key, the old one effectively is lost. The order of key-values in a map is unspecified.

Sets represent collections of unique elements. Two sets are the same if they contain the same elements. Adding an element to a set that already contains that element has no observable effect; it results in the same set as you started with. The order of elements in a set in unspecified.

Multisets represent collections of elements, but without the restriction that the elements are unique. Adding an element to a multiset that already contains that element result is an a multiset containing one more instance of that element. Two multi-sets are the same when the have the same elements, i.e. the same elements including the same number of duplicates of each unique element). The order of elements in a multi-set is unspecified.

You may add signatures for methods you need to implement the library, but YOU MUST NOT CHANGE ANY OF THE GIVEN SIGNATURES. Your code should be well-designed and abstracted to avoid code duplication.

Submission

Use submit.cs.umd.edu to submit your solution to the problems. You should create a zip file called Assign5.zip that contains the IntelliJ project containing your solutions.