FDS

Unit 2

Linear Data Structure using Sequential Organization

2.1 Concept of Sequential Organization

Sequential organization

 The physical order during which the records are placed within the file
determines the sequence of records.
  The relationships among records within the file don't change, except that the
file is often extended. There are not any keys. Both the files including database
files and files available on device can have sequential organization.
 Each record within the file, except the primary, features a unique predecessor
record, and every record, except the last, also features a unique successor record.
 In data structures, a knowledge structure is claimed to possess sequential access
if one can only visit the values it contains in one particular order. The canonical
example is that the linked list. Indexing into an inventory that has sequential access
requires O(n) time, where n is that the index.
 Sequential access is a term defined as a bunch of elements (such as data during a
memory array or a computer file or on magnetic tape data storage) being accessed
during a predetermined, ordered sequence.
 It’s the other of random access, the power to access an arbitrary element of a
sequence as easily and efficiently as the other at any time.
 Sequential access is usually the sole way of accessing the info , for instance if
it's on a tape
 It’s going to even be the access method of choice, for instance if all that's
wanted is to process a sequence of knowledge elements.
 As a result of sequential access, many sorting and searching algorithms like
quicksort and binary search may degenerate into bad algorithms that are even less
 efficient than their naive alternatives; these algorithms are impractical without
random access.
 The write and skim of records during a physical instead of a logical sequence.

 On the opposite hand, some algorithms, typically people who don't have index,
require only sequential access, like mergesort, and face no penalty.

2.2 Overview of Array

Array

Element: Every item stored in an array is termed as a component

Index: each memory location of a component in an array is denoted by a numerical

index which is used for identifying the element

The array could also be a fixed-size sequenced collection of variables belonging to

the same data types. The array has adjacent memory locations to store values.
Since the array provides a convenient structure for representing data, it falls under
the category of the data structures in C.

The syntax for declaring array are:

Data_typearray_name [array_size];

•        An array may be a container of elements.

•        Elements have a selected value and data type, like "ABC", TRUE or FALSE,
etc.

•        Each element also has its own index, which is employed to access the element.

•        Elements are stored at contiguous memory locations.

•        An index is usually but the entire number of array items.

•        In terms of syntax, any variable that's declared as an array can store multiple
values.

•        Most languages have an equivalent comprehension of arrays but have

alternative ways of declaring and initializing them.
 Three parts will always remain common altogether the initializations, i.e., array
name, elements, and thus the info kind of elements.

•        Array name: necessary for straightforward regard to the gathering of elements

•        Data Type: necessary for type checking and data integrity

•        Elements: these are the info values present in an array

Why can we need arrays?

 Here, are some reasons for using arrays:

 Arrays are best for storing multiple values during a single variable

 Arrays are better at processing many values easily and quickly

 Sorting and searching the values is simpler in arrays

2.3 Array as an Abstract Data Type

Arrays are defined as ADT’s because they're capable of holding contiguous

elements within the same order. And that they permitaccess for the precise element
via index or position.

They are abstract because they will be String, int or Person

int[] arrA = new int[1];

String[] arrB = new String[1];

Person[] arrC = new Person[3]; // where Person is treated as a defined class

Advantages

 Fast, random access of things or elements.

 Very memory efficient, little or no memory is required aside from that needed to
store the contents.

Disadvantages
  Slow insertion and deletion of elements

 Array size must be known when the array is made and is fixed (static)

2.4 Operations on Array

Basic operations in array

There is some specific operation which can be performed or people that are
supported by the array. These are:

 Traversing: It prints all the array elements one after another.

 Inserting: It adds a component at given index.

 Deleting: it's wont to delete a component at given index.

 Searching: It searches for an element(s) using given index or by

value.

 Updating: it's wont to update a component at given index

Array representation

Array can be represented as

int array[10]={10,20,11,30,40,39,23,12,34,16};

•        int represents data type

•        array represents name of array

•        [10] indicates size of array

•        {------} inside this parenthesis there are elements of array

10 20 11 30 40 39 23 12 34 16

elements

index                  0      1      2     3     4      5       6      7      8     9

•        For an array
•        Index always start with 0

