CMSC 341 Fall 2006
Project 2
Assigned |
27 Sept 2006 |
Due |
10 Oct 2006, 11:42pm |
Updates
| 05 Oct To avoid complex code when reading the data
files for the matrices, we now promise that the data files
WILL NOT contain comments. This allows you to use
operator>> for data file input
02 Oct In the descriptions of SMRowBegin, SMRowEnd, SMColumnBegin, and
SMColumnEnd, the use of "row" and "column" was incorrect.
These descriptions have been updated.
|
Background
A matrix is a set of values arranged in rows and columns.&nsp;
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 author's List code as a starting point.
You will also create an SMatrixData
class as well as iterators for the SMatrix.
You must implement the SMatrix 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.
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 related iterator code described in the text
and discussed in class. Code for the textbook's double linked list and
linke list iterator classes is available in the public directory.
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2
-
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 exceptions when operations are attempted on incompatible
SMatrix objects.
- Define and implement the necessary exception classes in
P2Exceptions.h which is #included in Proj2.cpp.
-
Implement the functions required by main( ) in
Proj2_aux.cpp. Put their prototypes in
Proj2_aux.h which is #included in Proj2.cpp.
As in project 1, we are providing main( ) in Proj2.cpp
which is found in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2
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.
-
Copy the file
/afs/umbc.edu/users/d/e/dennispub/CMSC341/Proj2/341-Fall06-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.
-
Write a makefile for project 2.
ADT Definitions
The following ADTs must be implemented for this project.
In some instances, the implementation of the ADT is partially specified.
You may add whatever private data
and methods you deem appropriate for any class.
You may assume that the SMatrix (and therefore the SMatrixData class)
will only be used for integers. Therefore, you need not implement
these classes as 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.
To easily implement these functions, the data in the SMatrix should
be sorted by row, then column within row (or vice-versa, your choice).
Your SMatrix class MUST be implemented using a single,
sorted LIST of SMatrixData objects (described below) and use SMatrix
row and column iterators to traverse the matrix to perform the matrix operations defined above.
Feel free to delete any unused code in List.h and to improve the author's
code by adding appropriate error checking.
The public operations allowed on the SMatrix ADT are:
-
SMatrix (int rows, int columns) which
constructs a zero-filled matrix with the specified dimensions.
-
void SetValue (int row, int column, int value)
which sets the specified value into the matrix at the specified row and column.
If there is already a value at the specified row and column, this method overwrites the value.
Otherwise, a new SMatrixData element is added to the SMatrix.
-
const SMatrix operator+ (const SMatrix& rhs 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& rhs) which performs
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<< (ostream & out, const SMatrix & matrix)
Note: Your implementation must use the print idiom described in the
Weiss text on page xx (in the Employee class) and implemented in project 1.
The output format for a matrix is shown in the
sample output
-
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 RowBegin( int column )
-- creates and returns an SMRowIter which points to the first element of
the specified column. This method is analgous to vector's begin( ) method.
-
SMRowIter RowEnd( int column )
-- creates and returns an SMRowIter which points beyond the end of the specified column.
This method is analgous to vector's end( ) method.
-
SMColumnIter ColumnBegin ( int row )
-- creates and returns an SMColumnIter which points to the first element of
the specified row. This method is analgous to vector's begin( ) method.
-
SMColumnIter ColumnEnd ( int row )
-- creates and returns an SMColumnIter which points beyond the end of
the specified row. This method is analgous to vector's end( ) method.
Warning/Hint/Alert:
Think very carefully about
- How these iterators are related to the underlying List iterators
- Possible/Necessary use of friendship. In the author's linked list, the
List is a friend of the itertors. Depending on your implementation, more
friendship may be necessary.
- What "beginning of row", "end of row", "beginning of column",
and "end of column" mean, especially considering
that some rows and/or columns may contain all zeros.
- How can an iterator call methods of the matrix that created it?
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 and stored in matrix. SMatrixData contains the
row, column and non-zero value for a single entry in the matrix.
Since only the SMatrix class should be creating SMatrixData objects, the SMatrixData
definition must be nested within the SMatrix. As with the nested Node in the linked
list, SMatrixData may be implemented as a struct rather than a class. You may implement
any methods of SMatrixData you feel are necessary.
The output format for an SMatrixData object is
[row, column, value ] as shown in the
sample output.
The SMatrix Iterator ADTs
Iterators are used with any data structure if it is
necessary to access the individual elements of that data structure.
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).
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 column iterator might be used in
operator * (matrix multiplication).
These iterators are referred to as SMColumnIter
and SMRowIter, respectively.
You are not required to completely implement both "const" and
"non-const" versions of these iterators. Implement only as much as
needed for your project.
As iterators, these ADTs support the generic iterator methods described
in class:
-
operator++ -- move to the "next" element in the current
row or column (depending on the type of iterator) and returns a SMRowItr or SMColumItr
(depending on the type) that represents the element moved to
-
SMatrixData& operator*
-- retrieve the SMatrixData from the element currently "pointed to" by the iterator.
It is an error to retrieve data from RowEnd() or ColumnEnd().
-
A private constructor to be
used only by the SMatrix class, similar to that of the iterator's private
constructor used in the text and described in class.
- Necessary comparison operators.
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 this project, will implement MatrixAddException
and MatrixMultiplyException which are caught in main( ).
Both exceptions must support the public what( ) which prints
an appropriate method. (Note that what( ) is a standard method
for all STL exceptions). These exceptions should be implemented in
a file named P2Exceptions.h which is #included in Proj2.cpp.
If you wish to add more exceptions in this project,
you may do so.
Proj2_aux.cpp
As in project 1, we are providing main( ) in Proj2.cpp in
Mr. Frey's public driectory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2
As in project 1, this file should not be copied to your directory
and should not be modified. Your makefile should reference this
file. Do not submit Proj2.cpp.
Note that main( ) calls functions which are not found
in Proj2.cpp. You must provide these functions in Proj2_aux.cpp and
provide their prototypes in Proj2_aux.h which is #included in Proj2.cpp.
Sparse Matrix Data Files
Project 2 will be executed with three (3) command line arguments
which are the names of files that contain the sparse matrix data.
If the files can be opened, you may assume the data follows the format specified below.
The row/column/value triples will be randomly generated.
NO ORDERING of the data should be assumed, but you may assume the zero-based
row and column numbers are valid. As in project 1, the data files may
contain blank lines and/or comments (whose first character is '#'). These lines
should be ignored.
- First line -- a postive integer indicating the number of rows
- Second line -- a positive 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
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.
The example belows shows the addition of two 2 X 3 matrices.
Matrix A Matrix B Sum
--------- --------- ---------
4 6 8 3 0 0 7 6 8
12 0 -3 2 0 7 14 0 4
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 left with the 3 X 2 matrix on the right, resulting in the 2 X 2 matrix below
Each element is labelled with its row and column number.
Matrix A Matrix B
----------- ---------
a11 a12 a13 b11 b12
a21 a22 a23 b21 b22
b31 b32
Matrix A * Matrix B (2 x 2)
----------------------------------------------------------
a11*b11 + a12*b21 + a13*b31 a11*b12 + a12*b22+ a13*b32
a21*b11 + a22*b21 + a13*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.
A Matrix should be output by rows. Each non-zero value of the
row is output in the form [row, column, value].
For example, this 3 x 3 matrix
3 x 3 Matrix
------------
12 0 7
0 4 0
0 0 3
would be output as
[0, 0, 12]
[0, 2, 7]
[1, 1, 4]
[2, 2, 3]
Putting multiple non-zero values for the same row on the same line will
help keep your output shorter, but is not required. DO NOT mix data
from different rows on the same line.
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_aux.cpp which contains the functions called from main( )
- SMatrix.h (and SMatrix.cpp if used) -- the definition and implementation file for
the SMatrix class. Because they are tightly related, SMatrixRowIter,
SMatrixColumnItr, and SMatrixData may also be defined and implemented
in this file (as in the text and discussed in class).
- P2Exceptions.h which contains the exceptions caught in main( )
and any other exceptions you deem necessary.
- Your answers to the project questions.
Grading and Academic Integrity
Project grading is described in the Project Policy handout.
Your answers to 341-Fall06-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 the due date will not be accepted. Do not submit any files
after that time.