DATA STRUCTURE

BCS301
 What Is Data?

• Data :- Raw Facts and Figure are known as data.

• Processed data us known as information. (Accurate, Completeness)
• Data are simply values or set of values.
• Data are facts form which a conclusion can be drawn.
• Datum (Singular), Data (Plural)
 What is Data Structure?
• The data structure name indicates itself that organizing the data in memory.
• The data structure is not any programming language like C, C++, java, etc. It is a set
of algorithms that we can use in any programming language to structure the data in
the memory.
• To structure the data in memory, 'n' number of algorithms were proposed, and all
these algorithms are known as Abstract data types. These abstract data types are the
set of rules.
• A data structure is a way of organizing the data so that it can be used efficiently.
• Data Structures are widely used in almost every aspect of Computer Science, i.e.,
Compiler Design, Operating Systems, Graphics, Artificial Intelligence, and many
more.
 Basic Terminologies Related to Data Structures
• Data: We can define data as an elementary value or a collection of values. For example, the Employee's
name and ID are the data related to the Employee.
• Data Items: A Single unit of value is known as Data Item.
• Group Items: Data Items that have subordinate data items are known as Group Items. For example, an
employee's name can have a first, middle, and last name.
• Elementary Items: Data Items that are unable to divide into sub-items are known as Elementary Items.
For example, the ID of an Employee.
• Entity and Attribute: A class of certain objects is represented by an Entity. It consists of different
Attributes. Each Attribute symbolizes the specific property of that Entity.
• Field: A single elementary unit of information symbolizing the Attribute of an Entity is known as Field.
• Record: A collection of different data items are known as a Record. For example, if we talk about the
employee entity, then its name, id, address, and job title can be grouped to form the record for the
employee.
• File: A collection of different Records of one entity type is known as a File. For example, if there are
100 employees, there will be 25 records in the related file containing data about each employee.
 Why should we learn Data Structure?

• Data Structures and Algorithms are two of the key aspects of Computer
Science.
• Data Structures allow us to organize and store data, whereas
Algorithms allow us to process that data meaningfully.
• Learning Data Structures and Algorithms will help us become better
Programmers.
• We will be able to write code that is more effective and reliable.
• We will also be able to solve problems more quickly and efficiently.
Classification of Data Structure
 Classification of Data Structure

Primitive Data Structures

• Primitive Data Structures are the data structures consisting of the numbers and
the characters that come in-built into programs.
• These data structures can be manipulated or operated directly by machine-level
instructions.
• Basic data types like Integer, Float, Character, and Boolean come under the
Primitive Data Structures.
• These data types are also called Simple data types, as they contain characters that
can't be divided further
 Classification of Data Structure
Non-Primitive Data Structures
• Non-Primitive Data Structures are those data structures derived from Primitive
Data Structures.
• These data structures can't be manipulated or operated directly by machine-level
instructions.
• The focus of these data structures is on forming a set of data elements that is
either homogeneous (same data type) or heterogeneous (different data types).
• Based on the structure and arrangement of data, we can divide these data structures
into two sub-categories -
1. Linear Data Structures
2. Non-Linear Data Structures
 Basic Operations Of Data Structure
1.Traversal
2.Search
3.Insertion
4.Deletion
5.Sorting
6.Merge
7.Create: Create is an operation used to reserve memory for the data elements of the program. We can perform this
operation using a declaration statement. The creation of data structure can take place either during the following:
1. Compile-time
2. Run-time
For example, the malloc() function is used in C Language to create data structure.
8.Selection: Selection means selecting a particular data from the available data. We can select any particular data by
specifying conditions inside the loop.
9.Update: The Update operation allows us to update or modify the data in the data structure. We can also update any
particular data by specifying some conditions inside the loop, like the Selection operation.
10.Splitting: The Splitting operation allows us to divide data into various subparts decreasing the overall process
completion time.
 Some Applications Of Data Structure