•        Array length is 10 so it can store 10 elements

•        Each element can be accessed with its index.

•        Like an element at index 5 is 39.

Size of data types may differ for different data types in array

S no Data type Size (default value)

1 bool False
2 char 0
3 int 0
4 float 0
5 double 0.0f
6 void  
7 wchar_t 0

 Traversing – this function is to traversing through the elements of

array.

2.     Inserting- Insert operation is used to insert one or more data elements into an
array. Based on thenecessary requirement, a new element can be added at the
beginning, end, or any given index of array.

3.     Deleting -Deletion refers to removing an existing element from the array and re-
organizing all elements of an array.

•        Algorithm: - Consider LA is a linear array with N elements and K

is a positive integer such that K<=N. Following is the algorithm to
delete an element available at the Kth position of LA.
                      Start

                      Set J = K

                      Repeat steps 4 and 5 while J < N

                      Set LA[J] = LA[J + 1]

                       Set J = J+1

                      Set N = N-1

                      Stop

4.     Searching- search operation is used to perform a search for an array element

based on its value or its index.

•        Algorithm: - Consider LA is a linear array with N elements and K

is a positive integer such that K<=N. Following is the algorithm to
find an element with a value of ITEM using sequential search
                      Start

                      Set J = 0

                      Repeat steps 4 and 5 while J < N

                      IF LA[J] is equal ITEM THEN GOTO STEP 6

                      Set J = J +1

                      PRINT J, ITEM

                      Stop

5.     Updating - Update operation refers to updating an existing element from the

array at a given index.

•        Algorithm: -Consider LA is a linear array with N elements and K

is a positive integer such that K<=N. Following is the algorithm to
update an element available at the Kth position of LA.
                      Start

                      Set LA[K-1] = ITEM

                      Stop

2.5 Merging of two arrays

 Input: arr1 [] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8}

Output: arr3 [] = {1, 2, 3, 4, 4, 5, 6, 8}

Input: arr1 [] = { 5, 8, 9}, arr2[] = {4, 7, 8}

Output: arr3 [] = {4, 5, 7, 8, 8, 9}

Method 1

•        Create an array arr3[] of size n1 + n2.

•        Copy all n1 elements of arr1[] to arr3[]

•        Traverse arr2[] and one by one insert elements (like insertion sort) of arr3[] to
arr1[]. This step take O(n1 * n2) time.

•        Time complexity   O(n1 * n2)

•        Space complexity   O(1)

Method 2

•        The idea is to use Merge function of Merge sort.

•        Create an array arr3[] of size n1 + n2.

•        Simultaneously traverse arr1[] and arr2[].

•        Pick smaller of current elements in arr1[] and arr2[], copy this smaller element
to next position in arr3[] and move ahead in arr3[] and the array whose element is
picked.

•        If there are remaining elements in arr1[] or arr2[], copy them also in arr3[].

•        Time complexity O(n1 + n2)

•        Space complexity  O(n1 + n2)

Time Complexity: O(n1 + n2)

Auxiliary Space: O(n1 + n2)

 

 
 

2.6 Advantages and Disadvantages of Arrays

Advantages and drawbacks of Arrays

Advantages

 Reading /parsing an array element is simple and efficient. As shown within the above
table, the read time of array is O(1) in both best and worst cases. This is often because
any element are often instantly read using indexes (base address calculation behind the
scene) without traversing the whole array.

 Array could also be a foundation of other data structures. For instance other data
structures like LinkedList, Stack, Queue etc. are implemented using array.

 All the weather of an array are often accessed employing one name (array name) in
conjunction with the index, which is readable, user-friendly and efficient rather than
storing those elements in different-2 variables.

Disadvantages

 While using array, we must need to make the selection of the size of the array within
the start, so if we aren't aware what percentage elements we are becoming to store in
array, it'd make the task difficult.

 The size of the array is fixed so if at later point; if we'd wish to store more elements in
it then it can’t be done. On the other hand, if we store less number of elements than the
declared size, the remaining allocated memory is wasted.

2.7 Storage Representation and their Address Calculation: Row major and
Column Major

One Dimensional Array

