Essay paper

Introduction This homework is intended to reinforce your understanding of working with maps in general. Your task is to implement and test both a treemap and a hashmap, as well as to complete some functions that use their functionality. 1.1 Deadline May 1, 2020 at 11:59pm 1.2 Submission You must create a .zip file containing all of the files that you develop and work with and you must submit only the .zip file to blackboard before the deadline. Your .zip file must be named using the following naming convention: -hw-07.zip For example, my NetId is jrt. If I submitted the homework, I would name my .zip file: jrt-hw-07.zip Do not submit the compiled .class files. You must submit any .java files and assets that support the application. 1.3 Grading Rubric • 35% For working implementation • 15% For sufficient comments • 10% For consistent coding style • 10% For successful binary tree unit testing • 10% For successful hash table testing • 20% For written analysis 1.4 Comments Throughout the semester, you have been provided model documentation for previous assignments. At this point, you must assume responsibility for documenting the classes that you develop. You should follow the models provided in earlier homeworks as an example. Specifically, you must include the following style of comments to receive full credit: • You must provide a file header for any files that you submit that documents the author and what is defined in the file. • You must document any instance variables, i.e. variables that belong to the class. 1• You must also document all functions that you implement with a function block header which must include information on what the function does, what the inputs to the function represent, and what the function returns. • You must provide relevant line comments inside any functions. 1.5 Plagarism We will use a set of automated tools specifically designed to analyze code for plagarism. If you copy code from another source, classmate or website, there is a very high probability that these tools will flag your work as plagarized. You are permitted to discuss the problems at a high level; however, you must code your own solution. If you do not share code or outright borrow code from a website, you will have no problem with the plagarism filter. 2 Maps As we discussing during class, a map is an abstract data type that associates, i.e. maps, keys to values. A map allows programmers to insert and search for values in the data structure quickly using the key. The key can also be a much more complex representation that is defined by the data in the value object rather than a simple, arbitrary integer value. To give a little more context, let’s consider the Dewey Decimal Classification. Libraries traditionally index books within their collections using a proprietary organizational model originall pioneers through the Dewey Decimal Classification. This classification system associates a key, i.e. an index consisting of numbers and letters, with a book to dictate where in a library that book is stored. This system basically defines how to generate a key in order to prioritize library organization by topic and attempts to ensure that books with similar subject matter are more tightly clustered within the library over a more simple organizational model such author and/or title. Consider how difficult it would be to use a library to cross-reference computer science topics if books by Eberly and Sipser were stored on different floors or even different buildings rather than within several shelves of one another. The key generated by Dewey classification directs library users directly to a floor, aisle, and shelf within the library and allows library users to quickly filter out thousands or even millions of non-relevant books from a search. The library organization model represents a map which facilitates quick access to information. Programmers need to be able to apply similar systems to ensure that search efficiency is minimized. We have also noted that there is close relationship between search efficiency and sorting where our most efficient search algorithm in “flat” data, i.e. binary search, requires an expensive sort operation to impose the organization necessary to gain the advantage of a fast search. To make our systems as efficient as possible, we need to reduce the cost of insertion and maintain order so that the combination of sort and search is efficient. In order to achieve this requirement, we will look at map implementations using both binary trees and hash tables. As we noted in class, the binary tree is a hierarchical data structure whose organizational structure produces the same search efficiency as binary search as long as the tree is balanced. The expensive aspect of maintaining the binary tree is due to rebalancing the tree which is may be performed on insertion. If rebalancing is as efficient as optimal quicksort, then a binary tree is no less efficient than a combination of quicksort and binary search and if rebalancing is more efficient than optimal quicksort then we can use a binary search approach that is more efficient overall than one dependent on quicksort. We also looked at hash tables and noticed that insertion into the hash table occurs in constant time; however, the efficiency of search in a hash table is subject to a number of factors, primarily the bias of the hashing algorithm and the ratio between the number of elements stored to the number of buckets. If the hash algorithm results in the same index being selected, then we are effectively storing data in a single linked-list and our search efficiency will be no better than searching a linked-list, and even if the hash algorithm is unbiased, when the ratio of elements to buckets is large then every bucket contains a lengthy linked-list. In this homework, we will implement maps using a binary tree and a hash table. We will then run a few experiments to confirm experimentally whether the performance of each of these maps approaches the estimates derived through Big O analysis. 22.1 Framework A framework is provided that consists of a number of completed classes and a few classes that you will need to implement. The framework consists of the following files: Analysis.java KVP.java Map.java UnitTests.java BinaryTree.java ListNode.java MapReader.java Utilities.java HashTable.java mapdata TreeNode.java You must implement functions in BinaryTree.java and HashTable.java which are tested and used by the executable files UnitTests.java and Analysis.java. To facilitate implentation of your maps, a TreeNode class is provided in TreeNode.java for your binary tree and a ListNode class is provided in ListNode.java. You will also need to familiarize yourself with the key-value pair implementation in KVP.java. As far as the remaining files, mapdata contains sample data that maps country names to capital cities, MapReader.java loads files structured like mapdata from disk into memory, Map.java defines the abstraction layer met by both implementations, and Utilities.java provides support functions. 2.1.1 profile A profile is an array that is used to track the performance of an operation. Recall that in Homework 2, we used a similar structure to experimentally quantify the number of comparisons needed to perform sorting operations. For this homework, we will use a similar technique to quantify the number of comparisons performed for map operations. For this case, our profile array will be structured such that it consists of one element which will be initialized to zero and will be incremented each time a comparison is performed inside the map during either the search or insert operation. This array must be allocated before calling either operation and is passed into the operation as a parameter. It may be easy to overcount the number of comparisons; however, recall that we can typically perform a comparison and store the result so that we do not need to perform a comparison multiple times. We can also use methods that produce non-binary results, for example the compareTo function returns three possible values, -1 if the parameter preceeds the operand, 0 if the parameter is equivalent to the operand, and 1 if the parameter follows the operand. The compareTo function is illustrated in Module 10 in the BinaryTreeString example and the example in the Appendix in Section 5 at the end of this document updates the BinaryTreeString example and illustrates how to use the compareTo function combined with the profile field to count comparisons. 3 Requirements You must implement the following methods in both the BinaryTree class and the HashTable class using the following function signatures: public void insert(String key, String value, int[] profile); public String search(String key, int[] profile); public void clear(); Please refer to the Section 2.1.1 above for detailed information on the profile parameter. 3.1 Classes This section defines specific requirements for each of the Map implementation classes. 33.1.1 BinaryTree You must implement the map interface methods in the BinaryTree class. Each element in the tree should be maintained by an instance of a TreeNode which provides fields for the key-value pair associated with a tree element and references for potential left and right elements that may be children for a given binary tree element. The constructor for the class takes a rebalance flag that specifies whether or not the tree should be rebalanced after every insertion. If the flag is true, then the provided balance function must be called after every insertion is completed, and if the flag is false, then balance should not be called. We will not count the operations in the rebalancing process in terms of efficiency, but you should keep in mind that balancing adds a cost and high frequency balancing will affect the overall performance of insertion into the tree; however, if balancing is not performed frequently enough, then the overall performance of search will be affected. 3.1.2 HashTable You must implement the map interface methods in the HashTable class. Each element in the hash table should be maintained by an instance of a ListNode which provides fields for the key-value pair associated with a hash table element and a reference for any potential next element that may follow a given hash table element in one of the lists. The constructor for the class takes the number of buckets in the linked-list as a parameter. You will find that ratio of the number of buckets in the linked-list to the number of elements stored in the entire hash table is a key heavily influences the efficiency of map operations in the hash table. Recall that a hash table is an array of linked-lists and the hash function is used to compute the index of the linked-list in the array where a key must be stored. When searching or inserting, you must hash the key using the hash function to compute the index of the bucket in which the key-value pair should be stored. Also recall that the key must be unique which means that upon insert and once the bucket is identified through hashing, you must perform a search on the key in the associated linked-list to determine whether the key is already stored in the linked-list before performing any insertion. This means that we cannot arbitrarily perform tail insertions on the linked-list, so there is no benefit of storing a tail pointer because we will end up searching for the tail anyway. For the sake of profiling comparisons, only count the comparisons when searching the linked-list itself. 3.2 Functions This section gives a general explanation of the requirements for each function. For void insert(String key, String value, int[] profile) Recall that keys must remain unique in a map so there can only be one key-value pair with a given key. Therefore, insert is itself a search operation. If the key does not exist in the map, then insert allocates a new key-value pair and inserts that key-value pair into the map at the appropriate location; however, if the key already exists in the map, then insert instead locates the key-value pair and updates the value associated with that key. For this example, you are not required to update an existing value; however, you still must confirm that a key does not already exist in the map before appending the key-value pair to the respective map. Please refer to the Section 2.1.1 above for detailed information on the profile parameter. String search(String key, int[] profile) search searches through the map for the specified key. If the key is found, search returns the associated value. If the key is not found, search returns a null value to indicate that the key does not exist in the map. Please refer to the Section 2.1.1 above for detailed information on the profile parameter.