Module Objective

An array is linear list in coded form. It is a structure used to store data of similar
type in static manner. In this module we will learn various types of array, their
indexing formulas . We will also learn various operation of 1 D & 2 D Array.

1
References

⮚ “Fundamentals of data structure in C” Horowitz, Sahani & Freed, Computer

Science.
⮚ “Fundamental of Data Structure” ( Schaums Series)
⮚ Robert Kruse, Data Structures and Program Design , Prentice Hall, 1984

2
Introduction to Array
 Array

An Array is a Data Structure which can be defined as a finite ordered

set of Homogenous elements

4
Question:

What is an array?

A. An array is a series of elements of the same B.An array is a series of element

type in contiguous memory locations

D. None of the mentioned C. An array is a series of elements of the same type

placed in non-contiguous memory locations

5
Properties of Array

Finite means fixed element , Arrays have a fixed size where the size of the
array is defined when the array is declared. In the below given figure, the
size of the array is fixed i.e., the size 5 is fixed and we cannot add one more
element in the array

6
Properties of Array

Ordered Set means every number will be in Sequence and will be denoted
by numbers called Index (“indices” in plural) or ”subscript.

7
Properties of Array

Homogenous elements means Data type of all the elements will be same

8
Properties of Array

Contiguous Memory allocation

9
Properties of Array

Random Access,

The general syntax to access an element is: <name_of_array>[<index>]

10
Continued...

There are 3 types of indexing provided by different languages to access the array.

0 (zero-based indexing): The first element of the array is indexed by a subscript 0. The index
of nth element is “n-1” in this case. (C, C++, etc.).

1 (one-based indexing): The first element of the array is indexed by the subscript 1. (Basic,
MATLAB, R, Mathematica

n (n-based indexing): The base index of an array can be freely chosen. Usually, programming
languages allowing n-based indexing also allow negative index values. (Fortran, Pascal,
ALGOL, etc.)

11
Types Of Array

The array is represented in various ways based on the number of

dimensions

1. One-Dimensional array
2. Two-Dimensional array
3. Multi-Dimensional array

12
One-Dimensional Array

A one-dimensional array (or single dimension array) is an array with one subscript only.

Declaration of one-dimensional array

Syntax:
<Data Type> <Arrayname> [<Array_Size>]

Example:

Declaration of one-dimensional array "A" having "int" data type and size 10 elements
in C.
int A[10]

13
One-Dimensional Array

Accessing the element in one-dimensional array

Accessing its elements involves a single subscript.

Syntax: Arrayname[index]
Example:
To access 2nd element in the array A, we write A[1]
To access 9th element in the array A, we write A[8]
(Here, we that assume the first index is 0)

14
Memory Representation of One-Dimensional Array

The memory representation of one-dimensional array is shown in below diagram.

In the above diagram A[0], A[1], A[2],. . . , A[9] are the array elements. The address
mentioned for these elements represent the physical location of data elements in the main
memory. It is assumed that each element requires 4 bytes for storage in this scenario.
15
Question:

A one dimensional array is always considered as____?

A. Complex B. Sequential

D. Both C and B C. Linear

16
Question:

int main() What is the output of C Program with arrays?

{
A. 0 0 B. -1 -1
static int ary[ ] = {1, 3, 5};
printf("%d %d", ary[-1], ary[5]);
return 0; D. None of the above C. Compile error
}

17
Question:

What is the index number of the last element of an array with 9 elements?
A. 9 B. 8

D. Programmer-defined C. 0

18
Question:

Which of the following gives the memory address of the first element in array?
A. array[0]; B. array[1];

D. array; C. array(2);

19
Two-Dimensional Array

A two-dimensional array (2-D array) has two subscripts. The elements are stored in the form of rows and
columns. It can also be termed as an array of one-dimensional arrays.
Matrix is an example of two-dimensional array

20
 Continued...

Declaration the two-dimensional array:

Syntax: <Data Type> <Arrayname> [m][n]

Where,

m = Number of rows

n = Number of columns

Example: Declaration of two-dimensional array “A” having “int” datatype and row size 6 and column size 5.
int A[6][5]

21
Continued...

Accessing the element in two-dimensional array

Accessing its elements involves two subscripts; one for row and second for column.

Syntax:
Arrayname[ row_index][column_index]

Example:
To access 2nd element of 1st row in the array A, we write A[0][1]

22
Memory Representation of Two-Dimensional Array

There are two-ways by which the 2D array elements can be represented in Memory.

a) Row Major

b) Column Major

23
Row Major Representation

In row-major order, storage of the elements in the memory is row-wise i.e. storage of elements of first row is
followed by the storage of elements of second row and so on so forth.

24
Column-major Representation

In column-major order, elements are stored column wise i.e., storage of elements of the first column followed
by storage of second column elements and so on so forth.

25
Three-Dimensional Array

When an array is represented in the form of 3 different dimensions, it is called 3-D Array. It can also be called
as an array of 2-dimensional arrays.

