## CS13002 Programming and Data Structures | ## Section: 4/D, Spring 2005 |

## Assignment 8

A matrix is said to be sparse if each row of it contains only few non-zero entries. Such sparse matrices occur in many situations. For example, a complicated machine may have one million components, but each component interacts with at most one hundred other components. So the interaction matrix, though million-by-million in size, has at most one hundred non-zero entries in each row and can be rightfully dubbed sparse.

In order to store a sparse matrix, it suffices to store for each row only the column indices where non-zero entries occur and also the corresponding entries. This reduces the space overhead associated with the storage. For the example in the last paragraph, a complete million-by-million array requires space for storing one trillion (10

^{12}) entries, whereas a sparse representation is capable of storing the same matrix in a space for only one hundred million (10^{8}) entry-index pairs.Define a suitable dynamic two-dimensional array type to represent a sparse matrix. Notice that each row is now to be allocated exactly the space required to store only the non-zero entries and the corresponding column indices.

Write a function that takes as input the dimension

nof a square matrix and a limitlon the number of non-zero entries in each row. The function should output a sparse matrix with integer entries such that the number of non-zero entries in each row is a random integer between1andl. Also the column indices occupied by these non-zero entries should be chosen randomly between0andn-1. You may restrict each non-zero entry to an integer value between 1 and 9.Write a function that takes as input two sparse matrices in your representation and stores in the first matrix the sum of the two input matrices again in your sparse format. Notice that if the input matrices have at most

lnon-zero entries in each row, the sum of these matrices can have at most2lnon-zero entries in each row. So iflis substantially smaller thann, then the output matrix may also be called sparse. You may passlas a parameter to this function. You should free unused memory while changing the first matrix.Write a function that prints a sparse matrix. Printing should also be sparse, i.e., each row is to be printed as a list of entry-index pairs.

Report the output of your program on matrices with dimension

n = 10and non-zero entry limitl = 5. Such a matrix is not really sparse. But for easy debugging and our checking of your output, it is desirable to play with small matrices.

Sample outputThe following data corresponds to the parameters

n = 8andl = 4.Matrix A Row 0 : ( 9, 3) Row 1 : ( 6, 0) ( 6, 3) ( 1, 5) Row 2 : ( 7, 2) ( 1, 3) ( 4, 4) ( 5, 5) Row 3 : ( 2, 1) ( 5, 2) ( 8, 3) ( 2, 5) Row 4 : ( 1, 1) ( 5, 5) ( 1, 6) Row 5 : ( 8, 1) ( 5, 4) ( 2, 5) ( 5, 7) Row 6 : ( 8, 1) ( 8, 4) ( 4, 7) Row 7 : ( 7, 0) ( 8, 1) ( 4, 4) Matrix B Row 0 : ( 6, 0) ( 9, 3) ( 1, 4) Row 1 : ( 9, 1) ( 2, 6) Row 2 : ( 5, 0) ( 8, 3) ( 7, 6) Row 3 : ( 5, 4) Row 4 : ( 2, 2) ( 3, 5) ( 3, 6) Row 5 : ( 2, 0) ( 9, 7) Row 6 : ( 7, 2) ( 5, 6) Row 7 : ( 7, 0) ( 1, 1) ( 7, 5) ( 8, 7) Matrix A+B Row 0 : ( 6, 0) (18, 3) ( 1, 4) Row 1 : ( 6, 0) ( 9, 1) ( 6, 3) ( 1, 5) ( 2, 6) Row 2 : ( 5, 0) ( 7, 2) ( 9, 3) ( 4, 4) ( 5, 5) ( 7, 6) Row 3 : ( 2, 1) ( 5, 2) ( 8, 3) ( 5, 4) ( 2, 5) Row 4 : ( 1, 1) ( 2, 2) ( 8, 5) ( 4, 6) Row 5 : ( 2, 0) ( 8, 1) ( 5, 4) ( 2, 5) (14, 7) Row 6 : ( 8, 1) ( 7, 2) ( 8, 4) ( 5, 6) ( 4, 7) Row 7 : (14, 0) ( 9, 1) ( 4, 4) ( 7, 5) ( 8, 7)