ZeePedia Add to Favourites   |   Contact us


Introduction to Programming

<<< Previous Matrices, Design Recipe, Problem Analysis, Design Issues and Class Interface Next >>>
 
img
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
img
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:
1
2
3
4
A=
5
6
7
8
9
10
11
12
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
1
2
3
3
6
8
-2
-4
-5
5
6
7
7
4
7
-2
2
0
=
-
9
10
11
9
10
1
0
0
10
Page 553
img
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
img
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)
2
4
1
2
*
1
2
5
6
(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.
1
2
3
1
5
9
5
6
7
2
6
10
9
10
11
3
7
11
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
img
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
img
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
img
CS201 ­ Introduction to Programming
The following member operator * handles this:
Matrix
operator * ( Scalar ) const;
But for operation like the following:
x *
A;
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
img
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
img
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:
  1. What is programming
  2. System Software, Application Software, C language
  3. C language: Variables, Data Types, Arithmetic Operators, Precedence of Operators
  4. C++: Examples of Expressions, Use of Operators
  5. Flow Charting, if/else structure, Logical Operators
  6. Repetition Structure (Loop), Overflow Condition, Infinite Loop, Properties of While loop, Flow Chart
  7. Do-While Statement, for Statement, Increment/decrement Operators
  8. Switch Statement, Break Statement, Continue Statement, Rules for structured Programming/Flow Charting
  9. Functions in C: Structure of a Function, Declaration and Definition of a Function
  10. Header Files, Scope of Identifiers, Functions, Call by Value, Call by Reference
  11. Arrays: Initialization of Arrays, Copying Arrays, Linear Search
  12. Character Arrays: Arrays Comparisonm, Sorting Arrays Searching arrays, Functions arrays, Multidimensional Arrays
  13. Array Manipulation, Real World Problem and Design Recipe
  14. Pointers: Declaration of Pointers, Bubble Sort Example, Pointers and Call By Reference
  15. Introduction, Relationship between Pointers and Arrays, Pointer Expressions and Arithmetic, Pointers Comparison, Pointer, String and Arrays
  16. Multi-dimensional Arrays, Pointers to Pointers, Command-line Arguments
  17. String Handling, String Manipulation Functions, Character Handling Functions, String Conversion Functions
  18. Files: Text File Handling, Output File Handling
  19. Sequential Access Files, Random Access Files, Setting the Position in a File, seekg() and tellg() Functions
  20. Structures, Declaration of a Structure, Initializing Structures, Functions and structures, Arrays of structures, sizeof operator
  21. Bit Manipulation Operators, AND Operator, OR Operator, Exclusive OR Operator, NOT Operator Bit Flags Masking Unsigned Integers
  22. Bitwise Manipulation and Assignment Operator, Programming Constructs
  23. Pre-processor, include directive, define directive, Other Preprocessor Directives, Macros
  24. Dynamic Memory Allocation, calloc, malloc, realloc Function, Dangling Pointers
  25. History of C/C++, Structured Programming, Default Function Arguments
  26. Classes and Objects, Structure of a class, Constructor
  27. Classes And Objects, Types of Constructors, Utility Functions, Destructors
  28. Memory Allocation in C++, Operator and Classes, Structures, Function in C++,
  29. Declaration of Friend Functions, Friend Classes
  30. Difference Between References and Pointers, Dangling References
  31. Operator Overloading, Non-member Operator Functions
  32. Overloading Minus Operator, Operators with Date Class, Unary Operators
  33. Assignment Operator, Self Assignmentm, Pointer, Conversions
  34. Dynamic Arrays of Objects, Overloading new and delete Operators
  35. Source and Destination of streams, Formatted Input and Output, Buffered Input/Output
  36. Stream Manipulations, Manipulators, Non Parameterized Manipulators, Formatting Manipulation
  37. Overloading Insertion and Extraction Operators
  38. User Defined Manipulator, Static keyword, Static Objects
  39. Pointers, References, Call by Value, Call by Reference, Dynamic Memory Allocation
  40. Advantages of Objects as Class Members, Structures as Class Members
  41. Overloading Template Functions, Template Functions and Objects
  42. Class Templates and Nontype Parameters, Templates and Static Members
  43. Matrices, Design Recipe, Problem Analysis, Design Issues and Class Interface
  44. Matrix Constructor, Matrix Class, Utility Functions of Matrix, Input, Transpose Function
  45. Operator Functions: Assignment, Addition, Plus-equal, Overloaded Plus, Minus, Multiplication, Insertion and Extraction