3-Dimensional array which has 3 dimensions named U1, U2, and U3.

26
Continued...

Declaration of three-dimensional array:

Syntax: <Data Type> <Arrayname> [m][n][o]

Where,

m = 1st Dimension

n = 2nd Dimension

o = 3rd Dimension

Example: Declaration of three-dimensional array “A” having “int” datatype with first dimension size 6, second
dimension size 5, third dimension size 4.
int A[6][5][4]

If the array is declared as A[3][4][5], it will have a total of 3 x 4 x 5 = 60 elements.

27
Continued...

Accessing the element in three-dimensional array

Accessing its elements involves three subscripts, one for each dimension.

Syntax: Arrayname[index1][index2][index3]

28
Memory Representation of Three-Dimensional Array

Memory Representation in Row Major Order

Here, the first dimension is considered as row.

(Here, we assume the first index for row and column is 0)

In the similar way Column major order arrangement can be done.

29
Question:

int main()
{ What is the output of C Program with arrays?
int ary[2][2][3] = { A. 1 11 B. 1 12
{{1,2,3},{4,5,6}},
{{7,8,9},{10,11,12}} D. Compile Error C. 2 13
};
int *p;
p = &ary;
printf("%d %d",*p, *p+11);
return 0;
}

30
Question:

Given A [1:15], bytes per cell = 3, base address = 1000 find the address of A [9].

A. 1022 B. 1021

D. 1024 C. 1023

31
Question:

If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element occupies 2 bytes then
the array has been stored in _________ order.

A. row major B. column major

D. None of these C. matix major

32
Question:

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?
A. 12 B. 210

D. 200 C. 120

33
Question:

Consider the following declaration of a ‘two-dimensional array in C:

char a[100][100];
Assuming that the main memory is byte-addressable and that the array is stored
starting from memory address 0, the address of a[40][50] is:
A. 4040 B. 4050

D. 5080 C. 5040

34
Question:

Which of the following expressions accesses the (i,j)th entry of an (m x n) matrix stored in column
major form?
A. n x (i -1) + j B. m x(j -1) + i

D. m x (n-j) + j C. n x(m-i) + j

35
Question:

The smallest element of an array’s index is called its

A. lower bound B. upper bound

D. extraction C. range

36
Question:

Given an array [ 1..8, 1..5, 1..7 ] of integers. Calculate address of element A[5,3,6], by using rows
and columns methods, if BA=900?

A. 1120 B. 1122

D. 1123 C. 1121

37
Question:

Given an array [ 1..8, 1..5, 1..7 ] of integers. Calculate address of element A[5,3,6], by using rows
and columns methods, if BA=900?

A. 1120 B. 1122

D. 1123 C. 1121

38
Question:

Given an array arr[1:8, -5:5, -10:5] with base value 400 and 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?

A. 4676 B. 4670

D. 4696 C. 4690

39
Question:

If more than one subscript is used, an array is known as a__________.

A. One- dimensional array B. Single dimensional array

D. None of the above C. Multi- dimensional array

40
Question:

The memory address of fifth element of an array can be calculated by the formula

