ARRAYS
- CONSTANT ACCESS
- BIG O COMPLEXITY
- DRY RUNNING OF 2D ARRAY
- PRACTICE QUESTIONS
Engr. Dr. Sidra Sultana
WHAT IS ARRAY?
Contiguous area of memory consisting of equal-size
elements indexed by contiguous integers
WHAT IS SPECIAL ABOUT ARRAYS?
Constant time access
● To read
● To write
array_addr+elem_size*(i-first_index)
=1000+8*(6-0)
=1048
CALCULATING THE ADDRESS OF ANY ELEMENT IN THE 1-D ARRAY:
EXAMPLE 1:
Given the base address of an array
A[1300 ………… 1900] as 1020
and the size of each element is 2 bytes in the memory,
find the address of A[1700].
SOLUTION
Given:
Base address B = 1020
Lower Limit/Lower Bound of subscript LB = 1300
Storage size of one element store in any array W = 2 Byte
Subset of element whose address to be found I = 1700
Formula used:
Address of A[I] = B + W * (I – LB)
Solution: Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820
MULTI-DIMENSIONAL ARRAYS (ARRAY OF AN ARRAY)
ROW MAJOR VS COLUMN MAJOR
Row Major: array_addr + elem_size*((i-first_index)*N + (j-first_index))
Column Major: array_addr + elem_size*((i-first_index) + (j-first_index)*M)
CALCULATE THE ADDRESS OF ANY ELEMENT IN THE 2-D ARRAY:
EXAMPLE 2:
Given an array, arr[1………10][1………15] with base
value 100 and the size of each element is 1 Byte in
memory. Find the address of arr[8][6] with the help of
row-major order.
SOLUTION
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
= 15 – 1 + 1
= 15
Formula: Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
Solution: Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
3-D ARRAY:
A 3-Dimensional array is a collection of 2-Dimensional arrays.
It is specified by using three subscripts:
● Block size
● Row size
● Column size
More dimensions in an array mean more data can be stored in
that array.
3-D ARRAY
CALCULATE THE ADDRESS OF ANY ELEMENT IN THE 3-D ARRAY:
To find the address of any element in 3-Dimensional
arrays there are the following two ways-
● Row Major Order
● Column Major Order
ROW MAJOR ORDER
Address of A[i][j][k] = B + W *(M * N(i-x) + N *(j-y) + (k-z))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width
EXAMPLE 3:
Given an array, arr[1:9, -4:1, 5:10] with a base value of
400 and the size of each element is 2 Bytes in memory
find the address of element arr[5][-1][8] with the help
of row-major order?
SGiven:
OLUTION
Row Subset of an element whose address to be found I = 5
Column Subset of an element whose address to be found J = -1
Block Subset of an element whose address to be found K = 8
Base address B = 400
Storage size of one element store in any array(in Byte) W = 2
Lower Limit of row/start row index of matrix x = 1
Lower Limit of column/start column index of matrix y = -4
Lower Limit of blocks in matrix z = 5
M(row) = Upper Bound – Lower Bound + 1 = 9 – 1 + 1 = 9
N(Column)= Upper Bound – Lower Bound + 1 = 1 – (-4) + 1 = 6
Formula used:
Address of[I][J][K] =B + W (M * N(i-x) + N *(j-y) + (k-z))
Solution:
Address of arr[5][-1][8] = 400 + 2 * {[9 * 6 * (5 – 1)] + 6 * [(-1 + 4)]} + [8 – 5]
= 400 + 2 * (9*6*4)+(6*3)+3
= 400 + 2 * (237)
= 874
COLUMN MAJOR ORDER
Address of A[i][j][k]= B + W(M * N(i – x) + M *(k – z) + (j – y))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width
EXAMPLE 4:
Given an array arr[1:8, -5:5, -10:5] with a base value of
400 and the size of each element is 4 Bytes in memory
find the address of element arr[3][3][3] with the help
of column-major order?
SOLUTION
Given:
Row Subset of an element whose address to be found I = 3
Column Subset of an element whose address to be found J = 3
Block Subset of an element whose address to be found K = 3
Base address B = 400
Storage size of one element store in any array(in Byte) W = 4
Lower Limit of row/start row index of matrix x = 1
Lower Limit of column/start column index of matrix y = -5
Lower Limit of blocks in matrix z = -10
M (row)= Upper Bound – Lower Bound + 1 = 8-1+1 = 8
N (column)= Upper Bound – Lower Bound + 1 = 5 +5 + 1 = 11
Formula used:
Address of[i][j][k] = B + W(M * N(i – x) + M * (j-y) + (k – z))
Solution:
Address of arr[3][3][3] = 400 + 4 * ((8*11*(3-1)+8*(3-(-5)+(3-(-10)))
= 400 + 4 * ((88*2 + 8*8+13)
= 400 + 4 * (253)
= 400 + 1012
= 1412
EXAMPLE 5:
1. (2,1,1)
2. (1,2,1)
3. (1,1,2)
4. None of above
TIMES FOR COMMON OPERATIONS
BIG O COMPLEXITY
● Constant time access to any element
● Constant time to add/remove at the end
● Linear time to add and remove from any arbitrary
location.
DRY RUNNING OF 2D ARRAYS
#include <iostream>
int main() {
int a[2][2] = {{1,2},{3,4}};
int i,j;
for (i = 0; i<2 ; i++){
for (j = 0 ; j<2 ; j++)
{
std::cout <<a[i][j] << " ";
}
std::cout<< std::endl;
}
return 0;
}
ARRAY PROGRAMS
● Addition
● Subtraction
● Multiplication
