CMSC 341 Spring 2001

Project 2

Assigned	14 February 2001
Due	28 February 2001

Background

A matrix is a set of values arranged in rows and columns. Matrices are used in many fields of mathematics including linear algebra. In that application, the values represent the coefficients of the terms of many simultaneous equations. In some applications, most of the values in the matrix are zero. Such a matrix is known as a "sparse" matrix since it has few non-zero values. Because there are few non-zero values, programs which implement sparse matrices do not use the usual 2-dimensional array -- to do so would be a large waste of memory. Instead, sparse matrices are implemented with other data structures whose structure is hidden by the implementation of the matrix operations.

Description

    In this project, you will implement a sparse matrix class (SMatrix) using the List ADT. You will write the main program which will be used to test your SMatrix class based on requirements and pseudo code provided for you. You will also create an SMatrixData class as well as iterators for the SMatrix. As discussed in class, you will also need to use ListIterators. See the details below.
    You must implement the List ADT as a sorted linked list Code for the textbook's linked list and linked list iterator classes is provided. You are free to use this code if you wish. You must create your own Makefile for this project as well. Use the makefile from project 1 and modify it as necessary.
    Remember that class template files do not get compiled, and therefore their .o files SHOULD NOT be included in the list of object files. Any .o files for non-template classes SHOULD be listed.

The ADTs described here are expanded on in the "ADT" section, below. Use these expanded versions to design your classes. Please remember that you must provide good documentation as described in the "Project Organization" handout.

Here are your tasks:

Read and understand the List and ListIterator ADTs described in the text and discussed in class. Code for the textbook's linked list and linked list iterator classes is available in the public directory.

/afs/umbc.edu/users/d/e/dennis/pub/CMSC341

(described below)

Be sure that your makefile references the appropriate files.

Implement the SMatrixData ADT described below. This class stores the 0-base row number, 0-based column number, and the value for each non-zero element of the matrix.

Implement the SMatrix ADT described below. This ADT must throw errors when operations are attempted on incompatible SMatrix objects.

Implement the test program Proj2.C, based on the pseudo code found in the file

/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2/Proj2.C

In this program, main( ) takes three parameters -- the names of files which contain the data from which to construct three sparse matrices. The format of these files is specified below. Test files are located in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2/

There are three data files in this directory. The files matrix1.dat and matrix2.dat are both 10 X 8 matrices. This allows them to be added together, but not multiplied together. The file matrix3.dat is an 8 X 8 matrix. This allows it to be multipiled with either matrix1 or matrix2 and allows us to print the diagonal. Any of these may be transposed. Feel free to construct your own data files for further testing. NOTE: The test files supplied may not be the same ones used to grade your project, but will have the relative dimensions as matrix1, matrix2 and matrix3 described above.

Answer the questions posed in 341-Spring01-proj2_questions.txt. Copy the file

/afs/umbc.edu/users/d/e/dennispub/CMSC341/Proj2/341-Spring01-proj2_questions.txt

to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it is 10% of this project's grade.

Modify the makefile you submitted for project 1 to be suitable for project 2

ADT Definitions

    The following ADT must be implemented for this project. In some instances, the implementation of the ADT is at least partially specified.
    All ADTs require the "big 4" -- default constructor, destructor, assignment operator and copy constructor, even if there is no code to write. All ADTs require that all data members be private.
    You may add whatever private data and methods you deem appropriate for any class.
    Note that although the List ADT is implemented as a class template, these ADTs are not templates.

The SMatrix ADT

A sparse matrix is a set of values arranged in rows and columns, but in which the vast majority are zero. The sparse matrix supports all the usual matrix operations. For this project, you may assume that the sparse matrix will consist of integer values.

The operations allowed on the SMatrix ADT are:

SMatrix (int rows, int columns) which constructs a zero-filled matrix with the specified dimensions.
int rows ( void ) const which returns the number of rows in the matrix.
int columns (void ) const which returns the number of columns in the matrix..
int retrieve (int row, int column) const which returns the value located in the matrix at the specified row and column.
void setValue (int row, int column, int value) which sets the specified value into the matrix at the specified row and column.
const SMatrix operator+ (const SMatrix &) which creates an SMatrix object that is the element-wise sum of the host SMatrix and the SMatrix parameter. It is an error to try to add two SMatrix objects that do not have the same dimensions.
const SMatrix operator * (const SMatrix &) which performs the usual matrix multiplication and creates a new matrix which is the product of the host SMatrix and the parameter. It is an error to try to multiply two SMatrix objects unless the number of columns of the host match the number of rows of the parameter. Note that matrix multiplication is NOT commutative.
ostream & operator << (const SMatrix &)