•        Simplest arrangement that creates use of computed address to locate its elements is that the
one dimensional array or vector; number of memory locations is sequentially allocated to the
vector

•        A vector size is fixed and thus requires a hard and fast number of memory locations.

•        Vector A with subscript boundary of “one” is represented as below….

•        L0 is that the address of the primary word allocated to the primary element of vector A.

•        C words are allocated for every element or node

•        For a given equation the address of A is  Loc (Ai) = L0 + C (i-1)

•        Let’s consider the more general case of representing a vector A whose boundary for its
subscript is given by some variable b.

•        For a given equation the location of A is Loc (Ai) = L0 + C (i-b)

An array can be stored in many ways

Array A=  [  a  a      a      ]

11      12  13

 [ a  a 21       22         a      ]

23

 Array could be stored in possible ways

 
Index Row major Column major
0 A11 A11

1 A12    A21 

2 A13      A12
 3 A21  A 22

4 A22    A 13

5 A23    A 23

Different programming languages handles array in different ways.

•        In C programming , multidimensional arrays are stored in row-major order, and the
array indexes are written row-first (lexicographical access order):

C: row-major order (lexicographical access order), zero-based indexing

Index Value  Access

0 A11 A[0][0]
1 A12    A[0][1]
2 A13     A[0][2]
3 A21  A[1][0]
4 A22    A[1][1]
5 A23    A[1][2]

•        Address of [I, J]th element in row-major = B + W[C(I – Kr) + (J – Kc)]

•        In Fortran, arrays are stored in column-major order, while the array indexes are still
written row-first (colexico graphical access order):

Fortran: column-major order (colexographical access order), one-based indexing

Index Value  Access

1 A11 A[1][1]
2 A21    A[2][1]
3 A12     A[1][2]
4 A22  A[2][2]
5 A13    A[1][3]
6 A23    A[2][3]

•        Address of [I, J]th element in column-major = B + W[R(J – Kc) + (I – Kr)]

•        Where  :
 •        B is the base address (address of the first block in the array).

•        W is the width in bytes (size in bytes for each block in the array).

•        Kr is the index of the first row.

•        Kc is the index of the first column.

•        R is the total number of rows.

•        C is the total number of columns.

2.8 Multidimensional Arrays: Two-dimensional arrays, n-dimensional

arrays.

Two Dimensional Array

•        Two dimensional arrays also are called table or matrix, two dimensional arrays have two
subscripts

•        Two dimensional array during which elements are stored column by column is named as
column major matrix

•        Two dimensional array during which elements are stored row by row is named as row major
matrix

•        First subscript denotes number of rows and second subscript denotes the amount of columns

•        Two dimensional array consisting of two rows and 4 columns as above Fig is stored
sequentially by columns : A [ 1, 1 ], A [ 2 , 1 ], A [ 1 , 2 ], A [ 2 , 2 ], A [ 1 , 3 ], A [ 2 , 3 ], A
[ 1, 4 ], A [ 2, 4 ]

•        The address of element A [ i , j ] are often obtained by expression Loc (A [ i , j ]) = L0 + (j-
1)*2 + i-1 generally for 2 dimensional array consisting of n rows and m columns the address
element A [ i, j ] is given by Loc (A [ i , j ]) = L0 + (j-1)*n + (i – 1)

•        In row major matrix, array are often generalized to arbitrary lower and boundary in its
subscripts, assume that b1 ≤ I ≤ u1 and b2 ≤ j ≤u2

 
  

For row major matrix: Loc (A [ i , j ]) = L0 + ( i – b1 ) *(u2-b2+1) + (j-b2)

Applications of Array
 Symbol Manipulation (matrix representation of polynomial equation)

 Sparse Matrix

2.9           Concept of Ordered List

Ordered list

•        The structure of an ordered list is a collection of items where each item holds a relative
position that is based upon some underlying characteristic of the item.

•        The ordering is typically either ascending or descending and we assume that list items have a
meaningful comparison operation that is already defined.

•        Many of the ordered list operations are the same as those of the unordered list.

•        OrderedList() creates a new empty ordered list. It doesn’t require any parameters and returns

an empty list.

