Data Structures

UCS301

Array

Department of CSE
Thapar Institute of Engineering and Technology, Patiala
Array ADT float marks[10];

• The simplest but useful data structure.

• Assign single name to a homogeneous collection of
instances of one abstract data type.
– All array elements are of same type, so that a
pre−defined equal amount of memory is
allocated to each one of them.
• Individual elements in the collection have an
associated index value that depends on array
dimension.
Contd…
• One-dimensional and two-dimensional arrays are
commonly used.
• Multi−dimensional arrays can also be defined.

• Usage:
– Used frequently to store relatively permanent
collections of data.
– Not suitable if the size of the structure or the
data in the structure are constantly changing.
Memory Storage
Memory Storage – One Dimensional Array

int student[4]; student[0] student[2]

student[1] student[3]

float marks[3]; marks[0] marks[2]

marks[1]
Memory Storage – Two Dimensional Array

int marks[3][5];

• Can be visualized in the form of a matrix as

Col 0 Col 1 Col 2 Col 3 Col 4
Row 0 marks[0][0] marks[0][1] marks[0][2] marks[0][3] marks[0][4]
Row 1 marks[1][0] marks[1][1] marks[1][2] marks[1][3] marks[1][4]
Row 2 marks[2][0] marks[2][1] marks[2][2] marks[2][3] marks[2][4]
Contd…
• Row-major order
(0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,2) (1,3) (1,4) (2,0) (2,1) (2,2) (2,3) (2,4)

Row0 Row1 Row2

• Column-major order
(0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) (0,3) (1,3) (2,3) (0,4) (1,4) (2,4)

Col0 Col1 Col2 Col3 Col4

Array Address Computation
1D array – address calculation
• Let A be a one dimensional array. B 100
• Formula to compute the address of the
Ith element of an array (A[I]) is: [0] 1 W
Address of A[I] = B + W * ( I – LB ) [1] 2
where,
B = Base address/address of first element, i.e. A[LB].
[2] 3
W = Number of bytes used to store a single array [3] 4
element.
I = Subscript of element whose address is to be [4] 5
found. [5] 6
LB = Lower limit / Lower Bound of subscript, if not
specified assume 0 (zero).
1D array – address calculation
• Let A be a one dimensional array. B 100
• Formula to compute the address of the
Ith element of an array (A[I]) is: [0] 1 W
Address of A[I] = B + W * ( I – LB ) [1] 2
Given:
B = 100, W = 4, and LB = 0
[2] 3
[3] 4
A[0] = 100 + 4 * (0 – 0) = 100
[4] 5
[5] 6
1D array – address calculation
• Let A be a one dimensional array. B 100
• Formula to compute the address of the
Ith element of an array (A[I]) is: [0] 1 100

Address of A[I] = B + W * ( I – LB ) [1] 2 104