A. LOC(Array[5]=Base(Array)+w(5-lower B. LOC(Array[5])=Base(Array[5])+(5-lower
bound), where w is the number of words per bound), where w is the number of words per
memory cell for the array memory cell for the array

D. None of above C. LOC(Array[5])=Base(Array[4])+(5-Upper

bound), where w is the number of words per
memory cell for the array

41
Index Formula Derivation for Array

One Dimensional Array

Index Formula Derivation in One Dimensional Array

Suppose there is a one-dimensional array A[L : U]

Number of elements /lengths of the array can be found

by the formula N = U – L + 1

Where U = Upper Bound of the array (Last index)

L = Lower Bound of the array (First index)

A[0:9] will contain 9-0+1 =10 elements

43
Index Formula Derivation in One Dimensional Array

 To find the address of ith index element, we will take two

assumptions
▪ Assumption 1: 1 Byte storage for each element.
▪ Assumption 2: First element is at index 1.

44
 Index Formula Derivation in One Dimensional Array

 Assume base address of an array = α.

 So
⮚ address of A[1]= α //address of 1st element of array A as given.
⮚ address of A[2]= α +1 //address of 2nd element of array A is address of base
address + no. of bytes i.e.1 (α +1)
⮚ address of A[3]= α +2 //address of 3rd element of array A is address of 2nd element
+ no. of bytes i.e.1 (α +1+1)
⮚ address of A[4]= α +3 //address of 4th element of array A is address of 3rd element
+ no. of bytes i.e.1 ((α +1+1+1)
⮚ address of A[i]= α + (i-1) ………………. (equation 1)

45
 Index Formula Derivation in One Dimensional Array

Step 2: Removal of first assumption i.e., 1 Byte storage for each element.
⮚ An element can take ‘n’ number of bytes depending upon the datatype
⮚ A[i]= α +(i-1)………………. (equation 1)
⮚ A[i]= α +(i-1) *n ………………. (equation 2)

Step 3: Removal of 2nd Assumption, i.e. First element is at index 1

 If index starts from L then, for some ith index element distance from first index will be i-L+1.

46
Index Formula Derivation in One Dimensional Array

⮚ Address of A[i]= α +(i-1) *n //As given in equation 2.

⮚ Replacing i with i-L+1

⮚ Address of A[i] = α + (i-L+1-1) *n
⮚ So, Address of A[i] = α +(i-L) *n
Address of A[i] = Base Address +n*(i – Lower Bound)

47
Index Formula Derivation in One Dimensional Array

Question 1: Given A [-1:10], bytes per cell = 4, base address = 2000 find
the address of A [7].
Solution:
Here, i = 7
n= 4
Lower Bound = -1
Upper Bound = 10
Address of A [i] = Base Address +n*(i-Lower Bound)
Address of A [7] = 2000 + 4*(7-(-1)) = 2032

48
Index Formula Derivation in One Dimensional Array

Question 2:Given A [1:15], bytes per cell = 3, base address = 1000 find
the address of A [9].
Solution:
Here, i = 9
n= 3
Lower Bound = 1
Upper Bound = 15
Address of A [i] = Base Address +n*(i-Lower Bound)
Address of A [9] = 1000 + 3*(9 - 1) = 1024

49
Index Formula Derivation in One Dimensional Array

Question 3: Why does indexing in most of the languages start with 0?

Solution:
In address calculation we can skip the offset value. E.g. A[10] =
{1,2,3,4,5,6,7,8,9,10}. If we start the indexing with 1, calculation of address of A[5]
= 1000+(5-1)*2
If we start the indexing with 0, calculation of address of A[5] = 1000+(5-0) *2. This
can directly be written as 1000+5*2. In this case, we do not need to perform the
additional arithmetic operation i.e. subtraction.
(5-1) in the above computations is known as extra subtraction or offset value.

50
Index Formula Derivation for Array

Two-Dimensional Array
Row Major Order Arrangement

⮚ Suppose we have a 2–D

array A[L1:U1, L2:U2] given as
shown:

⮚ Row side indices are L1, L1+1,

L1+2, …, U1–1, U1.
⮚ Column side indices are L2,
L2+1, L2+2, …, U2–1, U2.

52
Row Major Order Arrangement

⮚ In memory it will look like 1-D array as it will be stored row-wise.

53
Row Major Order Arrangement

⮚ For simplicity, we will assume that the first index is 1 and each
element requires 1 byte for storage. The array becomes A[1:U1,
1:U2].

If the base address of array is α then,

Address of A[1,1] = α
Address of A[1,2] = α + 1
Address of A[1,3] = α + 2
Address of A[1,4] = α + 3
…
Address of A[1, U2] = α + (U2 – 1)

54
Row Major Order Arrangement

Address of A[2,1] = α + ( U2 – 1) + 1
Address of A[2,1] = α + U2
Address of A[3,1] = α + U2 + U2
Address of A[3,1] = α + 2 U2
…
Address of A[i, 1] = α + (i – 1)*U2
Address of A[i,2] = α + (i – 1)*U2 +1
Address of A[i,3] = α + (i – 1)*U2 +2
…
Similarly, A[i, j] = α + (i – 1)*U2 + (j – 1)

55
Row Major Order Arrangement

Now, let us remove the assumption that every element takes 1 byte of storage with
n bytes for storage. So, the formula will change to

Address of A[i, j] = α +[(i – 1)*U2 + (j – 1)]*n

56
Row Major Order Arrangement

Now, remove the assumption that first index is 1 in row and column with L1 and
L2, respectively. Replacing U2 as U2 – L2 +1 (length formula), i with i – L1 + 1 and
j with j – L2 + 1

Address of A [i, j] = α + [(i – L1 + 1 – 1)*( U2 – L2 + 1) + (j – L2 + 1 – 1)] *n

Address of A [i, j] = α + [(i – L1)*( U2 – L2 + 1) + (j – L2)] *n

57
Can you answer these questions?

Suppose a 2D array A is declared as A[–2:2 , 2:6], words per cell = 4, base

address = 200. Consider Row major order arrangement.
⮚ A) Find out length of each dimension and the number of elements in array.
⮚ B) Find the location of A[1,2]

58
 Solution

