One of the most common operations involving a matrix is a matrix-vector multiplication operation. Many engineering software programs will typically perform millions of matrix-vector multiplications. Let A be an n by n matrix with entries a_ij, where 1 <= i <= n and 1 <= j <= n. Let x be a size-n vector with entries x_j for 1 <= j <= n. Then the product A*x is a size-n vector whose ith entry is a_i1*x₁ + a_i2*x₂ + a_i3*x₃ + ... + a_in*x_n. In other words, the ith entry of A*x is simply the dot product of the ith row of A with x.

1. Add a method called product to the CRS class that takes a vector x (stored in a 1-dimensional float array) and returns the product of the matrix stored in the CRS object with x. The method should have the following header:

   	float[] product(float[] x)
   

   You may assume that the size of x is identical to the dimensions of the square matrix stored in the CRS object; so there is no need to do any error checking. Your implementation should take advantage of the fact that (i) in CRS representation the matrix is stored row by row and (ii) the zeroes in the matrix, which are not explicitly stored in the CRS object, make no contribution to the matrix-vector product.

2. To test and experiment with the product method, write a program called CRSTester.java. This should contain, at least, the following methods.
   1. A method called uncompressedProduct that takes an n by n matrix A, stored in the standard manner in a 2-dimensional float array, and a size-n vector x and returns the product A*x. The header for this method should be:

      	float[] uncompressedProduct(float[][] A, float[] x)
      

   2. A method called generateMatrix that takes a probability p and a positive integer n and returns an n by n matrix (stored in a 2-dimensional array). Each entry in the array is non-zero with probability p. So if p = 1/100, we would expect 99% of the entries to be 0 and 1% of the entries to be non-zero. The exact values of the non-zero entries does not really matter; just to keep things simple let us assume that each non-zero entry is a real number generated at random in the range 1 through 2. The header for this method should be:

      	float[][] generateMatrix(float p, int n)
      

   3. A method called generateVector that takes a positive integer n and returns a size-n vector. You can generate the entries of the vector at random in the range 0 through 1. The header for this method should be:

      	float[] generateVector(int n)
      

3. The goal of your experiment is to compare the performance (i.e., running time) of product and uncompressedProduct. The general idea is that the method product needs to access only the non-zero entries of the matrix, whereas uncompressedProduct looks at all entries and therefore product should be much faster than uncompressedProduct. To perform a comparison, set p = 1/100 and generate n by n matrices with n = 500, 600, 700, ..., 1000. Also generate size-n vectors for the same values of n. Use uncompressedProduct to multiply each matrix with the corresponding vector and record the running time of uncompressedProduct. Then for each matrix, construct a CRS object and then use the method product to perform the same multiplication. Also record the running time of product.

   Make a table showing the running times of product and uncompressedProduct for the same matrix-vector pairs. How much faster (e.g., 5 times faster) is product, relative to uncompressedProduct? As n increases, how does the relative speed of product and uncompressedProduct change.