•        add(item) adds a new item to the list making sure that the order is preserved. It needs the
item and returns nothing. Assume the item is not already in the list.

•        remove(item) removes the item from the list. It needs the item and modifies the list. Assume
the item is present in the list.

•        search(item) searches for the item in the list. It needs the item and returns a boolean value.

•        isEmpty() tests to see whether the list is empty. It needs no parameters and returns
a boolean value.

•        size() returns the number of items in the list. It needs no parameters and returns an integer.
•        index(item) returns the position of item in the list. It needs the item and returns the index.
Assume the item is in the list.

•        pop() removes and returns the last item in the list. It needs nothing and returns an item.
Assume the list has at least one item.

•        pop(pos) removes and returns the item at position pos. It needs the position and returns the
item. Assume the item is in the list.

Array and ordered list

S Array Ordered list 

no
1 An array is a contiguous segment of The structure of an ordered list is a collection
memory, and a list is just a bunch of of items where each item holds a relative
nodes, each one has the pointers to position that is based upon some underlying
the "next" node (and also to the characteristic of the item. The ordering is
"previous" node, in the case of typically either ascending or descending and
bidirectional lists). we assume that list items have a meaningful
comparison operation that is already defined.
2 Arrays efficiently - in O(1) - support Lists, on the other hand, do not support
random access (i.e. by arbitrary given efficient random access (while supporting
index i), efficient consecutive traversal)
3 Deleting/inserting an element into an Inserting and deleting is fast - O(1).
array is slow - O(n), because you
have to move all elements after
deleting/inserting element
4 In the array, you have to shuffle other it is possible to add items to a particular point
entries around; in a list, you simply in the list more swiftly than it is possible to
adjust appropriate pointers in at most add a new item in an array at an equivalent
3 elements point
5 Access to the N  item takeO(1) time
th
Access to the N  item in a list takes O(N)
th

for an array. time

6 The items in an array are not The items in a list  are always  arranged in
necessarily in any particular order any particular order
7 With arrays, you can do random access Performance wise, maintaining an ordered list
of a member in O(1), while this takes is pretty expensive: O(N) insert, delete, but
O(N) in an list. you can do searches faster than O(N) (using
something like binary search)
 

2.10 Single Variable Polynomial: Representation using arrays, Polynomial

as array of structure, Polynomial addition, Polynomial multiplication.

 
 Symbol Manipulation using Array

•        We will use array for various quite operations in polynomial equation like addition,
subtraction, division, differentiation etc…

•        We have an interest find suitable representation for polynomial in order that different
operations like addition, subtraction etc… are often performed in efficient manner

•        Array are often used to represent Polynomial equation

•        Matrix Representation of Polynomial equation

•        Once we've algorithm for converting the polynomial equation to an array representation and
another algorithm for converting array to polynomial equation, then different operations in
array (matrix) are going to be  corresponding operations of polynomial equation

Storing of polynomial in an array

Eg :- for a polynomial p1= 5x  +10x  -11x  +12x+18

6 3 2

Representing power of x 0 1 2 3 4 5 6 7
Element 18 12 -11 10 0 0 5 0
index 0 1 2 3 4 5 6 7
  

Array will be represented as A={18, 12,-11,10,0,0,5}

•        the coefficient 18 is in slot 0 of the array (representing 18x^0)

•        the coefficient 12 is in slot 1 of the array (representing 12x^1)

•        the coefficient -11 is in slot 2 of the array (representing11x^2)

•        the coefficient 10 is in slot 3 of the array (representing 10x^3)

•        the coefficient 5 is in slot 6 of the array (representing 5x^6)

Advantage

 Only good for non-sparse polynomials

 Ease of storage and retrieval

Disadvantage 

•        Have to allocate size ahead of time

•        Huge array size required for sparse polynomials waste of space and runtime.

•        This polynomial representation in array is not good for higher degrees of polynomial .

•        Array representation cost too much memory to be wasted for higher degree of polynomial

•        Will consume too much time for searching element and wasting too much memory that used
for allocation .]

•        Foreg.  for a polynomial like p=5x  +15x  +10x  -11x  +12x4+18

34 19 13 8