By formula:
Here Lower Bound of row(L1) = –2 A[i, j] = Base address + [(i – L1)*( U2 – L2 + 1)
Here Upper Bound of row(U1) = 2 + (j – L2)] *n
Here Lower Bound of column(L2) = 2
Here Upper Bound of column(U2) = 6
A[1, 2]= 200 + [(1 – (–2) * (6 – 2 + 1) + (2 –
n=4
2)] * 4
Length of row = U1 – L1 + 1
= 2 – (–2) + 1 = 5
= 200 + 15* 4
Length of column = U2 – L2 + 1 = 260
= 6 – 2 + 1 =5
No. of elements = 5*5 = 25

59
 Column Major Order Arrangement

⮚ Suppose we have a 2–D array A[L1:U1,

L2:U2] given as shown:
⮚ Row side indices are L1, L1+1, L1+2, …,
U1–1, U1.
⮚ Column side indices are L2, L2+1, L2+2,
…, U2–1, U2.

60
 Column Major Order Arrangement

In memory it will look like 1-D array as it will be stored Column-wise.

61
Column Major Order Arrangement

For simplicity, we will assume that the first index is 1 and each element
requires 1 byte for storage. The Array becomes A[1:U1, 1:U2]. Another
assumption: every element requiring 1 byte for storage. So that, address of
first element say:
If the base address of array is α then,
Address of A[1,1] = α
Address of A[2,1] = α + 1
Address of A[3,1] = α + 2
Address of A[4,1] = α + 3
…
Address of A[U1,1] = α + (U1 – 1)

62
Column Major Order Arrangement

Address of A[1,2] = α + ( U1 – 1) +1
Address of A[1,2] = α + U1
Address of A[1,3] = α + U1 + U1
Address of A[1,3] = α + 2*U1
…
Address of A[1,j] = α + (j – 1)*U1
Address of A[2,j] = α + (j – 1)*U1 +1
Address of A[3,j] = α +(j – 1)*U1 +2
…
Similarly, A[i, j] = α +(j – 1)*U1 + (i – 1)

63
Column Major Order Arrangement

Now, let us remove the assumption that every element takes 1 byte of storage
with n bytes for storage. So, the formula will change to

Address of A[i, j] = α +[(j – 1)*U1 + (i – 1)]*n

64
Column Major Order Arrangement

Now, remove the assumption that first index is 1 in row and column
with L1 and L2, respectively. Replacing U1 as U1 – L1 +1 (length
formula), i with i – L1 + 1 and j with j – L2 + 1

Address of A [i, j] = α + [(j – L2 + 1 – 1)*( U1 – L1 + 1) + (i – L1 + 1 – 1)]*n

Address of A [i, j] = α + [(j – L2)*(U1 – L1 + 1) + (i – L1)] *n

65
Can you answer these questions?

Suppose a 2D array A is declared as A[–2:2, 2:6], words per cell = 4, base

address = 1024. Consider Column Major order arrangement.

⮚ Find the length of each dimension and number of elements in array.

⮚ Find the location of A[2,5]

66
 Solution

Here Lower Bound of row(L1) = –2

By formula:
Here Upper Bound of row(U1) = 2
Here Lower Bound of column(L2) = 2 Address of A[i, j] = Base address + [(j
– L2)*( U1 – L1 + 1) + (i – L1)] *n
Here Upper Bound of column(U2) = 6
n=4
Address of A[2,5] = 1024 + [(5 – 2) *
Length of row = U1 – L1 + 1
(2 – (–2) + 1) + (2 – (–2))] * 4
= 2 – (–2) + 1 = 5
Length of column = U2 – L2 + 1
= 1024 + [15 + 4]*4
= 6 – 2 + 1 =5
= 1024 + 76
No. of elements = 5*5 = 25
= 1100

67
 Three Dimensional Array
• An array represented in the form of 3 different
dimensions, is called 3-D Array

Declaration of three-dimensional array:

Syntax: <Data Type> <Arrayname> [m][n][o]
Where,
m  1st Dimension
n  2nd Dimension
o  3rd Dimension

• A[3][4][5], it will have a total of 3 x 4 x 5 = 60 elements.

68
 Three Dimensional Array

Memory Representation
Row Major Representation

• The first dimension is considered as row.

Column Major Representation

69
 Three Dimensional Array

Row Major Representation

• Imagine a cuboid of size U1 x U2 x U3.

• The 3-D Array can be represented as A[L1:U1, L2:U2, L3:U3]
where,
L1 = lower bound of first dimension
L2 = lower bound of second dimension
L3 = lower bound of third dimension

70
Index Formula Derivation in Three Dimensional Array

The diagram can be viewed as U1 2-D arrays of size U2xU3.

71
Index Formula Derivation in Three Dimensional Array

The above diagram can be viewed as U1 2-D arrays of size U2xU3

If the base address of array is α then,
Address of A[1,1,1] = α
Address of A[2,1,1] = α + U2*U3 (There are U2xU3 elements in the first slice)
Address of A[3,1,1] = α + U2*U3 + U2*U3
= α + 2*U2*U3
72
Index Formula Derivation in Three Dimensional Array

Address of A[4,1,1] = α + 3*U2*U3

Address of A[i, 1, 1] = α + (i – 1)*U2*U3

73
Index Formula Derivation in Three Dimensional Array

let us expand the ith array. This will be a 2-D array of size U2xU3
Address of A[i,2,1] = α + (i – 1)*U2*U3 + U3 (There are U3 elements in the first row of
this 2-D array)
Address of A[i,3,1] = α + (i – 1)*U2*U3 + U3 + U3
Address of A[i,3,1] = α + (i – 1)*U2*U3 + 2*U3

74
Index Formula Derivation in Three Dimensional Array

Address of 1st element of jth row

Address of A[i,j,1] = α + (i – 1)*U2*U3 + (j – 1)*U3
Address of A[i,j,2]= α + (i – 1)*U2*U3 + (j – 1)*U3 +1
Address of A[i,j,3] = α + (i – 1)*U2*U3 + (j – 1)*U3 +2
Similarly, for kth element of jth row
Address of A[i, j, k] = α + (i – 1)*U2*U3 + (j – 1)*U3 +
(k – 1)

75
Index Formula Derivation in Three Dimensional Array

• Remove the assumption that every element takes 1 byte of storage

• Remove the assumption that first index is 1

in each dimension with L1, L2 and L3
respectively.

76
 Three Dimensional Array

Column Major Representation

• The 3-D Array can be represented as A[L1:U1, L2:U2, L3:U3]
where,
L1 = lower bound of first dimension
L2 = lower bound of second dimension
L3 = lower bound of third dimension

• Cut the cuboid horizontally across the first dimension.

The slices obtained are of size U1xU2. So there will be
U3 such slices.

77
Index Formula Derivation in Three Dimensional Array

The above diagram can be viewed as U3 2-D arrays of size U1xU2.

If the base address of array is α then,
Address of A[1,1,1] = α
Address of A[1,1,2] = α + U1*U2 (There are U1xU2 elements in the first slice)

78
Index Formula Derivation in Three Dimensional Array

Address of A[1,1,3] = α + U1*U2 + U1*U2

= α + 2*U1*U2
Address of A[1,1,4] = α + 3*U1*U2

Address of A[1, 1, k]= α + (k – 1)*U1*U2

79
Index Formula Derivation in Three Dimensional Array
Address of A[1,2,k] = α + (k – 1)*U1*U2 + U1 (There are U1 elements in the first column of this 2-D array)
Address of A[1,3,k] = α + (k – 1)*U1*U2 + U1 + U1
Address of A[1,3,k] = α + (k – 1)*U1*U2 + 2*U1
Address of 1st element of jth column

Address of A[1,j,k] = α + (k – 1)*U1*U2 + (j – 1)*U1

Address of A[2,j,k]= α + (k – 1)*U1*U2 + (j – 1)*U1 + 1
Address of A[3,j,k] = α + (k – 1)*U1*U2 + (j – 1)*U1 +2
Similarly, for kth element of jth column

Address of A[i,j,k] = α + (k – 1)*U1*U2 + (j – 1)*U1 + (i – 1)

80
Index Formula Derivation in Three Dimensional Array

Remove the assumption that every element takes 1 byte of storage with n
bytes for storage. So, the formula will be

Address of A[i,j,k] = α + [(k – 1)*U1*U2 + (j – 1)*U1 + (i – 1)]*n

81
 Index Formula Derivation in Three Dimensional Array

Remove the assumption that first index is 1 in each dimension with L1, L2 and L3
respectively, i will be replaced by i–L1+1, j by j–L2+1 and k by k–L3+1

A[i, j, k] = α + [(k – L3)*(U1 – L1 + 1)*(U2 – L2 + 1) + (j – L2)*(U1 – L1 + 1) + (i – L1)]*n

82
Index Formula Derivation in Three Dimensional Array

Question: Given a 3D array A[2:8, –4:1, 6:10] with Base(A)= 200. Number of words per
cell =4. Calculate address of A[5,–1,8] if elements are stored in
- Row major order fashion
- Column major order.

83
Index Formula Derivation in Three Dimensional Array

Solution: Given:
Lower Bound of dimension 1(L1) = 2
Upper Bound of dimension 1 (U1) = 8
Lower Bound of dimension 2(L2) = -4
Upper Bound of dimension 2(U2) = 1
Lower Bound of dimension 3(L3) = 6
Upper Bound of dimension 3(U3) = 10
Base Address = 200
n=4
84
 Index Formula Derivation in Three Dimensional Array
Solution: By formula (Row major order):
Address of A[i, j, k] = Base Address + [(i–L1)(U2 –L2+1)(U3–L3+1) + (j–L2)(U3–L3+1) + (k–L3)]*n
Address of A[5,-1,8] = 200 + [(5 – 2) * (1 – (-4) + 1)* (10 – 6+1) + (-1 –(-4)*(10-6 +1) + (8 -6) ] * 4
= 200 + [ 3 * 6* 5 + 3*5 + 2]*4
= 200 + 107*4 = 628
By formula (Column major order):
Address of A[i, j, k] = Base Address + [(k–L3)(U1–L1+1)(U2–L2+1) + (j–L2) (U1–L1+1) + (i–L1)]*n
Address of A[5,-1,8] = 200 + [(8 – 6) * (8 – 2 + 1)* (1 – (–4)+1) + (-1 –(-4)*(8 -2 +1) + (5 -2) ] * 4
= 200 + [ 2 * 7 *6 + 3*7 + 3]*4
= 200 + 432 = 632
85
Index Formula Derivation for Array

Multi-Dimensional Array
N-Dimensional Array

A 3-D array A[5][4][6] can be considered as the 5 two dimensional arrays of 4x6.
For writing the Index formula for a N-dimensional array, the observation of 2-D and
3-D array derivations are used. Here it is assumed that an element requires B bytes
for storage.

87
 4.4 Primitive operations on Array

There are various primitive operations that get operate on linear data structure like
array are:
a) Traversing
b) Insertion
c) Deletion

