Foothill De Anza Community Sparse Matrices CS1C Programming Assignment
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 _x000D_
// Instructor Solution Featuring clone()_x000D_
_x000D_
// client -----------------------------------------------------_x000D_
import cs_1c.*;_x000D_
import java.util.*;_x000D_
_x000D_
//------------------------------------------------------_x000D_
public class Foothill_x000D_
{_x000D_
final static int MAT_SIZE = 100000;_x000D_
// ------- main --------------_x000D_
public static void main(String[] args) throws Exception_x000D_
{_x000D_
// 100000 x 100000 filled with 0_x000D_
int k;_x000D_
SparseMat<Double> mat _x000D_
= new SparseMat<Double>(MAT_SIZE, MAT_SIZE, 0.); _x000D_
_x000D_
// test mutators_x000D_
for (k = 0; k < 10; k++)_x000D_
{_x000D_
mat.set(k, k, k*1.);_x000D_
mat.set(4, k, k*10.);_x000D_
mat.set(k, 4, -k*10.);_x000D_
}_x000D_
mat.showSubSquare(0, 12);_x000D_
System.out.println();_x000D_
_x000D_
SparseMat<Double> mat2 = (SparseMat<Double>)mat.clone();_x000D_
_x000D_
for (k = 0; k < 10; k++)_x000D_
{_x000D_
mat.set(k, k, 1.);_x000D_
mat.set(4, k, 10.);_x000D_
mat.set(k, 4, -10.);_x000D_
}_x000D_
_x000D_
mat.showSubSquare(0, 12);_x000D_
System.out.println();_x000D_
mat2.showSubSquare(0, 12);_x000D_
}_x000D_
}_x000D_
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 _x000D_ 0.0 1.0 0.0 0.0 -10.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 2.0 0.0 -20.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 3.0 -30.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 10.0 20.0 30.0 -40.0 50.0 60.0 70.0 80.0 90.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -50.0 5.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -60.0 0.0 6.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -70.0 0.0 0.0 7.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -80.0 0.0 0.0 0.0 8.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -90.0 0.0 0.0 0.0 0.0 9.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 1.0 0.0 0.0 0.0 -10.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 1.0 0.0 0.0 -10.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 1.0 0.0 -10.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 1.0 -10.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 10.0 10.0 10.0 10.0 -10.0 10.0 10.0 10.0 10.0 10.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -10.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -10.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -10.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -10.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -10.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 1.0 0.0 0.0 -10.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 2.0 0.0 -20.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 3.0 -30.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 10.0 20.0 30.0 -40.0 50.0 60.0 70.0 80.0 90.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -50.0 5.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -60.0 0.0 6.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -70.0 0.0 0.0 7.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -80.0 0.0 0.0 0.0 8.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 -90.0 0.0 0.0 0.0 0.0 9.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 _x000D_ _x000D_
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_x000D_
protected class MatNode implements Cloneable_x000D_
{_x000D_
public int col;_x000D_
public E data;_x000D_
_x000D_
// we need a default constructor for lists_x000D_
MatNode()_x000D_
{_x000D_
col = 0;_x000D_
data = null;_x000D_
}_x000D_
_x000D_
MatNode(int cl, E dt)_x000D_
{_x000D_
col = cl;_x000D_
data = dt;_x000D_
}_x000D_
_x000D_
public Object clone() throws CloneNotSupportedException_x000D_
{_x000D_
// shallow copy_x000D_
MatNode newObject = (MatNode)super.clone();_x000D_
return (Object) newObject;_x000D_
}_x000D_
};_x000D_
Notes:
- 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.
- 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:
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.
Do you need a similar assignment done for you from scratch? We have qualified writers to help you. We assure you an A+ quality paper that is free from plagiarism. Order now for an Amazing Discount!
Use Discount Code "Newclient" for a 15% Discount!
NB: We do not resell papers. Upon ordering, we do an original paper exclusively for you.
We are an online Writing Agency that specializes in writing and editing nursing essays and academic assignments..
Have any questions? Talk to us…