Given: 108
[2] 3
B = 100, W = 4, and LB = 0
[3] 4 112
A[1] = 100 + 4 * (1 – 0) = 104
[4] 5 116
A[2] = 100 + 4 * (2 – 0) = 108
[5] 6 120
A[3] = 100 + 4 * (3 – 0) = 112
A[4] = 100 + 4 * (4 – 0) = 116
A[5] = 100 + 4 * (5 – 0) = 120
Example – 1
• Similarly, for a character array where a single
character uses 1 byte of storage.
• If the base address is 1200 then,
Address of A[I] = B + W * ( I – LB )
Address of A[0] = 1200 + 1 * (0 – 0) = 1200
Address of A[1] = 1200 + 1 * (1 – 0) = 1201
…
Address of A[10] = 1200 + 1 * (10 – 0) = 1210
Example – 2
• If LB = 5, Loc(A[LB]) = 1200, and W = 4.
• Find Loc(A[8]).
Address of A[I] = B + W * ( I – LB )
Loc(A[8]) = Loc(A[5]) + 4 * (8 – 5)
= 1200 + 4 * 3
= 1200 + 12
= 1212
Example – 3
• Base address of an array B[1300…..1900] is 1020
and size of each element is 2 bytes in the memory.
Find the address of B[1700].
Address of A[I] = B + W * ( I – LB )
• Given: B = 1020, W = 2, I = 1700, LB = 1300
Address of B[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * 400
= 1020 + 800
= 1820
 [0] [1] [2] [3]

Row-major 1 [0] 1 2 3 4 1 Column-major

2 [1] 5 6 7 8 5
3 [2] 9 10 11 12 9
4 2
5 6
6 10
7 3
8 7
9 11
10 4
11 8
12 12
2D Array – Address Calculation
• If A be a two dimensional array with M rows and N
columns. We can compute the address of an element at Ith
row and Jth column of an array (A[I][J]).
B = Base address/address of first element, i.e. A[LBR][LBC]
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Number of bytes used to store a single array element
LBR = Lower limit of row/start row index of matrix, if not given
assume 0
LBC = Lower limit of column/start column index of matrix, if not
given assume 0
N = Number of column of the given matrix
M = Number of row of the given matrix
 [0] [1] [2] [3]

Row-major 1 [0] 1 2 3 4
M=3
2 [1] 5 6 7 8
N=4
3 [2] 9 10 11 12
4
5
6 Address of A[2][1] =
7 B + W * (4 * (2 – 0) + (1 – 0))
8
9
10 Address of A[I][J] =
11 B + W * ( N * ( I – LBR ) + ( J – LBC ))
12
 [0] [1] [2] [3]

[0] 1 2 3 4 1 Column-major
M=3
[1] 5 6 7 8 5
N=4
[2] 9 10 11 12 9
2
Address of A [2][1] = 6
10
B + W * ((2 – 0) + 3 * (1
(2 – 0))
3
7
11
Address of A [I][J] = 4
B + W * ((I – LBR) + M * (J – LBC)) 8
12
Contd…
• Row Major
Address of A[I][J] = B + W * ( N * ( I – LBR ) + ( J – LBC ))

• Column Major
Address of A [I][J] = B + W * (( I – LBR ) + M * ( J – LBC ))

• Note: A[LBR…UBR, LBC…UBC]

M = (UBR – LBR) + 1
N = (UBC – LBC) + 1
Example – 4
• Suppose elements of array A[5][5] occupies 4 bytes, and
the address of the first element is 49. Find the address
of the element A[4][3] when the storage is row major.
Address of A[I][J] = B + W * ( N * ( I – LBR ) + ( J – LBC ))
• Given: B = 49, W = 4, M = 5, N = 5, I = 4, J = 3, LBR = 0,
LBC = 0.
Address of A[4][3] = 49 + 4 * (5 * (4 – 0) + (3 - 0))
= 49 + 4 * (23)
= 49 + 92
= 141
Example – 5
• An array X [-15…10, 15…40] requires one byte of storage. If
beginning location is 1500 determine the location of
X [0][20] in column major.
Address of A[I][J] = B + W * [ ( I – LBR ) + M * ( J – LBC ) ]
• Number or rows (M) = (UBR – LBR) + 1 = [10 – (- 15)] +1 = 26
• Given: B = 1500, W = 1, I = 0, J = 20, LBR = -15, LBC = 15, M = 26

Address of X[0][20] = 1500 + 1 * [(0 – (-15)) + 26 * (20 – 15)]

= 1500 + 1 * [15 + 26 * 5]
= 1500 + 1 * [145]
= 1645
Example – 6
• A two-dimensional array defined as A [-4 … 6] [-2 … 12] requires 2 bytes of
storage for each element. If the array is stored in row major order form
with the address A[4][8] as 4142. Compute the address of A[0][0].
Address of A[I][J] = B + W (N ( I – LBR ) + ( J – LBC ))
• Given:
W = 2, LBR = –4, LBC = –2
#rows = M = 6 + 4 + 1 = 11 #columns = N = 12 + 2 + 1 = 15
Address of A[4][8] = 4142
• Address of A[4][8] = B + 2 (15 (4 – (–4)) + (8 – (–2)))
4142 = B + 2 (15 (4 + 4) + (8 + 2)) = B + 2 (15 (8) + 10) = B + 2 (120 + 10)
4142 = B + 260
Thus, B = 4142 – 260 = 3882
• Now, Address of A[0][0] = 3882 + 2 (15 (0 – (–4)) + (0 – (–2)))
= 3882 + 2 (15(4) + 2) = 3882 + 2 (62)
= 3882 + 124
= 4006
Array Basic Operations
Operations on Linear Data Structures
• Traversal
• Search – Linear and Binary.
• Insertion
• Deletion
• Sorting – Different algorithms are there.
• Merging – During the discussion of Merge Sort.
 TRAVERSAL

Processing each element in the array.

Example – Print all the array elements.
Algorithm arrayTraverse(A,n)
Input: An array A containing n integers.
Output: All the elements in A get printed.
1. for i = 0 to n-1 do
2. Print A[i]

1. int arrayTraverse(int arr[], int n)

2. {
3. for (int i = 0; i < n; i++)
4. cout << "\n" << arr[i];
5. }
Example – Find minimum element in the array.

Algorithm arrayMinElement(A,n)
Input: An array A containing n integers.
Output: The minimum element in A.
1. min = 0
2. for i = 1 to n-1 do
3. if A[min] > A[i] 1. int arrayMinElement(int arr[], int n)
4. min = i 2. { int min = 0;
5. return A[min] 3. for (int i = 1; i < n; i++)
4. { if (arr[i] < arr[min])
5. min = i;
6. }
7. return arr[min];
8. }
 Search

Find the location of the element with

a given value.
Linear Search
• Used if the array is unsorted.
• Example:
Search 7 in the following array
i 0 1 2 3 4 5 6
Found at
a[] 10 5 1 6 2 9 7 8 3 4 index 6

Search 11 in the following array

i 0 1 2 3 4 5 6 7 8 9 10
a[] 10 5 1 6 2 9 7 8 3 4 Not found
Contd…
Algorithm linearSearch(A,n,num)
Input: An array A containing n integers and number
num to be searched.
Output: Index of num if found, otherwise -1.
1. for i = 0 to n-1 do
2. if A[i] == num
3. return i
1. int linearSearch(int a[], int n, int num)
4. return -1
2. { for (int i = 0; i < n; i++)
3. if (a[i] == num)
4. return i;
5. return -1;
6. }
Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
 Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Example: Find 9
3 5 7 8 9 12 15
 Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Example: Find 9
3 5 7 8 9 12 15
 Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Example: Find 9
3 5 7 8 9 12 15
 Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Example: Find 9
3 5 7 8 9 12 15
 Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Example: Find 9
3 5 7 8 9 12 15
 Binary search
Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1 subarray.
3. Combine: Trivial.
Example: Find 9
3 5 7 8 9 12 15
Pseudo Code of Binary Search
 Insertion
Insert an element in the array

Deletion
Delete an element from the array
Insertion and Deletion
0 1 2 3 4 5 6 7 8 9
a[] 8 6 3 4 5
• Insert 2 at index 1
4 3 2 1
0 1 2 3 4 5 6 7 8 9
a[] 8 6 3 4 5
2 6 3 4 5
• Delete the value at index 2
1 2 3
0 1 2 3 4 5 6 7 8 9
a[] 8 2 6 3 4 5
3 4 5
Algorithm – Insertion
Algorithm insertElement(A,n,num,indx)
Input: An array A containing n integers and the
number num to be inserted at index indx.
Output: Successful insertion of num at indx.
1. for i = n – 1 to indx do
2. A[i + 1] = A[i]
1. void insert(int a[], int num, int pos)
3. A[indx] = num 2. { for(int i = n-1; i >= pos; i--)
4. n = n + 1 3. a[i+1] = a[i];
4. a[pos] = num;
5. n++;
6. }
Algorithm – Deletion
Algorithm deleteElement(A,n,indx)
Input: An array A containing n integers and the index
indx whose value is to be deleted.
Output: Deleted value stored initially at indx.

1. temp = A[indx]
2. for i = indx to n – 2 do
1. int deleteElement(int a[], int pos)
3. A[i] = A[i + 1] 2. { int temp = a[pos];
4. n=n–1 3. for(int i = pos; i <= n-2; i++)
4. a[i] = a[i+1];
5. return temp 5. n--;
6. return temp;
7. }
Bubble Sort
Bubble Sort – Ascending

[0]
8 1 1 1 1 1 1 1
[1] 1 8 7 7 7 7
5 5
2 2
[2] 7 7 8 5 5 5
7
2 2
5 5
[3] 5 5 5 8 2 2
7 7 7
[4] 2 2 2 2 8 8 8 8
Pass 1st 2nd 3rd 4th
Bubble Sort – Descending

[0]
8 8 8 8 8 8 8 8
[1] 1 1 1 7 7 7 7 7
[2] 7 7 7 1 1 5 5 5
[3] 5 5 5 5 5 1 2 2
[4] 2 2 2 2 2 2 1 1
Pass 1st 2nd 3rd 4th
Algorithm – Bubble Sort
Algorithm bubbleSort(A,n)
Input: An array A containing n integers.
Output: The elements of A get sorted in increasing order.
1. for i = 1 to n – 1 do

2. for j = 0 to n – i – 1 do

3. if A[j] > A[j + 1]

4. Exchange A[j] with A[j+1]

In all the cases, complexity is of the order of n2.

Optimized Bubble Sort?

[0]
5 1 1 1 1 1
[1] 1 5 2 2 2 2
[2] 2 2 5 3 3 3
[3] 3 3 3 5 4 4
[4] 4 4 4 4 5 5
Pass 1st 2nd
Algorithm – Optimized Bubble Sort
Algorithm bubbleSortOpt(A,n)
Input: An array A containing n integers.
Output: The elements of A get sorted in increasing order.
1. for i = 1 to n – 1 The best case
2. flag = true complexity reduces
3. for j = 0 to n – i – 1 do to the order of n,
4. if A[j] > A[j + 1] but the worst and
5. flag = false average is still n2.
6. Exchange A[j] with A[j+1] So, overall the
7. if flag == true complexity is of the
8. break; order of n2 again.
Sparse Matrix
Sparse Matrix
• A matrix is sparse if many of its elements are zero.
• A matrix that is not sparse is dense.
• Two possible representations
– Array (also known as triplet) 0 0 0 2
0 6 0 0
– Linked list
0 0 0 9
0 5 4 0
Array representation
Row Col Value
[0] [1] [2] [3] [4] [5]
6 6 8
[0] 15 0 0 22 0 -15 0 0 15
[1] 0 11 3 0 0 0 0 3 22
0 5 -15
[2] 0 0 0 -6 0 0
1 1 11
[3] 0 0 0 0 0 0 1 2 3
[4] 91 0 0 0 0 0 2 3 -6
4 0 91
[5] 0 0 28 0 0 0
5 2 28
Operations
• Transpose
• Addition
• Multiplication
 Transpose

Row Col Value Row Col Value Row Col Value

6 6 8 6 6 8 6 6 8
0 0 15 0 0 15 0 0 15
0 3 22 3 0 22 0 4 91
0 5 -15 5 0 -15 1 1 11
1 1 11 1 1 11 2 1 3
1 2 3 2 1 3 2 5 28
2 3 -6 3 2 -6 3 0 22
4 0 91 0 4 91 3 2 -6
5 2 28 2 5 28 5 0 -15
Original Column Major Row Major
Addition
[0] [1] [2] [3] [4] [5] [0] [1] [2] [3] [4] [5]
[0] 15 0 0 22 0 -15 [0] 15 0 0 0 91 0
[1] 0 11 3 0 0 0 [1] 0 11 0 0 0 0
[2] 0 0 0 -6 0 0 [2] 0 3 0 0 0 28
[3] 0 0 0 0 0 0
+ [3] 22 0 -6 0 0 0
[4] 91 0 0 0 0 0 [4] 0 0 0 0 0 0
[5] 0 0 28 0 0 0 [5] -15 0 0 0 0 0

[0] [1] [2] [3] [4] [5]

[0] 30 0 0 22 91 -15
[1] 0 22 3 0 0 0
0 3 0 -6 0 28
= [2]

[3] 22 0 -6 0 0 0
[4] 91 0 0 0 0 0
[5] -15 0 28 0 0 0
 Row Col Value
Addition Counter = 14
6 6 14
0 0 30
0 3 22
Row Col Value Row Col Value 0 4 91
6 6 8 6 6 8 0 5 -15
0 0 15 0 0 15 1 1 22
0 3 22 0 4 91 1 2 3
0 5 -15 1 1 11 2 1 3
1 1 11 2 1 3 2 3 -6
1 2 3 2 5 28 2 5 28
3 0 22
2 3 -6 3 0 22
3 2 -6
4 0 91 3 2 -6
4 0 91
5 2 28 5 0 -15
5 0 -15
5 2 28
Multiplication
• Compute A x B
• First take transpose of B.
• Multiply only if the corresponding elements are
present and add them for each position in the
resultant matrix.
Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0]

[1] 0 0 0 0
× [1] 0 0 0 23
= [1]

[2] 0 0 5 0 [2] 0 0 9 0 [2]

[3] 15 12 0 0 [3] 20 25 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240
[1] 0 0 0 0
× [1] 0 0 0 23
= [1]

[2] 0 0 5 0 [2] 0 0 9 0 [2]

[3] 15 12 0 0 [3] 20 25 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300
[1] 0 0 0 0
× [1] 0 0 0 23
= [1]

[2] 0 0 5 0 [2] 0 0 9 0 [2]

[3] 15 12 0 0 [3] 20 25 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0
[1] 0 0 0 0
× [1] 0 0 0 23
= [1]

[2] 0 0 5 0 [2] 0 0 9 0 [2]

[3] 15 12 0 0 [3] 20 25 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1]