88
4.4.1 Traversal of an Array

 Explore the array elements one by one in sequential order..

 Traversing elements exactly once.
 Also called the visiting of an array.

89
Algorithm for Traversing an Array

90
Complexity of Traversing an array

⮚ Time Complexity: ϴ(N)

Reason: The above algorithm requires execution of for loop N times. Hence,
the number of statements to be executed is N.
⮚ Space Complexity: ϴ(1)
Reason : The only extra variable taken here is i. Hence, the space complexity
is constant.

91
 4.4.2 Insertion in Array

⮚ To insert a data element in an array.

⮚ A new element can be added at the beginning, end, or at any given index
based on the requirement.

92
Continued.....

93
Algorithm for Inserting an Element in an Array

94
 Complexity of Inserting an element in an Array

 Time Complexity:
Worst Case: O(N)
Reason: When the element is to be inserted at the beginning, N number of shifting will
be required and two statements to assign the value and increase the value of N. Hence,
N+2 statements will be executed. Average case complexity is same as worst case
complexity.
Best Case : Ω(1)
Reason: When the element is to be inserted at the end, no shifting is required.
Therefore, only two statements will be executed.
 Space Complexity :ϴ(1).
Reason: The only extra variable taken here is j, hence the space complexity is ϴ(1).

95
4.2.3 Deletion in Array

