It is possible to create more efficient linear data structures by restricting access to the ends, as in stacks and queues. It is possible to enhance the efficiency of find operations on a list by using binary search. However, this requires restricting access to the location of data in the structure in order to maintain a sorted order. Access to data in this type of data structure, called a map in Java, is through a key that is associated with, or mapped to, a particular value.
The file SortedArrayMap.java contains the outline for a sorted array based implementation of a map. Notice that there are two generic types for this class K, for keys, and V, for values. You can implement the map by either using parallel arrays (one of type K and one of type V), or with one array of some sub-class (that has instance variables of type K and V). Complete each of the methods in the SortedArrayMap class that has a todo comment. The get and containsKey methods should both use the private binarySearch method to find the index of a particular key. Remember to code in small pieces and test thoroughly. Proceed only when you are sure that your class is functioning properly.
A common use of maps is for memoization, a programming technique where the results of complex computations are stored so that they can be looked up instead of recomputed in the future. We did something similar to this when computing exponents using a recursive definition. Recall the recursive definition of the powers of 2 is:
21 = 2
2e = 2e/2*2e/2 (if e is even and greater than 1)
2e = 2*2(e-1)/2*2(e-1)/2 (if e is odd and greater than 2)
The recursive program that you created in lab used this definition to reduce the number of multiplications needed to compute a power of 2. With memoization previous sub-computations are stored in a map to speed up future computations. For example, when computing 25 the powers 21 and 22 would be computed and therefore the map would contain entries for 21, 22, and 25. As a result, if 210 was computed next, the result of 25 could be looked up in the map, so that only one multiplication is required and 210 would be added to the map.
The file Pow.java is similar to the power program you created in lab 6. Complete the power function to use memoization to compute powers of 2.
To submit your code: Tar your lab10 directory and submit your code on the course Inquire site.