Project 1: List of Sparse Matrices - Fall 2026

Due: Tuesday Sep 29, before 9:00 pm

Objectives

  • Practice analyzing a project's requirements.
  • Implement an algorithm to compress sparse matrices.
  • Implementing a singly linked list.
  • Combining two data structures to satisfy a project's requirements.
  • Practice C++ dynamic memory management, i.e. avoiding memory leaks, avoiding double free, protection against wrong accesses in memory (segmentation fault), etc.
  • Practice writing test cases for a project.

Introduction

In many applications we need to use large matrices which most of their elements are zero. Such a matrix is called a sparse matrix. We do not need to store many zeros, because it consumes memory without being required. Researchers introduced formats to represent the sparse matrices without storing all zeros. One of the formats to represent sparse matrices is called Compressed Sparse Row (CSR). CSR format packs members of a matrix into an array. The following example shows how CSR is presenting a sparse matrix. The following example is from Wikipedia.

In the above matrix (4 x 6) we only need to store the non-zero values. We define three arrays, V stores the non-zero values, COL_INDEX stores column indices for the non-zero values respectively, and ROW_INDEX is described shortly after this. We can populate the arrays by scanning the matrix from left to right, row by row from top to bottom. Then, for the above example, 

            V = [ 10  20  30  40  50  60  70  80 ]
    COL_INDEX = [ 0   1   1   3   2   3   4   5  ]

The ROW_INDEX array stores the information as follows, in the first index it stores 0, in the second index it stores the cumulative number of non-zero elements from first row in the sparse matrix, that would be 2. One may note that there are two non-zero values in the first row of the sparse matrix. The ROW_INDEX array stores the value 4 in its third position since from row 0 to row 1 in the sparse matrix there are 4 non-zero values. In general the ROW_INDEX array stores at every i-th position the cumulative number of non-zero members from row 0 to row (i-th – 1) from the sparse matrix. One may note that the i-th positions start at 0. This means at the last position of ROW_INDEX we store the total number of non-zero values. 

    ROW_INDEX = [ 0  2  4  7  8 ]

The following presents how we access every individual member of the matrix. To extract the members of a row in matrix, we use the following calculations, 

    row_start = ROW_INDEX[row]
    row_end   = ROW_INDEX[row + 1]

For example, to extract members of row 2 from the sparse matrix, row_start would be 4 (ROW_INDEX[2] = 4), and row_end would be 7 (ROW_INDEX[2+1] = 7). We can find the members of row 2 from the sparse matrix in the array V. The indices 4 to (7-1) are the non-zero values in the row 2 of matrix, i.e. 50, 60, and 70. For every one of those non-zero values we can find its column index in COL_INDEX. For example, the column index for 50 would be 2, and the column index for 70 would be 4.

We can calculate the sparsity ratio for a matrix, which shows how sparse the matrix is. The number of zeros divided by the total number of members in a matrix shows the sparsity ratio. The sparsity ratio allows us to determine how efficient is the used data structure in regard to space (memory). In this project we convert the ratio into percentage, e.g. if the ratio is 0.656, we convert it to 0.656 x 100 = 65.

Assignment

Your assignment is to implement a linked list data structure with head pointer along with support for Compressed Sparse Row (CSR) objects.

For this project, you are provided with the skeleton .h files and a sample driver:

  • csr.h - Interface for the CSR and CSRList classes.
  • csr.cpp - The skeleton for the CSR and CSRList classes implementation.
  • driver.cpp - The sample driver/test program.
  • driver.txt - The output of sample driver/test program.

You will implement the classes CSR and CSRList in csr.cpp.

Specifications

The CSR Class

The CSR class has three member variables m_values, m_col_index, and m_row_index which can be used for storing the information about a sparse matrix according to the Compressed Sparse Row algorithm. One may refer to the Introduction section on this page for the details about the algorithm. The member variables in the CSR class require dynamic memory allocation. The CSR class has also a member variable m_next which points to the next CSR object in a linked list. The class CSR can be used as a node in a linked list. The CSR class should not handle allocating or deallocating on its m_next member variable.

CSR::CSR()
This is the default constructor. It creates an empty object. An empty object does not hold any memory. The constructor must initialize all member variables.
CSR::~CSR()
This is the destructor and it deallocates the memory.
CSR::CSR(const CSR & rhs)
Copy constructor creates a deep copy of rhs.
void CSR::compress(int m, int n, int array[], int arraySize)
This function receives a sparse matrix in the form of an array and creates a compressed version of the sparse matrix. All required memory allocation happens in this function. Since the function can be re-called on the same object the function needs to re-create new memory for the new sparse matrix that is passed to the function. Moreover, the compress(...) function initializes all member variables.
int CSR::getAt(int row, int col) const
Returns the value of the matrix member at indices row and col. If the requested indices do not exist (they are out of range) the function throws a runtime_error exception. The exception is defined in <stdexcept> library and is available from std namespace.
int CSR::sparseRatio()
Returns the sparsity ratio for the CSR object. It returns the ratio as percentage, e.g. if the ratio is 0.656, the function returns 0.656 x 100 = 65 as integer. If the CSR object is empty this function returns zero. If all members of the matrix are zero the function returns 100.
bool CSR::operator==(const CSR & rhs) const
Overloaded equality operator returns true if all members of two matrices are equal.
void CSR::clear()
This function deallocates all memory and converts the object to an empty CSR object.
bool CSR::empty() const
This function returns true if the object is empty, otherwise it returns false.

The CSRList Class

The class CSRList implements a singly linked list in which nodes are of the type CSR.