[2] 0 0 5 0 [2] 0 0 9 0 [2]

[3] 15 12 0 0 [3] 20 25 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0
[2] 0 0 5 0 [2] 0 0 9 0 [2]

[3] 15 12 0 0 [3] 20 25 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0]

[1] 0 0 0 0
× [1] 0 0 0 25
= [1]

[2] 0 0 5 0 [2] 8 0 9 0 [2]

[3] 15 12 0 0 [3] 0 23 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0] 240
[1] 0 0 0 0
× [1] 0 0 0 25
= [1]

[2] 0 0 5 0 [2] 8 0 9 0 [2]

[3] 15 12 0 0 [3] 0 23 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0] 240 300
[1] 0 0 0 0
× [1] 0 0 0 25
= [1]

[2] 0 0 5 0 [2] 8 0 9 0 [2]

[3] 15 12 0 0 [3] 0 23 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0] 240 300 0
[1] 0 0 0 0
× [1] 0 0 0 25
= [1]

[2] 0 0 5 0 [2] 8 0 9 0 [2]

[3] 15 12 0 0 [3] 0 23 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 25
= [1]

[2] 0 0 5 0 [2] 8 0 9 0 [2]

[3] 15 12 0 0 [3] 0 23 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 25
= [1] 0
[2] 0 0 5 0 [2] 8 0 9 0 [2]

