To design a sparse matrix class.
None.
At this point, you should have a working implementation of a sparse
vector. This week's requirement is that you reimplement Matrix
with a sparse data representation; that is, a user of your class should be
able to write something like
SparseMatrix m(100000000, 100000000);
m.setelem(99999009, 99999009, 50);
without running out of memory! You might want to use a sparse vector of sparse vectors of ints for your data representation, or at least consider reusing some of your sparse vector code in your new class.
The interface to SparseMatrix should be exactly the same as
Matrix's, which means that the new version of the test suite,
now called checksparsematrix.cc, should run
against it without any errors.
Performing a reasonably large number of operations on a sparse matrix,
even a large one, shouldn't cause the computer to run out of memory or take
an unreasonably long time to compute. Another way to put this is that all of
the algorithms that act on the sparsematrix should have time complexities in
terms of the number of non-zero elements, not the size of the matrix. The
only exception is multiplication, which must work in all cases and must be
memory-efficient, but need not be time-efficient for large matrices. (So, if
your multiply operator sometimes takes a billion years to get the right
answer, that's okay, as long as everything else is snappy.) While by no
means a completely sufficient metric to pass the lab, you should expect
checksparsematrix to run against your code in well under one
second on any UGCS machine.
Since checksparsematrix doesn't know that it can invoke
operations on a huge SparseMatrix, you need to write some test
code to assure yourself (and me) that your implementation is efficient for
enormous matrices. Please submit some thorough test code as
lab5.cc. You cannot pass this lab without writing (and
having your code pass) a reasonably thorough test suite for the sparse
operations.