$29
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 S p a r s e V e c t o r
Create an n - d i m e n s i o n a l zero vector . public S p a r s e V e c t o r ( int n )
Create a vector whose c o m p o n e n t s are given in a . public S p a r s e V e c t o r ( double [] a )
Return the number of d i m e n s i o n s of this vector . public int size ()
Return the number of nonzero c o m p o n e n t s in this vector . public int nnz ()
Return the ith co mp on en t of this vector .
public double get ( int i )
Set the ith co mp on en t of this vector to x . public void set ( int i , double x )
Return a new vector that is this vector plus that . public S p a r s e V e c t o r add ( S p a r s e V e c t o r that )
Return a new vector that is alpha times this vector . public S p a r s e V e c t o r scale ( double alpha )
Return the dot product of this vector with that . public double dot ( S p a r s e V e c t o r that )
Return the norm ( length ) of this vector .
public double norm ()
Return a string r e p r e s e n t a t i o n of this vector . public String toString ()
$ java S p a r s e V e c t o r
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.081665
3826391966
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:
1 of 3
CS210 Project 5 (Sparse Vector and Matrix) Swami Iyer
public class S p a r s e M a t r i x
Create an m - by - n zero matrix . public S p a r s e M a t r i x ( int m , int n )
Create an m - by - n matrix whose elements are given in a. public S p a r s e M a t r i x ( 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 S p a r s e V e c t o r times ( S p a r s e V e c t o r x )
Return a new matrix that is the sum of this matrix and that . public S p a r s e M a t r i x add ( S p a r s e M a t r i x that )
Return a string r e p r e s e n t a t i o n of this matrix .
public String toString ()
$ java S p a r s e M a t r i x
A = m = 5 , n = 5 , nnz = 6
(0, 1.0)
(1, 1.0)
(2, 1.0)(4 , 0.3)
(3, 1.0)
(4, 1.0)
B = m = 5 , n = 5 , nnz = 5
(0, 1.0)
(1, 1.0)
(2, 1.0)
(3, 1.0)
(4, 1.0)
A + B = m = 5 , n = 5 , nnz = 6
(0, 2.0)
(1, 2.0)
(2, 2.0)(4 , 0.3)
(3, 2.0)
(4, 2.0)
B * x = (0 , 1.0)(1 , 2.0)(2 , 3.0)(3 , 4.0)(4 , 5.0)
Files to Submit:
2 of 3
CS210 Project 5 (Sparse Vector and Matrix) Swami Iyer
SparseVector.java
SparseMatrix.java
report.txt
3 of 3