•        Or for higher degree polynomial 50x  +100x  -141x  +112x+18

6000 3000 200

For a polynomial p=6x  +10x  -11x  +12x+18

50 3 2

•        polynomial = new array(50)  // I'm assuming all elements initialize to zero

•        polynomial[50] = 6

•        polynomial[3] = 10

•        polynomial[2] = -11

•        polynomial[1] = 12
•        polynomial[0] = 18

The basic idea of polynomial addition is to add coefficient parts of the polynomials having
same exponent.

Polynomial addition

A polynomial is an expression that contains quite two terms. A term is formed from
coefficient and exponent.

Example: P(x) = 4x3+6x2+7x+9

A polynomial could also be represented using array or structure. A structure could also be
defined such it contains two parts – one is that the coefficient and second is that the
corresponding exponent. The structure definition could also be given as shown below:

Structpolynomial{

int coefficient;

int exponent;

};

Algorithm: adding polynomial using structures

AddPoly(Struct Poly p1[10], Struct Poly p2[10], int t1,int t2,Struct Poly p3[10])

 [Initialize segment variables]

[Initialize Counter] Set i=0,j=0,k=0

2.     Repeat step 3 while i<t1 and j<t2

If p1[i].expo=p2[j].expo, then

3.     p3[i].coeff=p1[i].coeff+p2[i].coeff

p3[k].expo=p1[i].expo

[Increase counter] Set i=i+1,j=j+1,k=k+1

else if p1[i].expo > p2[j].expo, then

p3[k].coeff=p1[i].coeff

p3[k].expo=p1[i].expo
 [Increase counter] Set i=i+1,k=k+1

else

p3[k].coeff=p2[j].coeff

p3[k].expo=p2[j].expo

Set j=j+1,k=k+1

[End of If]

[End of loop]

4.     Repeat while i<t1

p3[k].coeff=p1[i].coeff

p3[k].expo=p1[i].expo

Set i=i+1,k=k+1

[End of loop]

5.     Repeat while j<t2

p3[k].coeff=p2[j].coeff

p3[k].expo=p2[j].expo

Set j=j+1,k=k+1

[End of loop]

6.     Return k

7.     Exit

Adding polynomial using array

Addition of polynomial is easy as compared to multiplication

add (A[0..m-1], B[0..n01])

1)     Create a sum array sum[] of size equal to maximum of 'm' and 'n'

2)     Copy A[] to sum[].

3)     Traverse array B[] and do following for every element B[i]

4)     sum[i] = sum[i] + B[i]

5)     Return sum[].

Example:

Input:  A [] = {5, 0, 10, 6}   similar to Pa =6x +10x +5

3 2

B [] = {1, 2, 4}   similar to Pb =4x +2x+1

2

Output:  sum [] = {6, 2, 14, 6} similar to Psum= 6x +14x +2x+6

3 2

Example 2

P1=1x +5x +3x+2

3 2

P2=5x +8x+7
2

Padd=1x +10x +11x+9

3 2

Enter the highest degree of polynomial 1 = 3

Enter the coeff of x^0 =2

Enter the coeff of x^1 =3

Enter the coeff of x^2 =5

Enter the coeff of x^3=1

Enter the highest degree of polynomial2=2

Enter the coeff of x^0 =7

Enter the coeff of x^1 =8

Enter the coeff of x^2 =5

Expression 1 = 2.0+ 3.0x^1+ 5.0x^2+ 1.0x^3

Expression 2 = 7.0+ 8.0x^1+ 5.0x^2

Expression after addition = 9.0+ 11.0x^1+ 10.0x^2+ 1.0x^3

Time complexity
 Time complexity of adding two polynomial  O(m+n)

 where m and n are orders of two given polynomials.

Multiplication of Two Polynomial

Multiplication of two polynomials however requires manipulation of each node such that the
exponents are added up and the coefficients are multiplied.  After each term of first
polynomial is operated upon with each term of the second polynomial, then the result has to
be added up by comparing the exponents and adding the coefficients for similar exponents
and including terms as such with dissimilar exponents in the result

Algorithm:

multiply(A[0..m-1], B[0..n01])

1)     Create a product array prod[] of size m+n-1.