1.Data Structures help in the organization of data in a computer's memory.
2.Data Structures also help in representing the information in databases.
3.Data Structures allows the implementation of algorithms to search through data (For example, search
engine).
4.We can use the Data Structures to implement the algorithms to manipulate data (For example, word
processors).
5.We can also implement the algorithms to analyse data using Data Structures (For example, data miners).
6.Data Structures support algorithms to generate the data (For example, a random number generator).
7.Data Structures also support algorithms to compress and decompress the data (For example, a zip
utility).
8.We can also use Data Structures to implement algorithms to encrypt and decrypt the data (For example,
a security system).
9.With the help of Data Structures, we can build software that can manage files and directories (For
example, a file manager).
10.We can also develop software that can render graphics using Data Structures. (For example, a web
browser or 3D rendering software).
 What is an Algorithm?
An algorithm is a process or a set of rules required to perform calculations or some other problem-solving operations
especially by a computer. The formal definition of an algorithm is that it contains the finite set of instructions which are
being carried in a specific order to perform the specific task.

Characteristics of an Algorithm
• Input: An algorithm has some input values. We can pass 0 or some input value to an algorithm.
• Output: We will get 1 or more output at the end of an algorithm.
• Unambiguity: An algorithm should be unambiguous which means that the instructions in an algorithm should be
clear and simple.
• Finiteness: An algorithm should have finiteness. Here, finiteness means that the algorithm should contain a limited
number of instructions, i.e., the instructions should be countable.
• Effectiveness: An algorithm should be effective as each instruction in an algorithm affects the overall process.
• Language independent: An algorithm must be language-independent so that the instructions in an algorithm can be
implemented in any of the languages with the same output.
 Algorithm Analysis
The algorithm can be analyzed in two levels, i.e., first is before creating the algorithm, and second is after creating the
algorithm. The following are the two analysis of an algorithm:
• Priori Analysis: Here, priori analysis is the theoretical analysis of an algorithm which is done before implementing
the algorithm. Various factors can be considered before implementing the algorithm like processor speed, which has
no effect on the implementation part.
When? Done before coding the algorithm.
How? Analyze the algorithm using mathematical calculations and logical reasoning.
Goal: Predict the algorithm's efficiency regardless of computers or programming languages.
Example: Say you design a sorting algorithm and, on paper, you determine that it uses two nested
loops—it will have a time complexity of O(n²).

• Posterior Analysis: Here, posterior analysis is a practical analysis of an algorithm. The practical analysis is achieved
by implementing the algorithm using any programming language. This analysis basically evaluate that how much
running time and space taken by the algorithm.
When? Done after implementing the algorithm in code.
How? Run the code on a real computer, measure actual run time and memory usage.
Goal: See how the algorithm performs in practice, considering hardware, compiler, and language
used.
Example: You write and run your sorting algorithm in Python, measure how many seconds it takes to
sort 1,000, 10,000, 100,000 items, and check how much RAM is used.
 Algorithm Complexity
The performance of the algorithm can be measured in two factors:

Time complexity: The time complexity of an algorithm is the amount of time required to complete
the execution. The time complexity of an algorithm is denoted by the big O notation. Here, big O
notation is the asymptotic notation to represent the time complexity. The time complexity is
mainly calculated by counting the number of steps to finish the execution.
sum=0;
for i=1 to n
Space complexity: An algorithm's space complexity is the amount of sum=sum+i;
space required to solve a problem and produce an output. Similar to the return sum;
time complexity, space complexity is also expressed in big O notation.

Auxiliary space: The extra space required by the

algorithm, excluding the input size, is known as an
auxiliary space.
Space complexity = Auxiliary space + Input size.
 Asymptotic Notations
The commonly used asymptotic notations used for calculating the running time complexity
of an algorithm is given below:

•Big oh Notation (O)

•Omega Notation (Ω)
•Theta Notation (θ)
 Big oh Notation (O)
•Big O notation is an asymptotic notation that measures the performance of an algorithm by
simply providing the order of growth of the function.
•This notation provides an upper bound on a function which ensures that the function never
grows faster than the upper bound. So, it gives the least upper bound on a function so that the
function never grows faster than this upper bound.

If f(n) and g(n) are the two functions defined for