⮚ To delete an element from the given index in the array and re-organizes the array
elements with shifting.

96
Algorithm for Deleting an Element in an Array

97
Application Problems Related to Array
Insertion in sorted 1-D Array

To insert an element “Key” in a sorted array (increasing order), the following steps need
to be performed:
1. A search operation for the appropriate position of insertion.
2. This position needs to be made vacant by shifting the elements to their right.
3. Insert the element at this position.

99
Insertion in sorted 1-D Array

100
 Insertion in sorted 1-D Array(Contd.)

ALGORITHM InsertionSortedArray(A[ ], N, key)

Input: Array A[ ] of size N, data element for insertion Key
Output: Updated array after insertion
BEGIN:
i =1
WHILE A[i]<key DO
i = i+1
FOR j =N TO i STEP–1 DO
A[j+1] = A[j]
A[i] = key
N=N+1
END;

101
Insertion in sorted 1-D Array(Contd.)

Time Complexity: ϴ(N)

If the desired place for the insertion is ‘I’ (found with the search) then ‘n–I’ shifting
will be required.
Search operations require l statement executions and shifting requires n-l statement
executions.
Apart from searching and shifting, three other statements will get executed. Total
statements execution is N+3 i.e. ϴ(N).

Space Complexity: ϴ (1)

The only variables taken here are i and j; hence the space complexity is constant,
i.e. ϴ(1).

102
Merging of two sorted arrays

To merge two sorted arrays, the following steps need to be performed:

 Given two sorted Arrays array1 and array2.

 The task is to combine these two sorted arrays to form a single sorted array.
 The steps given below are used to perform the merging.
 It is assumed that m represents the size of array1 and n represents the size of array2.

103
Example:

104
 Merging of two sorted arrays(Contd.)
ALGORITHM: MergeArr(A[ ], m, B[ ], n) WHILE i<=m DO
Input: Array A[ ] of size m, Array B[ ] of size n C[k]=A[i]
Output: Array after merging of elements in A[ ] and B[ ] i=i+1
BEGIN: k=k+1
C[m+n] WHILE j<=n DO
i=1, j=1, k=1 C[k]=B[j]
WHILE i<=m AND j<=n DO j=j+1
IF A[i]<B[j] THEN k=k+1
C[k]=A[i] RETURN C
i=i+1 END;
k=k+1
ELSE
C[k]=B[j]
j=j+1
k=k+1

105
Merging of two sorted arrays(Contd.)

Time Complexity:
The process of merging requires the comparison of each element of array1 with that of array2.
An element is added to the output array after the comparison.
Since m+n elements will be added in the output array, total m+n comparisons are required.
Hence Time Complexity is ϴ (m+n).

Space Complexity:
An array of size m+n is required for storage of the output.
Alongside, space is required for variables i, j and k.
the total space required is m+n+3 which can be represented as ϴ (m+n).

106
Set Union operation

 It is assumed here that the set elements are arranged in an array in ascending
sequence.
 The task is to combine these two sorted arrays to form a single sorted array
(common elements should be added only once in the output array).
 The steps given below are used to perform the union operation. It is assumed
that m represents the size of Set 1 (array1) and n, the size of Set 2 (array2) .

