Matrices, Design Recipe, Problem Analysis, Design Issues and Class Interface

<< Class Templates and Nontype Parameters, Templates and Static Members

Matrix Constructor, Matrix Class, Utility Functions of Matrix, Input, Transpose Function >>

CS201 Introduction to Programming

Lecture Handout

Introduction to Programming

Lecture No. 43

Reading Material

Lecture 1, Lecture 25 - Lecture 42

Summary

Programming Exercise - Matrices

Design Recipe

Problem Analysis

Design Issues and Class Interface

Programming Exercise - Matrices

Mathematics is a good domain to develop different classes and programs. For example,

solutions for Complex numbers, Matrices and Quadratic Equations can be sought for

developing our own classes. In this lecture, we will take a problem to manipulate and

perform different operations on Matrices. Matrices are used in lot of real world problems.

We will perform problem analysis, design and implementation.

Let's take a look at analysis and design phases first by using our design recipe.

Design Recipe

Firstly we do analysis and try to come up with a problem statement. Express its essence,

abstractly and with examples. After describing the problems in few sentences, we try to

formulate the problem with examples. It is emphasized to pay attention to the details. We

do analysis of the data structures to be used in the program and choose the best fit to the

program requirements. The code is written to implement the program. After

implementation is completed, we do its testing to verify that it is behaving properly in all

scenarios. If any bugs are found, they are fixed. This cycle of testing and bug fixing

continues until the program is working perfectly without any problem.

We are going to write a program to manage operations on Matrices.

Page 552

CS201 Introduction to Programming

At the start of the problem analysis phase, let's try to understand the problem domain

first.

Problem Analysis

A matrix is nothing but a two-dimensional array of numbers. It is normally represented in

rows and columns. A matrix is represented as:

It is a matrix A with 3 rows and 4 columns. So order of the matrix is 3 * 4.

Before going further, let's consider what are the operations normally performed on

matrices.

- A matrix is added to another matrix.

- A scalar value (an ordinary number) is added to a matrix.

- A matrix is subtracted from another matrix.

- A scalar number is subtracted from a matrix.

- A matrix is multiplied with another matrix.

- A scalar number is multiplied with a matrix.

- A matrix is divided by a scalar.

- A matrix is transposed.

Now, we will define what these operations are and if there are any restrictions on

matrices performing these operations.

The sum or addition of two matrices of the same order is found by adding the

corresponding elements of the two matrices. If A and B are two matrices of order m * n to

be added then their resultant matrix will also have the same order m * n.

Aij + Bij

Where i varies from 1 to m (max number of rows) and j varies from 1 to n (max number

of cols).

Clearly, there is a restriction on the matrices performing this addition operation that they

should have same numbers of rows and columns, in other words their order should be the

same.

There is another operation of addition of scalar number to a matrix. In this operation, a

number is added to all elements of the matrix.

Subtraction operation works in the same fashion that two matrices of the same order takes

part in this operation and resultant matrix with similar order is obtained by subtracting

each element of one matrix from the corresponding element of other matrix. For example,

see the subtraction operation and assignment below:

Cij = Aij - Bij

-2

-4

-5

-2

Page 553

CS201 Introduction to Programming

Not to confuse your understanding with assignment in computer programs, the resultant

matrix is put on the left of assignment operator otherwise in Mathematics it is located on

the right.

Each element of matrix B is subtracted from the corresponding element of the matrix A

and the resultant goes to matrix C. C will have the same number of rows and columns as

A and B.

Similar to the addition, there is another operation for subtracting a scalar from a matrix.

In this case, a number is subtracted from each element of the matrix.

For Division of a matrix by a scalar, the scalar number divides each element of the

matrix. Let x be a scalar number and A be a matrix then division is represented as:

Cij = Aij / x

Each element of matrix A is divided by the number x to produce the corresponding

number in the resultant matrix C. For example, A11 (element in first row and first column

of matrix A) is divided by the scalar number x to provide C11 (element in first row and

first column of matrix C).

The multiplication operation is bit complicated as compared to the above discussed

operations. We will discuss simple case first, when a scalar is multiplied by a matrix.

Suppose, this time we want to multiply the scalar x with the matrix A as:

Cij = x * Aij

Each element of matrix A is multiplied with the scalar x and the resultant number is put in

the corresponding location inside the matrix C.

Now, we will see how a matrix is multiplied with another matrix. Firstly, there is a

restriction on order of the matrices involved in this operation. The number of columns of

the first matrix should be equal to the number of rows of the second matrix.

Two matrices are multiplied in the following manner:

We take the first row of first matrix and multiply it with the first column of the second

matrix. The multiplication is done in such a way that the first element of the row is

multiplied with the first element of the column, second element is multiplied with the

second element and so on. The results of all these multiplication operations are added to

produce one number. The resultant number is placed at the corresponding position (i.e. 1st

row 1st col in this case) in the resultant matrix.