positive integers,
then f(n) = O (g (n)) as f(n) is big oh of g(n) or f(n) is
on the order of g(n)) if there exists constants c and
no such that:
f(n) ≤ c . g(n) for all n ≥ no
This implies that f(n) does not grow faster than g(n),
or g(n) is an upper bound on the function f(n). In
this case, we are calculating the growth rate of the
function which eventually calculates the worst time
complexity of a function, i.e., how worst an
algorithm can perform.
 Omega Notation (Ω)
•It basically describes the best-case scenario which is opposite to the big o notation.
•It is the formal way to represent the lower bound of an algorithm's running time. It measures
the best amount of time an algorithm can possibly take to complete or the best-case time
complexity.
•It determines what is the fastest time that an algorithm can run.

If f(n) and g(n) are the two functions defined for

positive integers,
then f(n) = Ω (g (n)) as f(n) is Omega of g(n) or f(n)
is on the order of g(n)) if there exists constants c
and no such that:
f(n)>=c .g (n) for all n ≥ no and c >0
 Theta Notation (θ)
•The theta notation mainly describes the average case scenarios.
•It represents the realistic time complexity of an algorithm. Every time, an algorithm does not
perform worst or best, in real-world problems, algorithms mainly fluctuate between the
worst-case and best-case, and this gives us the average case of the algorithm.
•Big theta is mainly used when the value of worst-case and the best-case is same.
•It is the formal way to express both the upper bound and lower bound of an algorithm running
time.
Let f(n) and g(n) be the functions of n where n is
the steps required to execute the program then:
f(n)= θ g(n)
The above condition is satisfied only if when
c1 . g (n)<= f (n)<=c2 .g (n)
 O = Worst Case
Ω = Best Case
Θ = Average Case

The more accurate statement is: Big O, Omega, and Theta are notations
used to describe the upper, lower, and tight bounds of an algorithm's
performance in its best, average, or worst-case scenario.
 Parameter Big O Notation O Omega Notation (Ω) Theta Notation (Θ)

Describes an upper bound on the time or space Describes a lower bound on the time or Describes both an upper and a lower
Definition
complexity of an algorithm. space complexity of an algorithm. bound on the time or space complexity.

Used to characterize an algorithm's

Used to characterize the worst-case scenario of Used to characterize the best-case
Purpose precise bound (both worst and best
an algorithm. scenario of an algorithm.
cases).

Indicates the maximum rate of growth of the Indicates the minimum rate of growth of Indicates the exact rate of growth of the
Interpretation
algorithm's complexity. the algorithm's complexity. algorithm's complexity.

f(n) = Θg(n)) if ∃ constants c₁, c₂ > 0,

f(n) = O(g(n)) if ∃ constants c > 0, n₀ such that 0 f(n) = Ωg(n)) if ∃ constants c > 0, n₀
Mathematical Expression n₀ such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)
≤ f(n) ≤ c*g(n) for all n ≥ n₀. such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ n₀.
for all n ≥ n₀.

Focuses on both the upper and lower

Focuses on the upper limit of performance (less Focuses on the lower limit of
Focus limits, providing a balanced view of
efficient aspects). performance (more efficient aspects).
performance.

It is commonly used to analyze efficiency, Used to demonstrate the effectiveness Used to provide a precise analysis of
Usage in Algorithm Analysis
especially concerning worst-case performance. under optimal conditions. algorithm efficiency in typical scenarios.

It is less common than Big O but Used when an algorithm exhibits a

Predominant in theoretical and practical
Common Usage important for understanding best-case consistent performance across different
applications for worst-case analysis.
efficiency. inputs.

Linear search in a sorted array, where

Inserting an element in a sorted array: Ω
Examples Searching in an unsorted list: O(n). the element is always in the middle: Θ
1.
(n).
 Time-Space Trade-Off in Algorithms

A tradeoff is a situation where one thing increases and another thing decreases. It is a way to solve a problem in:
• Either in less time and by using more space, or
• In very little space by spending a long amount of time.

The best Algorithm is that which helps to solve a problem that requires less space in memory and also takes less time
to generate the output.

Types of Space-Time Trade-off:

• Compressed or Uncompressed data
• Re Rendering or Stored images
• Smaller code or loop unrolling
• Lookup tables or Recalculation
 Time-Space Trade-Off in Algorithms
