3. (a) Box 3 shows a contract for a Map abstract data type. Explain carefully what is meant by a map. [Notes] A map is a collection of (key, value) entries, in no particular order, with no two entries having the same key. [2 marks for precise explanation.] (b) Using the contract of Box 3, write application code to do the following: (i) (ii) [2] Declare a map that will be used to record employees' names and their pay. Assume that all employees will have different names. Add an employee named Homer with pay $20,000, and an employee named Monty with pay $500,000. (iii) Remove Homer. Decrease the pay of the employee named Carl by $1,000. (V) Increase all employees' pay by 1%. [Notes] (i) Map payroll; (ii) payroll.put("Homer", 20000); payroll.put ("Monty", 500000); (iii) payroll. remove ("Homer"); (iv) String empName = "Carl"; (v) int pay payroll. get (empName); payroll.put (empName, pay-1000); for (String empName : payroll.keyset () ) { int pay payroll. get (empName)); } payroll.put (empName, (int) pay*1.01); [1 mark for each of (i)-(iv) + 2 marks for (v).] [6] (c) Explain how a map could be represented by a binary-search-tree (BST). Briefly explain how each of the operations of Box 3 would be implemented. (Note: If an operation is implemented by a standard BST algorithm, simply name the algorithm.) [Notes] Represent the map by a BST in which each node contains a key and the corresponding value. The BST is sorted by key (i.e., lesser keys go in the left subtree and greater keys in the right subtree). Implement the clear operation by setting the BST header to null. Implement the put operation by the BST insertion algorithm, modified to replace the value if a node containing key k is found. Implement the remove operation by the BST deletion algorithm. Implement the get operation by the BST search algorithm. Implement the keyset operation by simply returning a reference to the BST. (This assumes that sets are represented in the same way as maps.) [2 marks for data structure +1 mark for each non-trivial algorithm.] [6] (d) Suppose that we start with an empty map, represented by a BST. Then we add ("Homer", 20000), then add ("Monty", 500000), then add ("Carl", 100000), then add ("Lenny", 25000), then remove "Homer". Show the contents of the BST after each operation. [Unseen problem] After adding "Homer": "Homer" 20000 After adding "Homer" 20000 "Monty": After adding "Carl": After adding "Lenny": After removing "Homer": "Carl" 100000 "Carl" 100000 "Carl" 100000 "Homer" 20000 "Homer" 20000 "Lenny" 25000 "Lenny" 25000 [1 mark for each insertion + 2 marks for deletion.] "Monty" 500000 "Monty" 500000 "Monty" 500000 "Monty" 500000 A [6] public class Map { // A Map object represents a homogeneous map with keys of type K and // values of type V. public void clear (); // Make this map empty. public void put (K k, V v); // Add an entry to this map with key k and value v, replacing any existing entry // with key k. public void remove (K k); // Remove the entry with key k from this map, if any. public V get (K k); // Return the value from the entry with key k in this map, or null if there is no // such entry. public Set keyset (); // Return the set of all keys in this map. Box 3 A Map contract. Active