107
Example:

108
Set Union operation(Contd.)
i=i+1
j=j+1
ALGORITHM: SetUnion(A[ ], m, B[ ], n)
Input: Array A[ ] of size m, Array B[ ] of size n k=k+1
ELSE
Output: Array after union of elements in A[ ] and B[ ]
BEGIN: C[k]=B[j]
C[m+n] . j=j+1
Output array of size m+n k=k+1
WHILE i<=m DO
i=1, j=1, k=1
WHILE i<=m AND j<=n DO C[k]=A[i]
i=i+1
IF A[i]<B[j] THEN
k=k+1
C[k]=A[i]
WHILE j<=n DO
i=i+1
k=k+1 C[k]=B[j]
ELSE j=j+1
IF A[i]==B[j] THEN k=k+1
RETURN C
C[k]=B[j]
END;
109
Set Union operation(Contd.)

Time Complexity: This process of merging requires comparison of each element of Array1 with
that of Array2. An element is added to the output array after the comparison. Since maximum
m+n elements will be added in the output array, total m+n comparisons are required. Hence
Time Complexity is ϴ (m+n).

Space Complexity: An array of size m+n is required for storage of the output. Alongside, space
is required for variables i, j and k. Thus the total space required is m+n+3 which can be
represented as ϴ (m+n).

110
Problems for practice

1. Finding the number which is not repeated in Array of integers

111
Continued…

2. Finding the elements of one set that does not belong to the other set
It is assumed here that the set elements are arranged in ascending sequence. The algorithm traverses both the array
simultaneously and finds the common elements. These elements are not included in the output array. Rest of the
elements from set A are added to the output array. This is more like finding the set Difference of A from B.

112
Continued...

3. Set Intersection Operation

It is assumed here that the set elements are arranged in an array in ascending sequence. The task is to find the
common elements and add them to the final array. The steps given below are used to perform the intersection
operation. It is assumed that m represents the size of Set 1 (array1) and n, the size of Set 2 (array2).

113
Continued...

4. Set Difference Operation

The difference (B–A) will output the elements from array B that are not in the array A. It is assumed here that the set
elements are arranged in ascending sequence. The algorithm traverses both the array simultaneously and finds the
common elements. These elements are not included in the output array. The rest of the elements from set B are added
in the output array.

114
Question:

int val[2][4]={1,2,3,4,5,6,7,8};
4 will be value of

What would be the output of the above code ? Choose the correct option.

A. val [0][4] B. val [1][4]

C. val [1][1] D. None of these
 Question:
# include <stdio.h>
int main()
{
int arr[5],i=0; Tell the output
while(i<5) A. 12345 B. 01234
arrr[i]=++i; C. garbage value 1234 D. 23456
for(i=0;i<5;i++)
printf(“%d”,arr[i]);
printf(“\n”);
return 0;
}
 Question:

# include <stdio.h>
int main()
What will be the output of this code
{
A. Compile time error B. Same answer is printed
int a[3] = {1, 2, 3};
B.Different answer is printed D. None
int *p = a;
printf("%p\t%p", p, a);
}
Question:
# include <stdio.h>
int main() What will be the output of this code
{ A. Compile time error B. Same answer is printed
int a[3] = {1, 2, 3}; B. Different answer is D. None
int *p = a; printed
printf("%p\t%p", p, a);
}
 Question:
int main() {
int i; int arr[5] = {1}; What will be the output of this code
for (i = 0; i < 5; i++) A. followed by four B1 1 1 1 1
garbage values:
printf("%d ", arr[i]);
D. None
return 0; C. 10000
}
Question:

What will be the output of this code

#include<stdio.h>
A. 2 5 15 B125
int main()
{ C. 3 2 15 D. None
int a[5] = {5, 1, 15, 20, 25};
int i, j, m;
i = ++a[1];
j = a[1]++;
m = a[i++];
printf("%d, %d, %d", i, j, m);
return 0;}
Question:

What will be the output of this code

#include<stdio.h> A. 20 30 40 B. Compiler error
int main() C. 0 D. None
{
int a[3] = {20,30,40};
int b[3];
b=a;
printf("%d", b[0]);
}
Question:
A program P reads in 500 integers in the range [0..100] experimenting the
scores of 500 students. It then prints the frequency of each score above 50.
What would be the best way for P to store the frequencies?

What will be the output of this code

A. An array of 50 numbers B. An array of 100 numbers

C. An array of 500 numbers D. A dynamically allocated array

of 550 numbers
Question:

#include<stdio.h>
int main()
What will be the output of this code
{
A. 10 B.1
int arr[1]={10};
printf("%d\n", 0[arr]); C. 6 D. 8
return 0; }
Question:

#include<stdio.h>
int main()
What will be the output of this code
{
A. 10 B.1
int arr[1]={10};
printf("%d\n", 0[arr]); C. 6 D. 8
return 0;
}
Question:
⮚ Which of the following concepts make extensive use of arrays?

What will be the output of this code