Further the same first row is multiplied with the second column of the second matrix and

the resultant number is placed at intersecting position of first row and second column in

the resultant matrix. This process goes on till the last column of the second matrix.

Page 554

CS201 Introduction to Programming

Then comes the second row of first matrix and whole operation is repeated for this row,

this row is multiplied with all the columns of the second matrix. This process goes on till

the last row of the first matrix.

(1)(2)+(2)(1)

(1)(4)+(2)(2)

(5)(2)+(6)(1)

(5)(4)+(6)(2)

Note the resultant matrix is put on the left of the =. In Mathematics, this is put on right

but not to confuse your understanding with assignment concept in computer programs, it

is put on left.

If a matrix with order m rows, n columns is multiplied with another matrix of n rows and

p columns then the resultant matrix will have m rows and p columns. In the above

diagram, the first matrix has two rows and second matrix has two columns, therefore, the

resultant matrix has two rows and two columns.

Now comes the last operation, we are thinking of implementing i.e. Transpose of a

matrix. Transpose of a matrix is obtained by interchanging its rows and columns. How do

we interchange rows and columns for transposing the matrix? We take the first row of the

matrix and write it as a first column of the new matrix. The second row of the original

matrix is written as second column of the new matrix and similarly the last row of the

original matrix is written as last column of the new matrix. At the end of this operation,

when all rows of the original matrix are finished, we have new matrix as transpose of the

original matrix. There is no change in the size (order or number of rows and cols of a

matrix) of the transposed matrix when the original matrix is a square matrix. But when

the original matrix is not a square matrix, there is a change in the order of the transposed

matrix. The number of rows of the original matrix becomes the number of columns of the

transposed matrix and the number of columns of the original matrix becomes the number

of rows of the transposed matrix.

Until now in this problem analysis phase, we have analyzed the problem in order to

understand what are the matrices and what are their operations to be implemented. Now

at the next stage, we try to determine the followings:

- What are the constants to be used in our class?

- What are going to be the data structures to cater to the different sized matrices?

- How much memory is required and how it will be allocated?

Page 555

CS201 Introduction to Programming

What is going to be the interface of the class?

Design Issues and Class Interface

We want to specify the size of the matrix at creation time and allocate the memory for

that. So we don't see any use of constants inside our class named Matrix.

The size of the memory to be allocated is not going to be huge, as we are not catering to

the very huge sized matrices. Therefore, the memory for a matrix is going to be allocated

dynamically bluntly after the size of the matrix is specified in terms of rows and columns

without worrying about the size of the matrix.

For the interface of our Matrix class, we will declare a constructor that will accept integer

number of rows and columns of the matrix to be created as parameters.

Matrix ( int rows, int cols ) ;

The constructor function will be doing the memory allocation for the matrix.

As part of the interface, we will declare a display function inside our Matrix class that

will display the elements on the screen.

void display ( Matrix & );

To perform already discussed different operations on matrices, we need to overload

operators. For example to perform addition of two matrices, + operator will be

overloaded as a member function of the Matrix class. The + operator function will be

called for the Matrix object on the left of the + and the Matrix object on the right to it

will be passed as a parameter to it. This function will add the corresponding elements of

the both matrices and returns the resultant back.

Matrix operator + ( Matrix & ) const;

The same thing applies to the subtraction operation of two matrices.  operator function

will be overloaded for that as a member function of the Matrix class.

Matrix operator - ( Matrix & ) const;

The situation changes a bit, when we want to write the functions to cater to different

operations where both the operands are not matrix objects rather one of them is scalar.

For example, when we want to do the following operation:

A + x;

Where A is a matrix and x is a scalar.

Then we write a member function that accepts a scalar number as a parameter instead of a

Matrix object.

Page 556

CS201 Introduction to Programming

Matrix

operator + ( Scalar ) const;

The Scalar can be an int, double or float, that we will cover later.

But the situation is more different, when we want to perform the scalar addition operation

in the following manner:

x + A;

By now we should be clear that member function cannot be written to handle this

operation because there is a scalar number on the left of +. Therefore, we need to write a

friend operator function for this type of operation. The friend functions are non-members

and therefore, defined outside of the class.

friend Matrix operator + ( Scalar , Matrix & ) ;

Similarly, when a scalar is subtracted from a Matrix object like the following:

A - x;

A member function is written to cater to this operation.

Matrix operator - ( Scalar ) const;

But again, when a matrix is subtracted from a scalar number:

x - A;

Then we have to write a friend operator to handle this operation.

friend Matrix operator - ( Scalar , Matrix & ) ;

In order handle the multiplication operations of two Matrix objects like the following:

A * B;

A member operator * function is defined.

Matrix operator * ( const Matrix & ) ;

This operator is called for the Matrix object on the left of * and the object on the right is

passed as an argument. The function multiplies both the matrices and returns the resultant

matrix.

When a scalar is multiplied with a scalar like:

A * x;