Compressed or Uncompressed data: A space-time trade-off can be applied to the problem of data storage. If data
stored is uncompressed, it takes more space but less time. But if the data is stored compressed, it takes less space but
more time to run the decompression algorithm.
Re-Rendering or Stored images: In this case, Storing only the source and rendering it on demand takes less space but
more time i.e., storing an image in the cache is faster than re-rendering but requires more space in memory.
Smaller code or Loop Unrolling: Smaller code occupies less space in memory but it requires high computation time
that is required for jumping back to the beginning of the loop at the end of each iteration. Loop unrolling can optimize
execution speed at the cost of increased binary size. It occupies more space in memory but requires less computation
time.
Lookup tables or Recalculation: In a lookup table, an implementation can include the entire table which reduces
computing time but increases the amount of memory needed. It can recalculate i.e., compute table entries as needed,
increasing computing time but reducing memory requirements.
 Abstract Data Types
An Abstract Data Type (ADT) is a theoretical model for a data type that is defined by its behavior (the operations you can
perform on it) rather than its implementation (how those operations are actually coded).
In simple terms, an ADT tells you what you can do with the data, but it hides the details of how it's done.

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of
operations. The definition of ADT only mentions what operations are to be performed but not how these operations
will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for
implementing the operations. It is called “abstract” because it gives an implementation-independent view.
 Array in Data Structure
Arrays are defined as the collection of similar types of data items stored at contiguous memory
locations.
In C programming, they are the derived data types that can store the primitive type of data such
as int, char, double, float, etc.
Properties of array
There are some of the properties of an array that are listed as follows –
• Each element in an array is of the same data type and carries the same size that is 4 bytes.
• Elements in the array are stored at contiguous memory locations from which the first
element is stored at the smallest memory location.
• Elements of the array can be randomly accessed since we can calculate the address of each
element of the array with the given base address and the size of the data element.

Representation of an array Memory allocation of an array

Basic operations
Now, let's discuss the basic operations supported in the array -
• Traversal - This operation is used to print the elements of the array.
• Insertion - It is used to add an element at a particular index.
• Deletion - It is used to delete an element from a particular index.
• Search - It is used to search an element using the given index or by the value.
• Update - It updates an element at a particular index.

Traversal operation

#include <stdio.h>
void main() {
int Arr[5] = {18, 30, 15, 70, 12};
int i;
printf("Elements of the array are:\n");
for(i = 0; i<5; i++) {
printf("Arr[%d] = %d, ", i, Arr[i]);
}
}
Insertion operation Deletion operation
#include <stdio.h> #include <stdio.h>
int main()
{ void main() {
int arr[] = {18, 30, 15, 70, 12};
int arr[20] = { 18, 30, 15, 70, 12 }; int k = 30, n = 5;
int i, x, pos, n = 5; int i, j;
printf("Array elements before insertion\n");
for (i = 0; i < n; i++) printf("Given array elements are :\n");
printf("%d ", arr[i]);
printf("\n"); for(i = 0; i<n; i++) {
printf("arr[%d] = %d, ", i, arr[i]);
}
x = 50; // element to be inserted
pos = 4; j = k;
n++;
while( j < n) {
for (i = n-1; i >= pos; i--) arr[j-1] = arr[ j];
arr[i] = arr[i - 1]; j = j + 1;
arr[pos - 1] = x; }
printf("Array elements after insertion\n"); n = n -1;
for (i = 0; i < n; i++)
printf("%d ", arr[i]); printf("\nElements of array after deletion:\n");
printf("\n");
return 0; for(i = 0; i<n; i++) {
} printf("arr[%d] = %d, ", i, arr[i]);
}
}
Search operation Update operation
#include <stdio.h> #include <stdio.h>
void main() {
int arr[5] = {18, 30, 15, 70, 12}; void main() {
int item = 70, i, j=0 ; int arr[5] = {18, 30, 15, 70, 12};
int item = 50, i, pos = 3;
printf("Given array elements are :\n");
printf("Given array elements are :\n");
for(i = 0; i<5; i++) {
printf("arr[%d] = %d, ", i, arr[i]); for(i = 0; i<5; i++) {
}
printf("\nElement to be searched = %d", item);
printf("arr[%d] = %d, ", i, arr[i]);
while( j < 5){ }
if( arr[j] == item ) {
break; arr[pos-1] = item;
} printf("\nArray elements after updation :\n");

j = j + 1; for(i = 0; i<5; i++) {

} printf("arr[%d] = %d, ", i, arr[i]);
printf("\nElement %d is found at %d position", item, j+1);
}
} }
 Time Complexity