A. Binary Trees B. Scheduling

C. Caching
D. Spatial locality
Question:
⮚ Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the
pair (i, j) is called an inversion of A. What is the expected number of
inversions in any permutation on n elements ?

What will be the output of this code

A. θ(n) B.θ(n2)
C. O(1) C. O(n)
Question:

Which of the following operations is not O(1) for an array of sorted data. You may
assume that array elements are distinct.

What will be the output of this code

A. Find the ith largest element B. Delete an element
C. Find the ith smallest element C. All of the above
Application of 2D Array
Applications of Two Dimensional Array

a) Graph: Representation of Graph data structure using adjacency matrix.

b) Computer Graphics: Representation of pixel information. Various
operations like translation, rotation, scaling etc. can be performed with
direct computations on pixel matrix.
c) Geology: Matrices are used for the representation of dynamics of Earth
e.g., seismic surveys. Matrices can also be used to draw graphs, statistics,
perform scientific calculations.
d) Economics: Use of Decision matrix can help to select the best course plan
for business processes. Decision matrix provides a way to compare
different solutions to a given problem and select the best one.
129
Applications of Two Dimensional Array

e) In Auto CAD Civil Construction: here structure of buildings can be

represented as matrices by storing their coordinates and angles.
f) Manage Databases: Managing Tables
g) Robotics and Automation: Here, matrices are used to store the
direction coordinates and angles related to the robot’s movement.
h) Data Security by providing encryption and Decryption: In
cryptography, encryption and decryption is done by performing the
basic matrix operations like matrix multiplication, transpose etc.

130
Applications of Two Dimensional Array

Matrix Traversal
P[ ][ ] is the array and M x N is the size of the array.

131
Applications of Two Dimensional Array

Matrix Traversal

Time Complexity: ϴ(N)

The above algorithm requires execution of loop M x N times. Hence, the
number of statements to be executed are ϴ(Mx N).
Space Complexity: ϴ(1)
The only extra variables taken here is I and j. Hence, the space complexity is
constant.

132
Applications of Two Dimensional Array

Matrix Addition
P and Q are the two matrices of the same order (same number of rows and columns).

133
Applications of Two Dimensional Array

Matrix Addition

134
Applications of Two Dimensional Array

Matrix Addition

Time Complexity: Since addition is performed element by element

and there are R1xC1 elements, the time complexity will be
ϴ(R1*C1), where R1 is the number of rows and C1 is the number of
columns.
Space complexity: An additional matrix of size R1xC1 is used and
two variables i and j. Hence, the space complexity is ϴ(R1*C1).

135
Applications of Two Dimensional Array

Matrix Subtraction
P and Q are the two matrices of the same order (same number of rows and columns).

136
Applications of Two Dimensional Array

Matrix Subtraction

137
 Applications of Two Dimensional Array

Matrix Subtraction

Time Complexity: Subtraction is performed element by element and

there are R1xC1 elements, the time complexity will be ϴ(R1*C1),
where R1 is the number of rows and C1 is the number of columns.
Space complexity: An additional matrix of size R1xC1 is used and two
variables i and j. Hence, the space complexity is ϴ(R1*C1).

138
Applications of Two Dimensional Array

Matrix Multiplication
Let P and Q are the two matrices to be multiplied(P.Q), number of columns in P must be equal to the number
of rows in Q.
Let P be a R1xC1 matrix and Q be a R2xC2 matrix. Then the product of the matrices P and Q will be of the
order of mxp.

139
Applications of Two Dimensional Array

Matrix Multiplication

140
Applications of Two Dimensional Array

Matrix Multiplication
Time Complexity: The order of the first matrix is R1xC1, the order of the
second matrix is R2xC2. Total multiplications performed to obtain the output
matrix will be of the order of R1xC2 will be R1.C1.C2. Hence, the time complexity
is ϴ(R1.C1.C2).
Space complexity: An additional matrix of size R1xC2 is used and three
variables i, j and k. Hence, the space complexity is ϴ(R1C2).

141
Applications of Two Dimensional Array

Transpose of a matrix
Interchange the rows elements with the corresponding columns elements. If a matrix P is of
order rxc then transposed matrix will be of order cxr.

142
Applications of Two Dimensional Array

Transpose of a matrix

143
Applications of Two Dimensional Array

Transpose of a matrix
Time complexity: Let P be an RxC matrix. Transpose will require RxC
times placement of data from original matrix to transposed matrix.
Thus, complexity of transpose operation will be ϴ(C.R).
Space complexity: An additional matrix of size CxR is used and two
variables i, j. Hence, the space complexity is ϴ(C.R).

144
Applications of Two Dimensional Array

Determinant of a Matrix

145
Applications of Two Dimensional Array

Determinant of a Matrix

146
Applications of Two Dimensional Array

Determinant of a Matrix

Time Complexity: As N2 multiplications are required for finding

determinants, Time complexity will be ϴ (N2).
Space Complexity: There are no additional space required; hence the space
complexity will be ϴ(1)
147