print

ostream & operator<< (ostream &, const SMatrix &)

transpose( ) which changes the host matrix from N rows and M columns into M rows and N columns. To transpose a matrix, each element has its row and column interchanged. For example, the value which is originally found at row 7, column 3 is now found at row 3, column 7.
SMRowIter RowIter(int row ) -- creates and returns an SMRowIter which points to the first element of the specified row.
SMColumnIter ColumnIter (int column ) -- creates and returns an SMColumnIter which points to the first element of the specified column.

Your SMatrix class MUST be implemented using a single, sorted LIST of SMatrixData objects (described below) and use SMatrix iterators to traverse the matrix to perform the matrix operations defined above.

The SMatrixData ADT

Because the data for the sparse matrix is not stored in a 2-dimensional array, the row and column information for each non-zero value must be specified. This ADT provides accessor and mutator methods for the row, column and value. Further, because the SMatrix keeps the non-zero values in a sorted List, this ADT must support a comparison operator.

The operations allowed on the SMatrixData ADT are:

int row ( void ) const and void row ( int ) -- the accessor and mutator of the element's row.
int column ( void ) const and void column ( int ) -- the accessor and mutator of the element's column.
int value ( void ) const and void value ( int ) -- the accessor and mutator of the element's column.
bool operator < ( const SMatrixData &) const -- the "less than" comparison operator.
ostream & operator<< (const SMatrixData &)

print

ostream & operator<< (ostream &, const SMatrixData &)

The SMatrix Iterator ADTs

    Iterators are used with any data structure if it is necessary to access the individual elements of that data structure. Even if the application does not need to access the elements directly, it is still a good idea to use iterators within the data structure's internal methods.
    In the case of the SMatrix class, it is necessary to access the individual elements two ways. One way is starting at (row 0, column 0), and moving along the row (across the columns) to (row 0, column 1), (row 0, column 2), .... to (row 0, column N-1). This iterator could be used for output (among other things). It is also necessary to have an iterator that starts at (row 0, column 0) and moves down the column (across the rows) to (row 1, column 0), (row 2, column 0), ... to (row M-1, column 0). This iterator might be used in operator * (matrix multiplication).
    These iterators are referred to as SMRowIter and SMColumnIter, respectively. An SMRowIter is considered "past end" when it gets to the end of the row. Similarly, an SMColumnIter is considered "past end" when it is at the bottom of the column.

As iterators, these ADTs support the generic iterator methods described in class:

bool isPastEnd ( ) const -- true if the iterator is no longer "pointing" to a meaningful SMatrixData object.
void advance ( ) -- move to the "next" element in the SMatrix. If there is no "next" element, the iterator is "past end".
const SMatrixData & retrieve ( ) -- get the SMatrixData from the element currently "pointed to". It is an error to retrieve data from an iterator that is "past end".
A private constructor to be used only by the SMatrix class, similar to that of the ListIter private constructor used in the text and described in class.

Exceptions in Project 2

Since some SMatrix operations are invalid unless the matrices are "compatible", these methods must detect this incompatibility and throw an exception when it occurs. These exceptions are then caught in main( ) and the appropriate action is taken. In general, good design dictates that "low-level" code should only detect and report errors, not act on them.

In this project, will create our own exception class(es). The file "P2Exceptions.H" defines the BadMatrix exception class which should be thrown when certain matrix operations are not possible because the matrices are incompatible. You will also use "dsexceptions.h" which defines the BadIterator exception class to be thrown when an iterator that "is past end" is used inappropriately.

If you wish to add more exceptions in this project, you may do so. In that case, copy the P2Exceptions.H file into your directory and modify as you deem necessary. If you do make additions to P2Exceptions.H, be sure to submit your version of P2Exceptions.H and make the necessary changes to your makefile.

C++ Exceptions

C++ exceptions are used by the text in various places. Perhaps the first use is on page 74 in the retrieve method. Since you will be seeing exceptions throughout the course, this project will give you some easy experience with them. The particular exceptions you will use are the BadMatrix and BadIterator provided to you. The text defines a few other exceptions such as Underflow, Overflow, and OutOfMemory. You will not be using these in this project, but you will see them used in the text.

