Data Structures And Algorithms

Tutorial Three:
Introduction to Arrays
Implementation of Orthogonal Arrays using Dope Vectors
Lecture Instructors :
Prof. Dr. Ahmed El Nahas Prof. Dr. Amira Youssef

Tutorial Instructors:
Eng. Ahmed Abdelhamid Waheed Abdelwahab Eng. Mohamed Essam
Eng. Ahmed Ashraf Eng. Aya Salah Eng. Tamim Sherif
1
 Quick Review: Array
An array is a finite, fixed-sized, ordered set of values known as
elements. All elements are of the same type, and are individually
referenced by the use of subscripts (Random Access Structure).
An array is a mapping from the domain of index type into element
type.
0 1 2 3 4 5 6 ……… n-1
Index Type
15 4 9 12 20 25 21 32……… 15
Element Type n
elements
Index Type 0 1 2 3 4 5 6 ……… n-1
A B C E F D G I………… J
Element Type

2
 Quick Review: Variations of Arrays
Arrays differ fro language to language:
ϕTypes of elements
ϕTypes used as index
ϕBounds determined at compile or run-time
ϕDimensionality
ϕForm of array slicing provided
ϕKind of array initialization statements allowed
ϕProvided built in operations on compatible arrays

3
 Quick Review: Arrays in C
C treats some aspects of pointers and arrays notation differently
from other languages.
C has only one-dim arrays. An element of an array may be of any
type.
The size of an array must be fixed as a constant at compilation-time.
In C, subscript type is integer. The subscripts run from 0.

4
Quick review: Operations on Array

5
 Quick Review: Types of Arrays
Orthogonal Arrays
Others
ϕTriangular and Symmetric Arrays
ϕSparse Arrays

6
 Quick Review: Orthogonal Arrays
Orthogonal Arrays are either implemented as:
ϕDope Vectors (Main interest of this Tutorial)
ϕAccess Tables

7
 Quick Review: Dope Vectors
Sequential allocation technique
ϕ Array is implemented as two blocks
 Array elements
 Array Descriptor
ϕ Elements are sequentially allocated in a
block whose address is stored in the
Dope vector.
ϕ Multi-Dimensional arrays are mapped
into equivalent one-dimensional array.

8
 Quick Review: Row Major Storage vs Column
Major Storage of 2D arrays
Equivalent 1-dimensional Array A
Row Major
2-dimensional Array A
Row 0 Row 1 Row 2
Column 0 Column 1 Column 2 1 5 9 51 2 4 42 23 24
Row 0 1 5 9
Row 1 51 2 4
Row 2 42 23 24 Equivalent 1-dimensional Array A
Column Major
Column 0 Column 1 Column 2
A[0,1] = 5
A[1,2] = 4 1 51 42 5 2 23 9 4 24

9
 Quick Review: Accessing Function
An accessing/addressing function is needed to compute the address
of an element using the information in the Dope vector together with
the values of subscripts.
What if accessing non-existing element ?
ϕIn evaluation of addressing function, some programming languages do run-
time checks for validity of checks, others don’t.

10
 Quick Review: 1 Dimensional Array Accessing

Size of each
location

11
Quick Review: 2 Dimensional Array Accessing

Size of each
location

12
Quick Review: 3 Dimensional Array Accessing

Size of each
location

13
Quick Review: General Array Declaration

14
 Exercises(1)
1. Given the following array sorted in lexicographic order, derive the
appropriate addressing equation for X[s1, s2, s3, s4], an integer
occupies 4 memory cells;
Var X: array [ I…J, L…M, O…P, Q…R] of integer;

15
 Solution
L1 = I U1 = J
L2 = L U2 = M
L3 = O U3 = P
L4 = Q U4 = R
c = 4
Loc(X[s1, s2, s3, s4]) = Loc(X[L1, L2, L3, L4]) + 4* order(X[s1, s2, s3, s4])
=Loc(X[s1, s2, s3, s4]) = Loc(X[I, L, O, Q]) + 4* order(X[s1, s2, s3, s4])
order(X[s1, s2, s3, s4]) = (R – Q + 1)(P – O + 1)(M – L + 1)(s1 – I) +
(R – Q + 1)(P – O + 1)(s2 – L) +
(R – Q + 1)(s3 – O) +
(s4 - Q)

16
 Exercises(2)
2. Obtain the addressing formula for the element A[i1, i2, i3, i4, i5] in
array A declared as var A: array [L1 … U1, L2 … U2, L3 … U3, L4 … U4, L5
… U5] of ELEMENT. Assume a column-major representation of the
array, with 6 memory cells per element, and BASEADR to be the
address of the element A[L1, L2, L3, L4, L5].

