The purpose of this project is to familiarize with the map abstract data type (ADT) and its several implementations. Second, it is to reinforce the concepts of interfaces, inheritance, polymorphism, and the idea of empirical analysis.

In the project files folder you will find the Map.h file as well as several skeleton files. Map.h defines the interfaces for each of the template classes you will be implementing in this project. To complete this project you must implement the following three template classes: • HashMap • TreeMap • SearchTable Each of the above template classes must extend the given abstract Map class. For each of the above classes you must implement the “Big-3” (Copy constructor, overloaded assignment operator, and destructor) in addition to the below requirements. HashMap This class will implement the map ADT by using a hash table. You may use either separate chaining or open addressing to resolve hash collisions. If you choose open addressing, you must use linear probing. If you you use separate chaining you are free to use the ArrayList class or the LinkedList class from project 1. 2 n Put Erase Find Size 1 0 0 0 0 1001 0 0.000999001 0.001998 0 . . . . . . . . . . . . . . . 9001 0 0.0885457 0 0.0433285 Table 1: CSV File Structure TreeMap This class will implement the map ADT by using a binary search tree. The bi- nary search tree can be implemented in a separate file (BinarySearchTree.h). This class will contain a private data member for the binary search tree which is used to implement the methods of TreeMap. SearchTable This class will implement the map ADT by using a sorted search table and the binary search algorithm. A private function Sort for sorting the array using a sorting method of your choice must be implemented, as well as a method Search which implements the binary search algorithm. Once these classes have been implemented, use the [login to view URL] provided file to generate a CSV file of timing results. The timing results for HashMap, TreeMap, and SearchTable will be found in [login to view URL], [login to view URL], and [login to view URL] respectively. The structure for both of the CSV files is shown in Table 1. In the table, the n column denotes the input size and the next four columns give the average run-time in ms of the given operations. Plot these results using software like LATEX, Excel, Matlab, Mathematica, GNU Plot, etc. Given these plots, answer the following questions: 1. What are the big-O run-times of the four Map operations for HashMap? Do your empirical results agree with this? Why or why not? 2. What are the big-O run-times of the four Map operations for TreeMap? 3 Do your empirical results agree with this? Why or why not? 3. What are the big-O run-times of the four Map operations for SearchTable? Do your empirical results agree with this? Why or why not? 4. Draw a class diagram of the classes in this project. Label the inheri- tance relationships as either being has-a or is-a. Deliverables These are the following files required for this assignment: 1. HashMap.h 2. [login to view URL] (optional) 3. TreeMap.h 4. [login to view URL] (optional) 5. SearchTable.h 6. [login to view URL] (optional) 7. BinarySearchTree.h (optional) 8. [login to view URL] (optional) 9. [login to view URL] In the list of files above, the .cpp files are optional because the function implementations can be placed directly inside the .h files. Due to the way C++ implements templates, the function implementations must be visible when compiling the template class. This can be accomplished by either by providing the implementation inside the class itself, or by including the .cpp at the end of the .h file. If you do not have .cpp files, your .h files must contain the function implementations. The [login to view URL] file will contain the following sections: 1. Plots 2. Questions 4 3. Source Code Combine all of the above deliverable files into one zip file and upload it to portal by the due date. Clearly specify your name in the report.