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 position and value of each non-zero entries of the vector. Elements will be stored in increasing order of their one-based position in the vector. Thus the previous vector can be represented as [(5, 13.4), (8, 14.5), (12, 12.2)]. Note that positions 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 position indices and values.

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

· SparseNumericElement defines the data element containing both position 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: add an element to the vector

· remove: remove an element from the vector

· 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.

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.