2)     Initialize all entries in prod[] as 0

3)     Traverse array A[] and do following for every element A[i]

 Traverse array B[] and do following for every element B[j]

  prod[i+j] = prod[i+j] + A[i] * B[j]

4)     Return prod[].

A simple solution is to one by one consider every term of first polynomial and multiply it
with every term of second polynomial.

Example:-

Input:  A [] = {5, 0, 10, 6}   similar to Pa =6x +10x +5

3 2

B [] = {1, 2, 4}   similar to Pb =4x +2x+1

2

Output: prod [] = {5, 10, 30, 26, 52, 24}

Similar toPmul= 24x +52x +26x +30x +10x+5

5 4 3 2

p1=4x +3x+2
2

p2=2x +7x +6x+5

3 2

pmul= 2x +28x +18x+10

3 2

Enter the highest degree of polynomial1= 2

 Enter the coeff of x^0 = 2

Enter the coeff of x^1 = 3

Enter thecoeff of x^2 =4

Enter the highest degree of polynomial 2 = 3

Enter the coeff of x^0 = 5

Enter the coeff of x^1 = 6

Enter the coeff of x^2 = 7

Enter the coeff of x^3 = 2

Expression 1 = 2.0+ 3.0x^1+ 4.0x^2

Expression 2 = 5.0+ 6.0x^1+ 7.0x^2+ 2.0x^3

Expression after multiplication = 10.0+ 18.0x^1+ 28.0x^2+ 2.0x^3

2.11 Sparse Matrix: Sparse matrix representation using array, Sparse

matrix addition, Transpose of sparse matrix- Simple and Fast Transpose,
Time and Space tradeoff

Sparse matrix
 Sparse matrix is amatrix in which most of the elements are zero

•        An mXn matrix is claimed to be sparse if “many” of its elements are zero.

•        By contrast if most of the elements are non zero then the matrix is considered as ‘dense’ .

•        Sparcity of a sparse matrix is the number of zero valued element divided by total number of
elements

•        We can device a simple representation scheme whose space requirement equals the size of
the nonzero elements.

 Example:-
•        The non-zero entries of a sparse matrix could also be mapped into a linear list in row-major
order.

•        for instance the non-zero entries of 4X8 matrix of below

•        in row major order are 2, 1, 6, 7,3, 9, 8, 4, 5

Figure   A 4 x 4 matrix

Figure, Linear Representation of above matrix

•        To construct matrix structure we need to record

(a)  Original row and columns of every non zero entries

(b) No of rows and columns within the matrix

 
 •        So each element of the array into which the sparse matrix is mapped need to have
three fields: row, column and value

•        A corresponding amount of time is saved creating the linear list representation over
initialization of two dimension array.

•        Here from 6X7=42 elements, only 10 are non zero. A[1,3]=6, A[1,5]=9, A[2,1]=2, A[2,4]=7,
A[2,5]=8, A[2,7]=4, A[3,1]=10, A[4,3]=12, A[6,4]=3, A[6,7]=5.

•        One basic method for storing such a sparse matrix is to store non-zero elements in one
dimensional array and to spot each array elements with row and column indices
  

•        A more efficient representation in terms of storage requirement and access time to the row of
the matrix is shown in fid (d). The row vector changed in order that its ith element is that
the index to the primary of the column indices for the element in row I of the matrix.

Linked Representation of Sparse matrix

Typical node to represent non-zero element is

Figure:-linked representation of sparse matrix

Transpose of sparse matrix

 To Transpose a matrix, we will simply change every column value to the row value and vice-versa,

 However, during this case, the resultant matrix won’t be sorted as we require.
 Hence, we initially determine the number of elements less than the current element’s column being
inserted in order to get the exact index of the resultant matrix where the current element should be
placed.

 This is done by maintaining an array index[] whose ith value indicates the number of elements in

the matrix less than the column i.

Algorithm for Transpose of Sparse Matrix

SparseMatrixSparseMatrix::Transpose()

Construct a SparseMatrix, b(cols, rows, terms);