Operation Average Case Worst Case

Access O(1) O(1)

Search O(n) O(n)

Insertion O(n) O(n)

Deletion O(n) O(n)

 Address calculation of 1-D Array

Address(A[i]) = Base Address + [ I – LB] * w

• A is the array name

• B is the base address (starting address in memory of the array)
• W is the storage size of one element (in bytes)
• I is the index (position) of the element whose address you want to
find
• LB is the lower bound of the index (if not specified, assume 0)
Q1: Consider an array of size 50. Calculate the address of array
element 35 if the Base Address is 1000 and memory per word is 2.
Q1: Consider an array of size 50. Calculate the address of array
element 35 if the Base Address is 1000 and memory per word is 2.

Answer:
w = 2, b = 1000, i = 35
Address(A[i]) = b + w * (i - lb)
Address A[35] = 1000 + 2 * (35 - 0)
= 1000 + 2 * 35
= 1070
Q-2: Let the base address of the first element of an array be 400, and each
element of an array occupies 2 bytes in memory. Then find the address of the 4th
element in the array A[10].
Q-2: Let the base address of the first element of an array be 400, and each
element of an array occupies 2 bytes in memory. Then find the address of the 4th
element in the array A[10].

Solution:
i = 3, b= 400, lb = 0, w = 2
Address(A[3]) = 400 + 2 * [3 - 0]
= 400 + 6
= 406
Q-3: A[-25, +15] and Base address = 1000. Size of each element is 10,
and find the address of A[60].
Q-3: A[-25, +15] and Base address = 1000. Size of each element is 10,
and find the address of A[60].
Ans:
Address(A[i]) = b+ w * (i - lb)
Here i = 60, b= 1000, w = 10, lb = -25
Address(A[60]) = 1000 + 10 * [60 - (-25)]
= 1000 + 10 * [60 + 25]
= 1000 + 10 * 85
= 1850
• Q-4: Consider the linear array A[-5:30]. If the base address is 150 and
space required to store each element is 2 words, then calculate the
address of A[15].

Ans: ???
• Q-4: Consider the linear array A[-5:30]. If the base address is 150 and
space required to store each element is 2 words, then calculate the
address of A[15].

Ans: 190
• Q-5: Consider the linear array A[200:256]. If the base address is 200
and space required to store each element is 3 words of memory, then
the address of A[215], A[241], and A[266] is

Ans: ????
• Q-5: Consider the linear array A[200:256]. If the base address is 200
and space required to store each element is 3 words of memory, then
the address of A[215], A[241], and A[266] is

Ans: Address of A[215] is 245

Address of A[241] is 323
Address of A[266] is out of bounds
LIMITATIONS OF LINEAR ARRAYS

• Linear arrays are static structures, i.e., memory used by them cannot be
reduced or extended.

• Previous knowledge of the number of elements in the array is necessary.

• Since the elements of these arrays are stored in consecutive locations, the
insertions and deletions in these arrays are time-consuming.
MULTI-DIMENSIONAL ARRAYS
An array can be of more than one dimension. There are
no restrictions to the number of dimensions that we
can have.

But as the dimensions increase, the memory

requirements increase drastically, which can result in a
shortage of memory.

Hence a multi-dimensional array must be used with

utmost care.
For example,

following array declaration:

int A[50][50][50];

will result in occupying

50*50*50 = 1,25,000*4 = 5,00,000 bytes of memory.

Length of an Array:
The length of an array is: UB−LB+1

Two Dimensional Array:

• Two dimensional array is an array of one-dimensional arrays.

