Question 1. Sparse Vectors

In mathematics, a vector is simply a list of numbers, e.g., [13.4, 14.5, 12.2]. In many applications, vectors are sparse, that is, they contain mainly 0 elements, e.g., [0 0 0 0 13.4 0 0 14.5 0 0 0 12.2]. It is inefficient to represent such vectors as regular arrays. Instead, we consider a data structure that only represents data values that are non-zero. It will do this by maintaining elements containing both the one-based index and value of each non-zero entry of the vector. Elements will be stored in increasing order of their one-based index in the vector. Thus the previous vector can be represented as [(5, 13.4), (8, 14.5), (12, 12.2)]. Note that indices can be any integer from 1 to Long.MAX_VALUE.

We will represent this data structure as a singly-linked list, with elements containing both indices and values.

The files below define 4 classes to support this data structure.

· SparseNumericElement defines the data element containing both index and value.

· SparseNumericNode defines the list node that contains an element

· SparseNumericIterator defines an iterator for the vector of elements

· SparseNumericVector defines the vector using the above supporting classes.

All of the code in the first 3 classes is provided.

The only class you need to change and submit is SparseNumericVector. Here you need only add the code for

3 of the methods:

· add(e): add an element e to the vector.  If e contains a value of 0 or if the vector already contains an element with the specified index, your method should throw the built-in UnsupportedOperationException. 

· remove: remove an element from the vector.  Returns true if successfully removed, false if the vector does not contain an element with the specified index.

· dot: take the inner (dot) product of the vector with another vector passed as an argument. This method should run in O(m+n) time, where m and n are the number of non-zero elements in each vector.  For example, given sparse vectors [(5, 13.4), (8, 14.5), (12, 12.2)] and [(3, 4.1) (5, 1.0), (6 23.2), (12, 3.6), (15, 7.3)], dot should return the value 13.4 x 1.0 + 12.2 x 3.6 = 57.32.  (You do not have to worry about numerical overflow exceptions - these will automatically be re-thrown to the caller, and we will not test for these.)

Here is a test program testSparseNumericVector that provides a few test cases. You should, however, test your program using a broader range of test cases. Pay particular attention to boundary conditions.

All files are part of the package A1Q1, and should be downloaded to a directory of the same name.