17
 Solution
c = 6
Loc(A[i1, i2, i3, i4, i5]) = Loc(A[L1, L2, L3, L4, L5]) + 6*order(A[i1, i2, i3, i4, i5])
order(A[i1, i2, i3, i4, i5]) =
(U1 – L1 + 1)(U2 – L2 + 1)(U3 – L3 + 1)(U4 – L4 + 1) (i5 – L5) +
(U1 – L1 + 1)(U2 – L2 + 1)(U3 – L3 + 1)(i4 – L4) +
(U1 – L1 + 1)(U2 – L2 + 1)(i3 – L3) +
(U1 – L1 + 1)(i2 – L2) +
(i1 – L1)

18
 Exercises(3)
3. Assume that each element of an array A is stored in row-major
order occupies four units of storage. If A is declared by each of the
following, and the address of the first element of A is 1000, find the
address of the indicated array element:
a) Var A: array [1…100] of T; address of A[10]
b) Var A: array [10…200] of T; ‘’ ‘’ A[100]
c) Var A: array [-100…1, 1…100] of T; ‘’ ‘’ A[1, 12]
d) Var A: array [1…10, 1…20] of T; ‘’ ‘’ A[2, 1]

19
 Solution(a)
c = 4
L1 = 1 U1 = 10
Base address (loc(A[1])) = 1000
Loc(A[10]) = 1000 + 4 * (10 – 1) = 1036

20
 Solution(b)
c = 4
L1 = 10 U1 = 200
Base address (loc(A[10])) = 1000
Loc(A[100]) = 1000 + 4 * (100 – 10) = 1360

21
 Solution(c)
c = 4
L1 = -100 U1 = 1
L2 = 1 U2 = 100
Base address (loc(A[-100,1])) = 1000
Loc(A[1,12]) = 1000 + 4 * [(100 – 1 + 1)(1 – (-100)) + (12 - 1)] = 41444.

22
 Solution(c)
c = 4
L1 = 1 U1 = 10
L2 = 1 U2 = 20
Base address (loc(A[1,1])) = 1000
Loc(A[2,1]) = 1000 + 4 * [(20 – 1 + 1)(2 – 1) + (1 - 1)] = 1080.

23
 Exercises(4)
4. Assume that each of the elements of the array X occupies 8 units of
storage. Derive the addressing function for computing the address
of the array element, X[i, j, k], if the array X is declared as: var X:
array [1….10, 5…9, -3…6] of T; and the array is stored in row-major
order with the first element at address 10,000. Repeat if the array is
stored in column-major (reverse lexicographic).

24
 Solution
c = 8
L1 = 1 U1 = 10
L2 = 5 U2 = 9
L3 = -3 U3 = 6
Base address (loc(X[1, 5, -3])) = 10000
Row Major
ϕ Loc(X[I, J, K]) = 10000 + 8 * order(X[I, J, K])
ϕ order(X[I, J, K]) = (6 – (-3) + 1)(9 – 5 + 1)(I – 1) +
(6 – (-3) + 1)(J – 5) +
(K – (-3)) =
50(I-1) + 10(J-5) + (K + 3)

25
 Solution
c = 8
L1 = 1 U1 = 10
L2 = 5 U2 = 9
L3 = -3 U3 = 6
Base address (loc(X[1, 5, -3])) = 10000
Column Major (Reverse Lexicographic)
ϕ Loc(X[I, J, K]) = 10000 + 8 * order(X[I, J, K])
ϕ order(X[I, J, K]) = (10 – 1 + 1)(9 – 5 + 1)(K – (-3)) +
(10 – 1 + 1)(J – 5) +
(I – 1) =
50(K + 3) + 10(J-5) + (I - 1)

26
 Exercises(5)
5. Obtain the addressing formula for element A [i1, i2, i3] in array A
declared as:
var A : array [L..M, O..P, Q..R] of ELEMENT .
Assume row-major representation of the array, with 8 memory cells
per element, and that BASE is the address of the element A [L, O,
Q].

27
 Solution
L1 = L U1 = M
L2 = O U2 = P
L3 = Q U3 = R
c = 8
Loc(X[i1, i2, i3]) = Loc(X[L1, L2, L3]) + 8* order(X[i1, i2, i3])
= Loc(X[L, O, Q]) + 8* order(X[i1, i2, i3])
=BASE + 8* order(X[i1, i2, i3])
order(X[i1, i2, i3]) = (R – Q + 1)(P – O + 1)(i1 – L) +
(R – Q + 1)(i2 – O) +
(i3 – Q)

28