[3] 15 12 0 0 [3] 0 23 0 0 [3]

Multiplication
[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 8 0 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 23
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 0 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 20 25 0 0 [3] 0 0 120 276

[0] [1] [2] [3] [0] [1] [2] [3] [0] [1] [2] [3]
[0] 0 10 0 12 [0] 0 0 0 20 [0] 240 300 0 230
[1] 0 0 0 0
× [1] 0 0 0 25
= [1] 0 0 0 0
[2] 0 0 5 0 [2] 8 0 9 0 [2] 0 0 45 0
[3] 15 12 0 0 [3] 0 23 0 0 [3] 0 0 120 276
Multiplication Counter = 0
Row Col Value Row Col Value Row Col Value
4 4 5 4 4 5 4 4
0 1 10 0 3 20
0 3 12 1 3 25
2 2 5 2 0 8
3 0 15 2 2 9
3 1 12 3 1 23
Row Col Value
4 4 5
0 2 8
1 3 23
2 2 9
3 0 20
3 1 25
Multiplication Counter = 6

Row Col Value Row Col Value Row Col Value

4 4 5 4 4 5 4 4 6
0 1 10 0 3 20 0 0 240
0 3 12 1 3 25 0 1 300
2 2 5 2 0 8
0 3 230
3 0 15 2 2 9
2 2 45
3 1 12 3 1 23
3 2 120
[0] [1] [2] [3]
3 3 276
[0] 240 300 0 230
[1] 0 0 0 0
[2] 0 0 45 0
[3] 0 0 120 276