sparse matrices cs1c

Part A (required) – Sparse Matrices

This is going to be a fun assignment. Imagine trying to allocate a 100000 x 100000 matrix of objects on any computer in a resident program (without using disk storage). Can’t be done. But with your knowledge of ArrayLists and LinkedLists, you can create a template that you and your company can use to do just that.

Design a generic class SparseMat<E> which implements a sparse matrix. Use FHarrayList and FHlinkedList, only, as base ADTs on which to build your class. Your primary public instance methods will be:

• SparseMat( int numRows, int numCols, E defaultVal) – A constructor that establishes a size (row size and column size both > 1) as well as a default value for all elements. It will allocate all the memory of an empty matrix by calling a private utility void allocateEmptyMatrix().
• E get(int r, int c) – An accessor that returns the object stored in row r and column c. It throws anIndexOutOfBoundsException if matrix bounds (row and/or column) are violated.
• boolean set(int r, int c, E x) A mutator that places x in row r and column c. It returns false without an exception if bounds are violated. Also, if x is the default value it will remove any existing node (the internal data type used by SparseMat) from the data structure, since there is never a need to store the default value explicitly. Of course, if there is no node present in the internal data representation, set() will add one if x is not default and store x in it.
• void clear() – clears all the rows, effectively setting all values to the defaultVal(but leaves the matrix size unchanged).
• void showSubSquare(int start, int size) – a display method that will show a square sub-matrix anchored at (start, start) and whose size is size x size. In other words it will show the rows from start to start + size -1 and the columns from start to start + size – 1. This is mostly for debugging purposes since we obviously cannot see the entire matrix at once.

Here is a sample main() that will test your template. However, this does not prove that you are correctly storing, adding and removing internal nodes as needed. You’ll have to confirm that by stepping through your program carefully. You main should also print the upper left and lower right of the (huge) matrix, so we can peek into it.

// CIS 1C Assignment #2 
// Instructor Solution Featuring clone()

// client -----------------------------------------------------
import cs_1c.*;
import java.util.*;

//------------------------------------------------------
public class Foothill
{
   final static int MAT_SIZE = 100000;
   // -------  main --------------
   public static void main(String[] args) throws Exception
   {
      // 100000 x 100000 filled with 0
      int k;
      SparseMat<Double> mat 
         = new SparseMat<Double>(MAT_SIZE, MAT_SIZE, 0.); 

      // test mutators
      for (k = 0; k < 10; k++)
      {
         mat.set(k, k, k*1.);
         mat.set(4, k, k*10.);
         mat.set(k, 4, -k*10.);
      }
      mat.showSubSquare(0, 12);
      System.out.println();
      
      SparseMat<Double> mat2 = (SparseMat<Double>)mat.clone();
      
      for (k = 0; k < 10; k++)
      {
         mat.set(k, k, 1.);
         mat.set(4, k, 10.);
         mat.set(k, 4, -10.);
      }
      
      mat.showSubSquare(0, 12);
      System.out.println();
      mat2.showSubSquare(0, 12);
   }
}

Depending on how your showSubSquare() formats numbers, a run might look like this:

 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  1.0  0.0  0.0 -10.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  2.0  0.0 -20.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  3.0 -30.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0 10.0 20.0 30.0 -40.0 50.0 60.0 70.0 80.0 90.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -50.0  5.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -60.0  0.0  6.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -70.0  0.0  0.0  7.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -80.0  0.0  0.0  0.0  8.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -90.0  0.0  0.0  0.0  0.0  9.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 1.0  0.0  0.0  0.0 -10.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  1.0  0.0  0.0 -10.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  1.0  0.0 -10.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  1.0 -10.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
10.0 10.0 10.0 10.0 -10.0 10.0 10.0 10.0 10.0 10.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -10.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -10.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -10.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -10.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -10.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  1.0  0.0  0.0 -10.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  2.0  0.0 -20.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  3.0 -30.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0 10.0 20.0 30.0 -40.0 50.0 60.0 70.0 80.0 90.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -50.0  5.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -60.0  0.0  6.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -70.0  0.0  0.0  7.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -80.0  0.0  0.0  0.0  8.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0 -90.0  0.0  0.0  0.0  0.0  9.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 

As support, you’ll want an inner node class, which you should call MatNode, as a building block. I’ll give this to you now without charge:

   // protected enables us to safely make col/data public
   protected class MatNode implements Cloneable
   {
      public int col;
      public E data;
      
      // we need a default constructor for lists
      MatNode()
      {
         col = 0;
         data = null;
      }

      MatNode(int cl, E dt)
      {
         col = cl;
         data = dt;
      }
      
      public Object clone() throws CloneNotSupportedException
      {
         // shallow copy
         MatNode newObject = (MatNode)super.clone();
         return (Object) newObject;
      }
   };

Notes:

1. Your MatNode class will need (and has, as you can see, above) a default constructor, as you will be creating an FHlinkedList of these things for each row, and FHlinkedList instantiates two objects (header and tail nodes) without parameters.
2. As specified, showSubSquare(), only allows sub-matrices along the diagonal. You may change the signature if you wish to make it more flexible. (You can add String formatting in this if you wish – your output does not have to look like mine.)

Part B (2 points extra credit)

Make SparseMat implement Cloneable and provide a clone() (correctly, as per Java standards for clone(), as you learned in your previous courses.)

Once your assignment is graded and returned, you can view the instructor solution here:

• Quiz List

Your access code will be provided in your graded assignment comments. Find the assignment in the list, click “Take Survey” and you will see the solution. Even though it is called a “Quiz,” it is actually just a solution; there is no need to submit anything, just open the quiz and see the solution.

 

Looking for a similar assignment? Our writers will offer you original work free from plagiarism. We follow the assignment instructions to the letter and always deliver on time. Be assured of a quality paper that will raise your grade. Order now and Get a 15% Discount! Use Coupon Code "Newclient"