CSRList::CSRList()
This is the default constructor. It creates an empty object. An empty object does not hold any memory. The constructor must initialize all member variables.
CSRList::~CSRList()
This is the destructor and it deallocates the memory.
CSRList::CSRList(const CSRList & rhs)
Copy constructor creates a new CSRList object from rhs.
Note: If we use simply insertAtHead(...) to make insertion, the new list will be reversed. That is not what we need. Copy constructor makes an exact copy of rhs, i.e. the order of the CSR objects should be the same as rhs.
const CSRList& CSRList::operator=(const CSRList & rhs)
The overloaded assignment operator creates an exact deep copy of the rhs object.
bool CSRList::operator==(const CSRList & rhs) const
The overloaded equality operator returns true if both lists have the same matrices and in the same order, otherwise returns false.
int CSRList::getAt(int CSRIndex, int row, int col) const
This function returns the value of a matrix member with row and col indices, from the matrix at the position CSRIndex in the CSRList object. If the requested indices do not exist (they are out of range in the matrix or the matrix does not exist in the list) the function throws a runtime_error exception. The exception is defined in <stdexcept> library and is available from std namespace.
int CSRList::averageSparseRatio()
This function returns the average sparse ratio for all matrices stored in the CSRList object. It returns the ratio as percentage, e.g. if the ratio is 0.656, the function returns 0.656 x 100 = 65 as integer.
void CSRList::insertAtHead(const CSR & matrix)
This function inserts the CSR object at the head of the CSRList object.
void CSRList::clear()
This function resets the CSRList object to its initial, empty state.
bool CSRList::empty() const
This function returns true if the list is empty, otherwise it returns false.

Additional Requirements

  • To build a matrix from the array, we use the row-by-row scanning pattern. For example, if the array is {0,1,0,0,0,0,0,2}, the indices 0 to 3 make the first row of the matrix, and the indices 4 to 7 make the second row of the matrix for a matrix of 2 x 4.
  • In constructing a CSR object, if the number of data members in the input array is less than (m x n), the function uses the array to initialize the matrix, and the rest of matrix members will be initialized to zero.
  • In constructing a CSR object, if the number of data members in the input array is greater than (m x n), the function uses the array to initialize the matrix, and the rest of array data will be ignored.
  • In constructing a CSR object, if the user decides to make a 0 x 0 matrix, that would be considered an empty object, even if user provides data in the array.
  • In constructing a CSR object, if user specifies the matrix size, but does not provide data in the array it would be considered a matrix with all members set to zero.
  • The class declarations (CSR, CSRList) and provided function implementations in csr.cpp may not be modified in any way. No additional libraries may be used.
  • You are not allowed to use STL template containers in the CSR and CSRList classes.
  • You are allowed to use STL template containers in your test functions.
  • The class functions must be written in csr.cpp; in particular, they must not be written “in-line.”
  • Private helper functions may be added, but must be declared in the private section of the CSR and CSRList classes. There is a comment indicating where private helper fuction declarations should be written.

Testing

  • The test file name must be mytest.cpp; the file name must be in lower case, a file name like myTest.cpp is not acceptable.
  • The test file must contain the declaration and implementation of your Tester class and the main() function as well as all your test cases, i.e. calls to your test functions.
  • You are responsible for adequately testing your work before submission. The following section presents a non-exhaustive list of tests to perform on your implementation.
  • You must write a separate function for every test case.
  • Every test function must return true/false depending on passing or failing the test. Visual outputs are not accepted as test results.
  • The dump() function should not be called in the test functions. The dump() function is only provided to facilitate debugging.
  • Tests cannot be interactive. The test file mytest.cpp must compile and run to completion.
  • An example of declaring, implementing, and calling a test function, and outputting the test results was provided in the driver.cpp file of project 0.
  • The testing guidelines page provides information that helps you to write more effective test cases.

Note: Testing incrementally makes finding bugs easier. Once you finish a function and it is testable, make sure it is working correctly.

Testing CSR Class

  • Test whether the compress(...) function works correctly for a normal case, e.g. it populates the member variables of the class with the expected values for an array of data.
  • Test whether the compress(...) function works correctly for an error case, e.g. the user provides data which is less than the asking matrix size.
  • Test whether the compress(...) function works correctly for an error case, e.g. the user asks for a 0 x 0 matrix but provides data.
  • Test whether the overloaded equality operator works correctly for a normal case.
  • Test whether the overloaded equality operator works correctly for an edge case, i.e. both objects are empty.
  • Test whether the getAt(...) function throws an exception for an error case, i.e. the requested index numbers do not exist in the matrix.

Testing CSRList Class

  • Test whether the overloaded assignment operator works correctly for a normal case.
  • Test whether the overloaded assignment operator works correctly for an edge case, e.g. the case of assigning an empty object to an object that contains data.
  • Test whether the getAt(...) function throws an exception for an error case, i.e. the list of matrices is empty.
  • Test whether the getAt(...) works correctly for a normal case, it returns the expected answer.

Testing For Memory Leaks / Memory Errors

  • Run your test program in valgrind; check that there are no memory leaks or errors.
    Note: If valgrind finds memory errors, compile your code with the -g option to enable debugging support and then re-run valgrind with the -s and --track-origins=yes options. valgrind will show you the line numbers where the errors are detected and can usually tell you which line is causing the error.
  • Never ignore warnings. They are a major source of errors in a program.

What to Submit

You must submit the following files to the proj1 submit directory:

  • csr.h
  • csr.cpp
  • mytest.cpp (Note: This file contains the declaration and implementation of your Tester class as well as all your test cases.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command: 

   cp csr.h csr.cpp mytest.cpp ~/cs341proj/proj1/

Grading Rubric

For details of grading rubric please refer to Project Grading Policy