If (terms > 0)

 {

Let rowSize be an integer array of size cols.

Let rowStart be an integer array of size cols.
Initialize each element in rowSize to 0.
For (i=0; i
 rowSize [smArray[i].col]++;
rowStart [0] = 0;
For (i = 1; i< cols; i++)
rowStart [i] = rowSize [i-1] + rowStart [i-1];
For (i=0; i< terms; i++) {
j = rowStart [ smArray [i].col ];
Copy smArray[ i ] to smArray[ j ];
Interchange row and col of smArray[ j ];
rowStart [ smArray [i].col ]++;

}
}
Return b;
}

Multiplication of sparse matrix

 To Multiply the matrices, we first calculate transpose of the second matrix to simplify our
comparisons and maintain the sorted order.

 So, the resultant matrix is obtained by traversing through the whole length of both matrices and
summing the acceptable multiplied values.

 Any row value adequate to x within the first matrix and row value adequate to y within the second
matrix (transposed one) will contribute towards result[x][y].
 This is obtained by multiplying all such elements having col value in both matrices and adding
only those with the row as x in first matrix and row as y within the second transposed matrix to urge
the result[x][y].

Multiplying Sparse Matrices

  1 void    mm_mul_sa (sa_t *A, sa_t *B, sa_t *C)

  2 {

  3          inti, j, k;

  4          int sum;

  5 

  6          for (i = 0; i< A->num_rows; i++) {

  7                  for (j = 0; j < B->num_cols; j++) {

  8                          sum = 0;

  9                          for (k = 0; k < A->num_cols; k++) {

 10                                  sum += saGet (A,i,k) * saGet (B,k,j);

 11                          }

 12                          saSet (C,i,j,sum);

 13                  }

 14          }

15  }

Row Col Val      Row Col Val

1   2   10       1   1   2

1   3   12       1   2   5

2   1   1        2   2   1

2   3   2        3   1   8

The resulting matrix after multiplication will be obtained as follows:

Transpose of second matrix:

Row Col Val      Row Col Val

1   2   10       1   1   2

1   3   12       1   3   8

2   1   1        2   1   5

2   3   2        2   2   1

Summation of multiplied values:

result[1][1] = A[1][3]*B[1][3] = 12*8 = 96

result[1][2] = A[1][2]*B[2][2] = 10*1 = 10

result[2][1] = A[2][1]*B[1][1] + A[2][3]*B[1][3] = 2*1 + 2*8 = 18

result[2][2] = A[2][1]*B[2][1] = 1*5 = 5

Any other element cannot be obtained by any combination of row in

Matrix A and Row in Matrix B.

Hence the final resultant matrix will be:

Row Col Val

1   1   96

1   2   10

2   1   18 

Matrix operations

Matrix 1: (4x4)
Row ColumnValue

1   2       10

1   4       12

3   3       5

4   1       15

4   2       12

Matrix 2: (4X4)

Row Column Value

1   3       8

2   4       23

3   3       9

4   1       20

4   2       25

Output:

Result of Addition: (4x4)

Row Column Value

1   2      10

1   3      8

1    4       12

2    4      23

3   3      14

4   1      35

4   2      37

Result of Multiplication: (4x4)

Row Column Value

1   1      240

1   2      300

1   4      230

3   3      45

4   3      120

4   4      276

Result of transpose on the first matrix: (4x4)

Row Column Value

1   4      15

2   1      10

2   4      12

3   3      5

4   1      1

Time Complexity

 Addition operation of sparse matrix  has time complexity of, hence, has a time complexity of O(n),

 Addition operation traverses the matrices linearly

 where n is the number of non-zero elements in the larger matrix amongst the
two.
 Transpose of sparse matrix has a time complexity of  O(n+m)

 Where n is the number of columns and m is the number of non-zero elements in

the matrix
 During worst case when matrix is not a sparse matrix  T(n)=O(m^2*n),

 where 'm' is the length of the first array and

  'n' is the length of the second array and with the optimization,

  We can reduce it by a constant K where K is the no of zero's in the matrix A.

 Multiplication of sparse matrix has a time complexity of O(x*n + y*m),

 where (x, m) is number of columns and terms in the second matrix;

 and (y, n) is number of rows and terms in the first matrix.