Description
Summary. Many real-world applications rely on processing of large 2D matrices that often
have few non-zero elements relative to the total number of entries in the matrix. For Project #3,
you will use linked lists to implement a memory-efficient, sparse 2-dimensional matrix data
structure. Then, you will test your data structure by loading in some large 800×800 matrices,
which we have constructed to contain hidden patterns that will be visible if you have
implemented your matrix correctly.
Overview of a Linked List Sparse Matrix Data Structure Design.
A typical linked list implementation of a sparse matrix relies on two sets of interconnected linked
lists: one for the rows of the matrix, and one for the columns of the matrix. On both sides, an
array can be used to keep track of the heads of each linked list, and each element is part of one
column linked list as well as one row linked list. An example of the logical structure a linked list
is shown below for a 5×5 matrix (Figure A).
Each of the matrix elements will need to store their data, row and column indices, and two links:
one to the next element in that column (if it exists) and one to the next element in that row (if it
exists) (Figure B). The data for the element (1,0) of the sparse matrix is shown as an example
in Figure C. Your goal will be to implement a class MatrixEntry that stores all of this information
as well as a class SparseIntMatrix that implements the linked list structure shown above.
Part I. (20 points) Defining and Implementing a MatrixEntry class
The MatrixEntry class contains all of the data members necessary for storing the data and links
for each element of the sparse matrix. Define and implement this class including the following
methods:
● MatrixEntry(int row, int col, int data) (constructor); input: the row, column, and data
associated with this matrix element; output: an instance of the MatrixEntry class
● int getColumn(); input: none; output: an integer corresponding to the column of this entry
● void setColumn(int col); input: integer corresponding to the column of this entry; output:
none
● int getRow(); input: none; output: an integer corresponding to the row of this entry
● void setRow(int row); input: integer corresponding to the row of this entry; output: none
● int getData(); input: none; output: an integer corresponding to the data associated with
this entry
● void setData(int data); input: integer with the data for this matrix entry; output: none:
● MatrixEntry getNextRow(); input: none; output: output: a MatrixEntry reference for this
entry’s next row. (The next row is defined as the element with the same column number,
and a different row number)
● void setNextRow(MatrixEntry el); input: MatrixEntry reference of this entry’s next row;
output; output: none
● MatrixEntry getNextCol(); input: none; output: a MatrixEntry reference for this entry’s
next column. (The next col is defined as the MatrixEntry element with the same row
number, and a different col number)
● void setNextCol(MatrixEntry el); input: MatrixEntry reference of this entry’s next column;
output: none
Data members: any that are necessary to maintain the object’s state and implement the
methods above. The MatrixEntry class should be defined as a separate class from the
SparseIntMatrix class described below, and all data members should be declared private. Your
SparseIntMatrix class client should interact with MatrixEntry objects through the public
accessor/mutator methods.
Part II. (10 points) Writing Unit Tests for MatrixEntry
Before you implement your SparseIntMatrix class, you will need to write unit tests, using JUnit,
to ensure your MatrixEntry class is working as expected. You are required to implement at least
four unit tests, but are free to write more than that if you wish. Please write the tests in a java file
named MatrixEntryTest.java The unit tests need to assert the following features:
● The MatrixEntry constructor properly initializes the row, column, and data member
variables.
● setRow(), setCol(), and setData() properly update the MatrixEntry’s row, column, and
data variables.
● setNextColumn() updates the correct MatrixEntry reference variable, and
getNextColumn() returns the correct MatrixEntry reference variable.
● setNextRow() updates the correct MatrixEntry reference variable, and getNextRow()
returns the correct MatrixEntry reference variable.
You are free (and encouraged) to use existing JUnit tests we have provided you for this project
as well as previous projects and labs as a resource for creating your testing class.
Hint: Because the row, col, data, nextRow, and nextCol variables in your MatrixEntry class must
be private, you will need to use your getter methods (i.e. getRow() and getCol()) to ensure the
appropriate setter methods are working).
Part III. (50 points) Defining and Implementing a SparseIntMatrix class
Your third goal is to design and implement the SparseIntMatrix class, which should provide the
basic functionality of a matrix, but use the linked list structure described above (NOTE: you
should not just use a 2D array here—you will receive 0 points for a 2D array-based solution,
however you may use two single dimension arrays as shown in the overview).
Note: For full credit, you must keep properly link both rows and columns for each element in the
matrix.
The SparseIntMatrix class should have all of the following methods:
● SparseIntMatrix(int numRows, int numCols) (constructor); Input: integers with the
number of rows and number of columns in this matrix; output: instance of this class
● SparseIntMatrix(int numRows, int numCols, String inputFile) (constructor); Input:
integers with the number of rows and number of columns in this matrix, and a String with
the filename of a file with matrix data. The format of the input file should be comma-
delimited lines with the row,column,data of each element. This constructor should
populate the matrix with this data; output: instance of this class
● int getElement(int row, int col); input: integers with the row and column of the desired
element; output: corresponding element (integer) if one exists or zero otherwise.
● boolean setElement(int row, int col, int data); input: integers with the row and column of
the element to be set and an integer with the matrix data; output: boolean indicating if
operation was successful (e.g. row/col were in the correct range)
● boolean removeElement(int row, int col, int data); input: integers with the row and
column of the element to be removed; output: boolean indicating if an element was
removed or not (false indicates that the element didn’t previously exist or that the row/col
were out of range, true indicates that it did and has been removed). Any links to/from the
element that was removed should be properly updated in the matrix.
● int getNumCols(); input: none; output: integer with the number of columns in this matrix.
● int getNumRows(); input: none; output: integer with the number of rows in this matrix
● boolean plus(SparseIntMatrix otherMat); input: another sparse matrix to be added to the
current one. This method should update the state of the current object; output: boolean
indicating if addition was successful (matrices should be identical dimensions)
● boolean minus(SparseIntMatrix otherMat); input: another sparse matrix to be subtracted
from the current one. This method should update the state of the current object; output:
boolean indicating if addition was successful (matrices should be identical dimensions)
Data members: any that are necessary to implement the methods above using the linked
list structure shown in Figure A. All data members should be declared private.
Part IV. (10 points) Testing your SparseIntMatrix Implementation
Now that you’ve finished implementing the SparseIntMatrix class, write a main method in a
separate class to test its functionality. We have provided three data files for you to test your
implementation: matrix1_data.txt, matrix2_data.txt, and matrix2_noise.txt. All three of these
files are comma-delimited with the following format on each line:
We have also provided a helper class MatrixViewer and EasyBufferedImage which will allow
you to visualize the patterns in these matrices. If you have implemented your matrix
construction correctly matrix1_data.txt will contain an obvious pattern, which you can view by
putting the following code inside a main method:
SparseIntMatrix mat = new SparseIntMatrix(800,800,”matrix1_data.txt”);
MatrixViewer.show(mat);
Matrix2_data.txt also contains a pattern, but it is obscured by random noise. All you’ll need to
do is load in the matrix in matrix2_noise.txt and subtract this matrix off of matrix2_data (i.e.
matrix2_data.minus(matrix2_noise). Check for a pattern before and after removing the noise—
if you’ve implemented your matrix arithmetic correctly, the pattern should be obvious. Be sure
to save all of the code that you use to check these patterns in your main method. To receive the
full 10 points for this section, you must successfully load and properly use all three example files
described above.
Part V. (10 points) Analysis and Comparison of Space Efficiency of your SparseIntMatrix
class
Answer the following questions about the memory used by your SparseIntMatrix implementation
relative to a standard 2-dimensional integer array. Please include your answers in the header of
your SparseIntMatrix.java file.
Assume that for the MatrixEntry class, each of the following require 1 memory unit: row label,
column label, matrix element data, link to next row element, link to next column element. Ignore
the overhead of the array that stores the links to the row/column linked lists— only consider the
memory used in storing matrix elements. Also, you can assume that each element of a 2D
array will require 1 memory unit. Be sure to justify how you arrived at your answers to receive
full credit.
(a) For a square matrix of N x N elements with m non-zero elements, how much memory is
required for the SparseIntMatrix implementation? How much for a standard 2D array
implementation?
(b) For a square matrix, assume N=100,000 and m=1,000,000. Is the SparseIntMatrix
implementation more space-efficient, and if so, by how much? (i.e. was it worth all of the effort
you just went through implementing it?) For what value of m does the 2D array implementation
become more space-efficient than the SparseIntMatrix implementation?
Submitting your finished assignment:
Once you’ve completed Project #3, create a zip file with all of your Java files (.java) and submit
them through Moodle.
Working with a partner:
As discussed in lecture, you may work with one partner to complete this assignment (max team
size = 2). If you choose to work as a team, please only turn in one copy of your assignment. At
the top of your class definition that implements your main program, include in the comments
both of your names and student IDs. In doing so, you are attesting to the fact that both of you
have contributed substantially to completion of the project and that both of you understand all
code that has been implemented.