An exception can be "thrown" at any point in a program when an exceptional situation occurs. For example, an Overflow exception might be thrown when a quotient has a denominator of zero. An exception is thrown by using the syntax "throw exception". Typical code for Overflow would be:

       if (denom == 0)
          throw Overflow()
       else
          quotient = numer/denom;

When an exception is thrown, the normal flow of control is terminated while a suitable "catcher" is sought along the calling sequence. In this project, the SMatrix operator+ and others will throw the BadMatrix exception if the matrices are incompatible for the operation. Iterators also throw the BadIterator exception if used improperly when "past end".

SMatrix::operator+ (const SMatrix& rhs)
{
   if (the matrices are incompatible)
       throw BadMatrix
   else
       do the operation
}

The code in main( ) that calls operator+ is surrounded by a "try-catch" block.

try
{
matrix1 = matrix2 + matrix3;
}
catch (BadMatrix & exc)
{
cout << "Exception: Incompatible Matrices for addition" << endl;
}

What happens is that if the call to operator+ is made on an incompatible SMatrix, the BadMatrix exception will be thrown. The enclosing "catch" block catches the exception and deals with it. In this case it simply prints an error message. If the "try-catch" block were not present, the exception would not be caught, and it would cause the program to terminate.

Proj2.C

A skeleton version of Proj2.C is publicly available in the directory

/afs/umbc.edu/users/d/e/dennis/pub/CMSC341

This file has not been compiled and serves only as a framework for Proj2.C that you must complete it and submit.
Note that Proj2.C uses try/catch blocks around SMatrix object methods. It expects your code to throw
error. Check out "dsexceptions.h" which is used in the textbook's LinkedList code on how to define exception objects and how to throw and catch them.

Sparse Matrix Data Files

Within Proj2.C, main( ) expects two command line arguments which are the names of files that contain the sparse matrix data. If the arguments are present, you can assume that they are valid filenames and the data follows the format specified below. The row/column/value triple will be randomly generated. NO ORDERING should be assumed.

First line -- an integer indicating the number of rows
Second line -- an integer indicating the number of columns
All remaining lines consist of three integers separated by whitespace and end with a newline

The row number of the non-zero value
The column number of the non-zero value
The non-zero integer value

What to Submit

For this project, you must submit the following files:

Your makefile -- it must be named "makefile" or "Makefile". The graders will simply type "make" and your file must compile and link all source files as appropriate
Proj2.C -- after you have completed it by adding the missing code. DO NOT change the #include directives
SMatrix.H and SMatrix.C -- the definition and implementation files for the SMatrix class. Because all they are tightly related, the SMatrixRowIter, SMatrixColumnItr and SMatrixData classes may also be defined and implemented in these files. You may, of course, choose to implement each of these in it's own .H and .C files.
P2Exceptions.H, only if you have added your own exception classes.
Your answers to the project questions.

Grading and Academic Integrity

Project grading is described in the Project Policy handout.

Your answers to 341-Spring01-proj2_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing
projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files
after that time.

Matrix Operations

For those who have not taken MATH 221 yet, or have simply forgotten, this section gives a brief explanation of matrix addition and multiplication.

Matrix Addition

Two matricies may be added if and only if they have the same dimensions (number of rows and columns). To add the matrices, simply add the corresponding elements of each matrix. The resulting matrix will be the same size as the matrices added together.

Matrix Multiplication

    Two matrices can be multiplied if and only if the number of columns of the left hand matrix is the same as the number of rows of the right hand matrix. For example, you can multiply a 3 x 4 matrix with
a 4 X 2 matrix (the result is a 3 X 2 matrix), but you can't multiply a 3 X 4 matrix with a 2 X 4 matrix.
Consider the following example which multiplies the 2 X 3 matrix on the right with the 3 X 2 matrix on
the left, resulting in the 2 X 2 matrix at the bottom. Each element is labelled with its row and column number.
                Matrix A is 2 X 3                Matrix B is 3 X 2
               a11    a12    a13                        b11    b12
               a21    a22    a23                        b21    b22
                                                                b31    b32

                                         The result is 2 x 2
            a11*b11 + a12*b21 + a13*b31    a11*b12 + a12*b22 + a13*b32
            a21*b11 + a22*b21 + a23*b31    a21*b12 + a22*b22 + a23*b32

To form the product, we multiply the elements of each of matrix A's rows with the corresponding elements of each of matrix B's columns and sum the product of each element-wise multiplication.