Syntax:
Datatype ArrayName [row-size][column-size];
Example:
int A[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int a[][3] = {------------}; ✔
Int a[3][]= X

a[0][0] :would access the first element,

a[1][2] :would access the element in the second row and third column
The 2D array is structured like this:
0 1 2
0 1 A[0][0] 2 A[0][1] 3 A[0][2]
1 4 A[1][0] 5 A[1][1] 6 A[1][2]
2 7 A[2][0] 8 A[2][1] 9 A[2][2]
• 2D Array is also known as a Matrix.
• 2D Array is treated as a collection of 1D arrays.
• 2D Array is stored in memory in sequential order.
There are two ways to store a 2D array in memory:
(i) Row-major order(raw by row)
(ii) Column-major order(column by column)
• The elements of a two-dimensional array are stored in a computer's
memory row-by-row or column-by-column.

• If the array is stored as row-by-row, it is called row-major order.

• If the array is stored as column-by-column, it is called column-major

order.
• Under row-major representation, the first row of the array occupies
the first set of memory locations reserved for the array, the second
row occupies the next set, and so forth.

• Under column-major representation, the first column of the array

occupies the first set of memory locations reserved for the array, the
second column occupies the next set, and so forth.
• In row-major order, elements of a two-dimensional array are ordered
as:

A11,A12,A13,A14,A15,A16,A21,A22,A23,A24,A25,A26,A31,…,A56

• column-major order, elements are ordered as:

A11,A21,A31,A12,A22,A32,A13,A23,A33,…,A56
Suppose we have

• Row major representation

{a, b, c, d, e, f, g, h, i, j, k, l}

• Column-Major Representation
{a, e, i, b, f, j, c, g, k, d, h, l}
 Q. Show how the matrix
would appear in memory
when stored in:
(a) Row-major order
(b) Column-major order
• Solution
Q . A 2D array with 2 rows and 3 columns stands in memory as: 853
726
Show the matrix form of 2 dimensional array
• Solution: Data may be stored in row-major or
column-major order. If the data is stored in row-major
order, then the memory mapping and the matrix form
would be as:
853
726

If data is stored in column-major order, then the memory

mapping and the matrix form would be as:
832
576
• Index formula for 1D, 2D, 3D, and N-D Arrays
• The index formula for a multi-dimensional array allows you to
compute the linear index (position) of an element in the array given
its indices along each dimension.
• Let’s denote the dimensions of the array as d1,d2,d3,…, where n is
the number of dimensions.
• 1-D Array:
For a 1-dimensional array, the index formula is very simple: Index = i
where i is the index of the element along the 1st (and only) dimension.
• 2-D Array:
For a 2-dimensional array with dimensions d1 and d2, the index is:
Index = i_1 × d_2 + i_2

where i1 is the index of the element along the 1st dimension and i2 is the index along the 2nd dimension.

Example: Suppose we have a 2-dimensional array with dimensions 3×4.

Let’s find the linear index for the element at position (2, 3).

• Given the dimensions, d1=3 and d2=4 and the indices i1= 2 and i2=3 the index formula
becomes: Index = i_1 × d_2 + i_2

• Index = 2 × 4 + 3 = 11
• 3-D Array:
For a 3-dimensional array with dimensions d1,d2,d3
• Index = i_1 × (d_2 × d_3) + i_2 × d_3 + i_3

where i1 is the index of the element along the 1st dimension, i2 is the index along the 2nd dimension, and i3 is the index along the
3rd dimension.
• ADDRESS CALCULATION FOR 2D ARRAY
• Let us consider a two-dimensional array A of size m×n.
• Like a linear array system, the array keeps track of the address of the first
element only, i.e., the base address of the array (Base(A)). Using the base
address, the computer computes the address of the element in the ith row
and jth column, i.e., LOC(A[i][j]).
 (a) Column-Major Order
LOC(A[i][j]) = Base(A) + w[(i - lower bound for column index) + m(j - lower bound for row index)]
Or in general
LOC(A[i][j]) = B+ w[(i-Lr)+m*(j-Lc)] in C/C++
(b) Row-Major Order
LOC(A[i][j]) = Base(A) + w[n(i - lower bound for row index) + (j - lower bound for column index)]
Or in general
LOC(A[i][j]) = B+ w[n(i-Lr)+(J-Lc)] in C/C++

w denotes the number of words per memory location for the array A or the number of bytes per storage location
for one element of the array.
B = Base Address
w = Storage size of an element
hr = Start row index of matrix / lower bound of row
hc = Start column index of matrix / lower bound of column
M = Number of rows in matrix
N = Number of columns in matrix
i = Row subscript of element whose address is to be found
j = Column subscript of the element whose address is to be found
• Q.

A[2][1] =?
Ans.

LOC(A[i][j]) = B+ w[n(i-Lr)+(J-Lc)]
• Here Base(A) = 104
w=2
N = 4, i = 2, j = 1

LOC(A[i][j]) = B+ w[n(i-Lr)+(J-Lc)]
Address of A[2][1] = 104 + 2[4(2 - 0) + (1 - 0)]
= 104 + 2[4 * 2 + 1]
= 104 + 2 * 9
= 104 + 18 = 122
• Q. Column Major order

Address of A[i][j] = Base(A) + w[(i - Lr) + M * (j - Lc)]

A[1][2] = 104 + 2[(1 - 0) + 3 * (2 - 0)]
= 104 + 2[1 + 6]
= 104 + 14
• Problem 1:
An array A[1:10, 1:10] requires 2 bytes of storage for
each element, and the base address is 500. So,
determine the location of A[5][2].
• Row -> 582
• Column -> 528
• Problem 2:
An array X[-15:10, 15:40] requires 1 byte of storage
for each element, and the base address is 1500. So,
determine the location of X[5][20].
• Row -> 2025
• Column -> 1650
• Q3 - Consider a 20×5 2D array. Base address = 1000 and size of an element = 2.
Calculate the address of element A[10][4] by row-major and column-major order.

• Solution:
Given:
Base Address (BA) = 1000
M × N = 20 × 5
w=2
i = 18, j = 4
• Row-major:
• Address of A[i][j] = Base(A) + w[N(i - hr) + (j - hc)]
• = 1000 + 2[5(10 - 0) + (4 - 0)]
• = 1000 + 2[5 * 10 + 4]
• = 1000 + 2 * 54
• = 1000 + 108
• A[10][4] = 1108
• Column-major:
Address of A[i][j] = Base(A) + w[(i - hr) + M * (j - hc)]
= 1000 + 2[(10 - 0) + 20(4 - 0)]
= 1000 + 2[10 + 80]
= 1000 + 2 * 90
A[10][4] = 1180
• Problem 4:
Consider a two-dimensional array A[10][8] which has a base address =
1000 and the number of bytes per element = 2. Compute the address
of element A[8][5] by row-major and column-major order.
• Answer:
Row = 1170
Column = 1116
• Problem 5:
Consider 2D array A[25...79, 55...124]
Base(A) = 1000
Size of each element w = 100
Find the location of A[55][75] by row-major and column-major.

Solution:
A[25...79, 55...124]
Number of rows (lr) = UB₁ - LB₁ + 1 = 79 - 25 + 1 = 55
Number of columns (lc) = UB₂ - LB₂ + 1 = 124 - 55 + 1 = 70

Row-major: A[i][j] = Base(A) + w[N * (i - lr) + (j - lc)]

Column-major: A[i][j] = Base(A) + w[(i - lr) + M * (j - lc)]

 Row:
A[55][75] = 1000 + 100[70*(55 - 25) + (75 - 55)]
= 1000 + 100[70 * 30 + 20]
= 1000 + 100 * 2120
= 1000 + 212,000
A[55][75] = 213,000
Column:
A[55][75] = 1000 + 100[(55 - 25) + 55 * (75 - 55)]
= 1000 + 100[30 + 55 * 20]
= 1000 + 100[30 + 1100]
= 1000 + 100 * 1130
= 1000 + 113,000
A[55][75] = 114,000
• Important Questions:
• Consider a linear array AAA(5:50), B(5:10), and CCC(10).
a. Find the number of elements in each array.
b. Suppose Base(AAA) = 300 and w = 4 words per memory cell for
AAA. Find addresses of AAA[15], AAA[35], and A[55].
(a) Number of elements
• AAA(5:50) → indices 5 through 50 inclusive → 50−5+1=46 elements.
• B(5:10) → indices 5 through 10 inclusive → 10−5+1= 6elements.
• CCC(10) → typical convention is 1..10 → 10 elements.