Sparse Matrix and Vector

Problem 1. (Sparse Vector) Use a symbol table of index-value pairs to implement a data type called SparseVector that represents an n-dimensional sparse vector, storing only the non-zero components of the vector. The data type must support the following API:

public class SparseVector
// Create an n-dimensional zero vector.
public SparseVector(int n)

// Create a vector whose components are given in a.
public SparseVector(double[] a)

// Return the number of dimensions of this vector.
public int size()

// Return the number of nonzero components in this vector.
public int nnz()

// Return the ith component of this vector.
public double get(int i)

// Set the ith component of this vector to x.
public void set(int i, double x)

// Return a new vector that is this vector plus that.
public SparseVector add(SparseVector that)

// Return a new vector that is alpha times this vector.
public SparseVector scale(double alpha)

// Return the dot product of this vector with that.
public double dot(SparseVector that)

// Return the norm (length) of this vector.
public double norm()

// Return a string representation of this vector.
public String toString()

$ java SparseVector
a = (3, 0.5)(6, 0.11)(9, 0.75)
b = (3, 0.6)(4, 0.9) a dot b = 0.3
c = a + b = (3, 1.1)(4, 0.9)(6, 0.11)(9, 0.75)
dim = 10
nnz = 4
alpha * a = (3, 1.5)(6, 0.33)(9, 2.25)
norm b = 1.0816653826391966

Problem 2. (Sparse Matrix) Implement a data type called SparseMatrix that represents an m-by-n sparse matrix, as an array of size m of n-dimensional SparseVector objects. The data type must support the following API:

public class SparseMatrix
// Create an m-by-n zero matrix.
public SparseMatrix(int m, int n)

// Create an m-by-n matrix whose elements are given in a.
public SparseMatrix(double[][] a)

// Return a two-element array whose elements are the number of rows
// and columns of this matrix.
public int[] size()

// Return the number of nonzero elements in this matrix.
public int nnz() {

// Return the element at (i, j).
public double get(int i, int j)

// Set the element at (i, j) to x.
public void set(int i, int j, double x)

// Return a new vector that is the product of this matrix and x.
public SparseVector times(SparseVector x)

// Return a new matrix that is the sum of this matrix and that.
public SparseMatrix add(SparseMatrix that)

// Return a string representation of this matrix.
public String toString()

$ java SparseMatrix
A = m = 5, n = 5, nnz = 6
0: (0, 1.0)
1: (1, 1.0)
2: (2, 1.0)(4, 0.3)
3: (3, 1.0)
4: (4, 1.0)
B = m = 5, n = 5, nnz = 5
0: (0, 1.0)
1: (1, 1.0)
2: (2, 1.0)
3: (3, 1.0)
4: (4, 1.0)
A + B = m = 5, n = 5, nnz = 6
0: (0, 2.0)
1: (1, 2.0)
2: (2, 2.0)(4, 0.3)
3: (3, 2.0)
4: (4, 2.0)
B * x = (0, 1.0)(1, 2.0)(2, 3.0)(3, 4.0)(4, 5.0)