Page 557

CS201 Introduction to Programming

The following member operator * handles this:

Matrix

operator * ( Scalar ) const;

But for operation like the following:

x *

following friend operator function is written:

friend Matrix operator * ( const Scalar , const Matrix & ) ;

For division operation like the following:

A / x;

A member operator / is overloaded as:

Matrix

operator / ( const Scalar );

Now we will talk about transpose of a matrix. For this operation, we will write a member

function transpose that will transpose the original matrix.

Matrix & transpose(void) ;

Now we are left with few more things to cover to complete the rudimentary interface of

our class Matrix.

Operators += and -= are overloaded as member operators. These composite operators

use the assignment operator ( = ).

We will also overload stream insertion and extraction operators as friend functions to our

Matrix class as follows:

friend ostream & operator << ( ostream & , Matrix & ) ;

friend istream & operator

>> ( istream & , Matrix & ) ;

So here is how we declare our Matrix class. The interface of the class is the public

methods of the class. Here is one important point to understand that what we are

concerned about here is the class interface and not about the program interface to the user

of the program. A programmer can develop user interface by writing his/her code while

using the class interface.

/* Declaration of the Matrix class. This class is containing the double type elements */

Page 558

CS201 Introduction to Programming

class Matrix

{

private:

int numRows, numCols;

double **elements;

public:

Matrix(int=0, int=0);

// default constructor

Matrix(const Matrix & );

// copy constructor

~Matrix();

// Destructor

int getRows(void) const;

// Utility fn, returns no. of rows

int getCols(void) const; // Utility fn, returns no. of columns

const Matrix & input(istream &is = cin); // Read matrix from istream

const Matrix & input(ifstream &is);

// Read matrix from istream

void output(ofstream &os) const;

// Utility fn, prints matrix with graphics

void output(ostream &os = cout) const; // Utility fn, prints matrix with graphics

const Matrix& transpose(void);

// Transpose the matrix and return a ref

const Matrix & operator = (const Matrix &m);

// Assignment operator

Matrix operator+( Matrix &m) const;

// Member op + for A+B; returns matrix

Matrix operator + (double d) const;

const Matrix & operator += (Matrix &m);

friend Matrix operator + (double d, Matrix &m);

Matrix operator-( Matrix & m) const;

// Member op + for A+B; returns matrix

Matrix operator - (double d) const;

const Matrix & operator -= (Matrix &m);

friend Matrix operator - (double d, Matrix& m);

Matrix operator*(const Matrix & m);

Matrix operator * (double d) const;

friend Matrix operator * (const double d, const Matrix& m);

Matrix operator/(const double d);

friend ostream & operator << ( ostream & , Matrix & );

friend istream & operator >> ( istream & , Matrix & );

friend ofstream & operator << ( ofstream & , Matrix & );

friend ifstream & operator >> ( ifstream & , Matrix & );

void display( ) ;

};

In the above declarations, we should note how we are passing and returning Matrix

objects. We are passing and returning the Matrix objects by reference because passing the

Page 559

CS201 Introduction to Programming

Matrix objects by value will be a overhead that will affect performance and more

memory will be allocated and de-allocated on stack.

Notice that we are doing dynamic memory allocation inside the constructor of the class.

You must be remembering that wherever the dynamic memory allocation is made, it has

to be freed explicitly. To de-allocate the memory, we will write code inside the destructor

of the class Matrix. The other consideration when we are allocating memory on free store

from within constructor is that the default assignment operator will not work here.

Remember, the default assignment operator makes shallow copy of the object members,

therefore, we will have to write our own assignment operator ( = ) in order to make deep

copy of the object data members. Remember that a copy constructor is called when a new

Matrix object is initialized and constructed based on an already existent Matrix object.

Therefore, we have to write our own copy constructor in order to make deep copy of the

object data members.

There is one very important point to mention about this class Matrix. A Matrix can be

composed of ints, floats or doubles as their elements. Instead of handling these data types

separately, we can write Matrix class as a template class and write code once for all

native data types. While writing this template class, the better approach to write will be,

to go with a simple data type (e.g. double) first to write a Matrix class and then extend it

to a template class later. Another thing that can be templatized in the Matrix class is the

Scalar number. Actually, this Scalar number can be an int, float or double; therefore, we

may also use a template for this.

We have to perform certain checks and make decisions inside the implementation of

member functions. For example, while writing the division operator member function, we

will check against the number that it should be non-zero. Before adding two matrices, we

will check for their number of rows and columns to be equal. Also in this exercise, we

have declared only one class Matrix to manipulate matrices. There are alternate

approaches to this. For example, we could declare a Row class first and then contain

multiple objects (same in number as number of rows required for the matrix object) of

Row class inside the Matrix class making a matrix of a certain size. To make it simple,

we have selected to manage matrices using only one class Matrix. The objective here is to

practice the already studied programming constructs as much as possible.

Page 560

Table of Contents: