Discipline: BS (Software Engineering) – 2nd Semester

Subject: Database Systems Notes (MID Term):

Week No. 04: Data Structure and Algorithm
Prepared by: Kashif Aman, Lecturer (Computer Science),
Computer Science Department, CECOS University
of IT & Emerging Sciences, Peshawar

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 Array
Table of Content

 What is an Array?
 Need of Array Data Structures
 Types of Array Data Structures
 Array Operations
 Application of Array

Array:
Array is the name of the consecutive memory locations that all have same name and same type.
Or
An array is a collection of items of the same variable type that are stored at contiguous memory locations
It’s one of the most popular and simple data structures and is often used to implement other data
structures. Each item in an array is indexed starting with 0 . Each element in an array is accessed through
its index.
Or
Array is a finite number of homogeneous data having a common name, a unique index, and
stored in consecutive memory location in the computer memory.
By finite number mean that size of the array should be known. By homogenous mean that the data
should be of the same type. By consecutive mean that the data item of the array stored one after the other
in computer memory.

Need of Array Data Structures

 Storing data for processing
 Implementing data structures such as stacks and queues
 Representing data in tables and matrices
 Creating dynamic data structures such as linked lists and trees

Types: There are two types of arrays:

1. One-Dimensional Array(ODA)
2. Two-Dimensional Array

One-Dimensional Array: These arrays store a single row of elements.

Length or size of the One Dimensional Array:
Total number of elements in the ODA is called the length of the One Dimensional Array.
Formula:
Length = UB – LB + 1;

Where UB represents the upper bound of the one-dim ensional array and LB is

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 lower bound of the one-dimensional array.

Representation of Array

The representation of an array can be defined by its declaration. A declaration means allocating
memory for an array of a given size.

Accessing One Dimensional Array by Dope Vector method:

The dope vector method is an efficient way to access each element of an array. This method
uses the start address and subscript number (index number) of the element for accessing
using the following formula:
MA (i) = SA + (i-1) * w (If array started from index value
1)OR
MA (i) = SA + i * w (If array started from index value 0)

What is a Dope Vector?

A dope vector is essentially a structure (or record) that contains metadata about an array. This
metadata includes information such as the base address, the size of each element, the number of
elements in the array, and possibly bounds (lower and upper bounds). The dope vector helps in
accessing elements of the array efficiently without recalculating array parameters repeatedly.

MA = Memory Address of the element

SA = Start Address
i = Subscript number (index number) of an element to be accessed
w = the word length, for integer w = 2, for float w = 4, for char w = 1
For example:
1 2 3 4
10 20 30 40
1010 1012 1014 1016
Find the Memory Address of an element at position i = 4?

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 MA (i) = SA + (i-1) * w
Where: SA = 1010 & w = 2
MA (4) = 1010 + (4-1) * 2
MA (4) = 1010 + 3 * 2
MA (4) = 1010 + 6
MA (4) = 1016
The value at address 1016 is 40.

Iterative Algorithm for Accessing Elements in a One-Dimensional Array:

Iterative of array means visiting each element of the array. The followingalgorithm is
used to traverse an array.

ALGORITHM: TRAVERSING (LB, UB, LA, K)

Here LA is a linear array with lower bound (LB) and upper bound
(UB)and K is a counter variable. The algorithm is used to traverse the
LA.

Step # 01: [Initialize counter variable]

Set K: = LB
Step # 02: [Start loop to traverse]
Repeat step 3 & 4 while (K<=UB)
Step # 03: [Visit element]
Apply PROCESS to LA [K]
Step # 04: [Increase counter variable]
Set K: = K + 1
[End of Loop]
Step # 05: [Finish]
Exit
TRAVERSING ALGORITHM using C++:
#include<iostream.h>
#include<conio.h>
void main ()
{
clrscr ();
int LA [50], LB, UB, K;
cout<<"Enter Upper Bound of the Array:
UB = ";cin>>UB;
cout<<endl<<"Enter Lower Bound of the Array:
LB = ";cin>>LB;
cout<<endl<<"Enter your Elements in the
Array:"<<endl<<endl;for (K=0; K<=UB; K++)

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 cin>>LA [K];
// Start TRAVERSING ALGORITHM
cout<<endl<<"Traversing Elements of the Array Starting from LB to
UB: ";K = LB;
while (K<=UB)
{
cout<<LA
[K]<<" ";K =
K+1;
}
// End of TRAVERSING ALGORITHM
getch ();
}

Time Complexity of Array Traversal

1. Best Case:
o Complexity: O(n)
o Explanation: Even in the best case, you must visit each element to perform an operation
(e.g., print, sum, etc.). This means the time required grows linearly with the number of
elements in the array.
2. Average Case:
o Complexity: O(n)
o Explanation: On average, traversing each element will still require visiting every
element once, resulting in linear time complexity.
3. Worst Case:
o Complexity: O(n)
o Explanation: In the worst case, the traversal still involves visiting every element of the
array, leading to linear time complexity.
Explanation:
1. Initialization: The process of starting the traversal (e.g., setting up a loop) is constant time, but
this is not a significant part of the complexity in this case.
2. Loop: The loop runs from the first element to the last element of the array:
o Iterations: There are n iterations, where n is the length of the array.
o Operation per Iteration: Each iteration involves accessing an element and performing a
constant-time operation.
3. Operation on Each Element:
o Accessing an element and performing a constant-time operation (like printing) does not
change with the size of the array.
o Each element is processed in constant time.
Mathematical Representation:
The time complexity T(n) for traversing an array is given by:
T(n)=O(n)
where:
 T(n) is the total time required to traverse an array of size n.
 O(n) indicates that the time required grows linearly with the number of elements n in the array.

Insert, and Delete in an Unsorted Array | Array Operations

Insertion Operation:

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
In an unsorted array, the insert operation is faster as compared to a sorted array because we don’t have to
care about the position at which the element is to be placed.

ALGORITHM: INSERTION (A, K, N, I, ITEM)

This algorithm is used to insert an element in array A at Kth location. N isthe total number of
filled memory location and I is the counter variable.

Step#01: [Initialize the counter variable]

I=N
Step#02: [Start loop to move the elements]
Repeat step 3 & 4 while (I > K) or (I > = K) (for 1 index number)
Step#03: [Moving element]
A [I] = A [I–1] or A [I + 1] = A [I] (when array started from 1 index number)
Step#04: [Decrement the counter variable]
I=I–1
[End of Loop]
Step#05: [Add new element]
A [K] = ITEM
Step#06: [Add memory
location]N = N+1
Step#07: [Finish]
Exit

INSERTION ALGORITHM USING C++:

#include<iostream.h>
#include<conio.h>
void main ()
{
clrscr ();
int A [100], I, K, N, ITEM;
cout<<"Enter Total number of elements in array: N = ";
cin>>N;
cout<<endl<<"Enter N number of elements into ODA:"<<endl<<endl;
for (I=0; I<N; I++)

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
cin>>A[I];
cout<<endl<<"Elements in ODA: ";
for (I=0; I<N; I++)
cout<<A[I]<<" ";
cout<<endl<<endl<<"Enter the element to insert into ODA: ";
cin>>ITEM;
cout<<endl<<"Enter position of the element to be inserted: ";
cin>>K;
// Start INSERTION ALGORITHM

I = N;
while(I>K)
{
A [I] = A
[I-1];I =
I-1;
}
A[K] = ITEM;
N = N+1;
cout<<endl<<"Total number of elements in array after insertion of an element: "<<N<<endl;
// End of Insertion Algorithm
cout<<endl<<"Array after insertion of an element: ";

for (I=0; I<N; I++)

cout<<A[I] <<" ";
getch ();
}

Time Complexity: O(1)

Delete Operation:
In the delete operation, the element to be deleted is searched using the linear search, and then the delete
operation is performed followed by shifting the elements.

ALGORITHM: DELETION (A, K, N, I)

The algorithm is used to delete an element from Kth location of an array

A. N is the total number of filled memory locations and

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 I isthe counter variable.

Step#01:[Initialize the counter variable]

I=K
Step#02: [Delete the element]
Delete A [K]
Step#03:[Starting loop]
Repeat step 4 & 5 while (I < N - 1) or (I < = N - 1) (for 1 index number)
Step#04:[Moving element]
A [I] = A [I + 1]
Step#05:[Increment the counter variable]
I=I+1
[End of Loop]
Step#06: [Remove memory location]
N=N–1
A [N] = -1 // Assign Garbage value
Step#07:[Finish]
Exit

DELETION ALGORITHM USING C++:

#include<iostream.h>
#include<conio.h>
void main ()
{

clrscr ();
int A [200], I, K, N;
cout<<"Enter Total number of filled memory locations in array: N = ";
cin>>N;
cout<<endl<<"Enter N number of elements into
Array:"<<endl<<endl;for (I=0; I<N; I++)
cin>>A[I];
cout<<endl<<"Elements in
Array: ";for (I=0; I<N; I++)
cout<<A[I]<<" ";
cout<<endl<<endl<<"Enter position of an element to be deleted: k = ";
cin>>K;
// Start DELETION ALGORITHM
I = K;
cout<<endl<<"Element to be deleted at position "<<I<<": "<<A[I]<<endl<<endl;
while (I<N-1)

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 {
A [I] = A [I+1];
I = I+1;
}
N = N-1;
A [N] = -1;
// End of DELETION ALGORITHM
cout<<"Total number of elements in array after deletion an element: "<<N<<endl<<endl;
cout<<"Array after deletion of an element:"<<endl;
for (I=0; I<=N; I++)
cout<<A[I]<<" ";
getch ();
}
TWO-DIMENSIONAL ARRAY
Introduction to Two-Dimensional Array:
Two dimensinal array has two dimensions which consist on both rows and columns.
A two dimensional array is declared by giving two indexed values in square brackets.
The first indexed value represents the total number of rows and the second represents
the total number of columns. E.g. Int arr [5][5];
A two dimensional array is called matrix in mathematics and table in the database.
Two Dimensional Array Program-01:
#include<iostream.h>
#include <conio.h>
void main()
{
clrscr ();
int i, j;
int A [3][3]={{10,20,30},{40,50,60},{70,80,90}};
cout<<"Two Dimensional Array Elements: ";
for (i=0; i<3; i++)
for (j=0; j<3; j++)
cout<<" "<<A[i][j];
getch();
}
Size or Length of Two Dimensional Array:
If m is the number of rows and n is the number of columns then the formula
forthe Size of Two Dimensional Array is as under:

Length or Size = m × n
Representation of Two-Dimensional Array in computer memory:
When two-dimensional array is stored in computer memory, it is first mapped
into a single vector because two-dimensional array is logically represented in rows and
columns but physically mapped into computer memory in vector form. It is either
mapped ina Row-by-Row Vector or a Column-by-Column Vector.
 Row-by Row Vector Method
 Column-by-Column Vector Method

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
  Row-by Row Vector Method or Row-by-Row Major Order:
In row-by-row major order, first row is stored/mapped, then second row and so on.
For example:
1 3 5
A= 2 4 6
7 8 9

Can be mapped row-by-row major order as follows:

(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
1 3 5 2 4 6 7 8 9

 Column-by-Column Vector Method:

In column-by column or column major order, first stored/mapped the first
column then the second column and so on….
For example:

1 3 5
A= 2 4 6
7 8 9

Can be mapped column-by-column major order as follows:

(1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,3) (3,3)
1 2 7 3 4 8 5 6 9

Accessing Two-Dimensional Array by Dope Vector method:

The two-dimensional array is stored into two types of vectors either row-by-row or
column- by-column. A single two-dimensional array will have two different
representations in computer memory according to the above-mentioned techniques.
Row Major Order (Row-by-Row):
Row Major Order (Row-by-Row) mapping an element can be accessed as:
MA (i, j) = SA + {n (i - 1) + (j – 1)} * w
MA = Memory Address of the element
i = No. of Row of elements to be accessed
j = No. of Column of elements to be accessed
SA = Start Address
n = Total number of Columns
w = the word length, for integer w = 2, for float w = 4, for char w = 1
For example:

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 1 3 5
A= 2 4 6
7 8 9

Can be mapped row-by-row major order as follows:

(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
1 3 5 2 4 6 7 8 9
1010 1012 1014 1016 1018 1020 1022 1024 1026

Find the Memory Address of an element at position (3, 2)?

i = 3, j = 2, SA = 1010, n = 3, w =
2 MA (i, j) = SA + {n (i - 1) + (j –
1)} * w
MA (3, 2) = 1010 + {3 (3 - 1) + (2 – 1)} * 2
MA (3, 2) = 1010 + {3 (2) + (1)} * 2
MA (3, 2) = 1010 + {6 + 1} * 2
MA (3, 2) = 1010 + {7} * 2
MA (3, 2) = 1010 + 14
MA (3, 2) = 1024
Thus, the value at the address 1024 is 8.

Column Major Order (Column-by-Column):

Column Major Order (Column-by-Column) mapping an element can be accessed as:

MA (i, j) = SA + {m (j - 1) + (i – 1)} * w

MA = Memory Address of the element

i = No. of Row of elements to be accessed
j = No. of Column of elements to be accessed
SA = Start Address
m = Total number of Rows
w = the word length, for integer w = 2, for float w = 4, for char w = 1

For example:

1 3 5
A= 2 4 6
7 8 9

Can be mapped Column-by-Columns major order as follows:

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 (1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,3) (3,3)
1 2 7 3 4 8 5 6 9
1010 1012 1014 1016 1018 1020 1022 1024 1026

Find the Memory Address of an element at position (2, 3)?

i = 2, j = 3, SA = 1010, m = 3, w =

2 MA (i, j) = SA + {m (j - 1) + (i –

1)} * w
MA (2, 3) = 1010 + {3 (3 - 1) + (2 – 1)} * 2
MA (2, 3) = 1010 + {3 (2) + (1)} * 2
MA (2, 3) = 1010 + {6 + 1} * 2
MA (2, 3) = 1010 + {7} * 2
MA (2, 3) = 1010 + 14
MA (2, 3) = 1024

Thus, the value at the address 1024 is 6.

Searching
Introduction to Searching:

Computer systems are often used to store large amounts of data from which individual
records are retrieved according to some search criteria.

The process of finding a specific data item or record from a list is called searching.

OR

It is the process by which can find the specific location of a given item in a list.

OR

Searching is a technique of finding an element from the given list or a set of elements like
arrays, list or trees.

If the item exists in the given list, then search is said to be successful otherwise if the element
is not found in the given list then search is said to be unsuccessful.

For example: Finding a telephone number in a telephone directory is called searching.

Internal search: The search in which the whole list resides in the main memory is called
internal search.

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 External search: The search in which most of the list resides in the secondary
memory is called external search.

In this searching we will concentrate on internal searching. The complexity of any

searching method is determined from the number of comparisons performed among the
collected elementsin order to find the elements. The time required for operation is depends
on the complexity of theoperation or algorithm.

There are some cases in which an element can be found:

 Best Case: The best case is that in which the element is found during the first
comparison.

 Worst Case: The worst case is that in which the element is found only at the end
or thelast comparison or not found.

 Average Case: The average case is that in which the element is found in
comparisons more than best case but less than worst case.

Types of Searching:

1. Linear Search
2. Binary Search

1. Linear Search:
Linear Search is also called sequential search. It is the simplest way for finding an element
in alist. In Linear Search, the elements find sequentially in a list, no matter whether the list
is sorted or unsorted.

In case of sorted list, the search is started from 1st element and continuous until the element
is found or the element whose value is greater than the value being searched.

In case of unsorted list, the search is started from 1st location and continuous until the
elementis found or the end of the list is reached.

Linear Search is a very slow process. It is used for small amounts of data. This method is
not recommended for large amount of data.

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 Example: Sorted Array

Data

0 1 2 3 4 5 6 7 8 9 10 11 12
A [13] = 10 20 30 40 50 60 70 80 90 100 110 120 130

Find the ITEM = 80?

1. A [0] = 10 comparison with 1st element, since 80 > 10 then

2. A [1] = 20 comparison with 2nd element, since 80 > 20 then

3. A [2] = 30 comparison with 3rd element, since 80 > 30 then

4. A [3] = 40 comparison with 4th element, since 80 > 40 then

5. A [4] = 50 comparison with 5th element, since 80 > 50 then

6. A [5] = 60 comparison with 6th element, since 80 > 60 then

7. A [6] = 70 comparison with 7th element, since 80 > 70 then

8. A [7] = 80 comparison with 8th element, since 80 =

80 thusThe search is successful, the ITEM is found at location 7.

Algorithm for Linear Search: This algorithm is used for linear searching. ITEM
is to be searched in a linear array A having N numbers of elements. LOC is variable
which store the location in case of successful search and ‘I’ is a counter variable.
Algorithm for Sorted Array: LINEAR SEARCH (A, LOC, I, N, ITEM)

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
Step 1: [Initialization]
I = 0 and LOC = -1
Step 2: [Starting Loop to Search]
Repeat step 3 & 4 ... While (I < N)
Step 3: [Comparing given element]
If (ITEM == A [I]) then
LOC: = I
Break
(These statements will not be included for unsorted array)Else if (ITEM < A [I]) then
Break
[End of IF Structure]
Step 4: [Increment counter variable]
I = I+1
[End of Loop]
Step 5: [Display Result]
If (LOC == -1) then
Write (“Element is not Found”)
Else:
Write (“Search is Successful”)
Write (“ITEM is found at Location”, LOC)
[End of IF Structure]
Step 6: [Finish]
Exit

1. Binary Search:
Binary search is the most efficient searching technique for finding an element in a sorted
list/array. In binary search, first, find the middle index of the list/array, then compare
the element (which you want to search) with the middle element of the list/array. If they
are equal, the search is successful otherwise if the element is greater than the middle
element of the list/array, then right side of the list/array will be searched and if the
element is less than the middle element, then left side of the list/array will be searched in
similar way.

Example
01 2 3 4 5 6 7 8 9 10 11 12
10 20 30 40 50 60 70 80 90 100 110 120 130
Find the ITEM = 50?

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar
 BEG=0 & END=12, MID=INT ((0+12)/2) = 6 so A[MID]=70 and 50 < 70.
2. Since 50 < 70 therefore BEG = 0 & END = MID - 1 = 6 – 1 = 5
MID = INT ((0 + 5) / 2) = 2.5 = 2 so A [MID] = 30 and 50 > 30.
3. Since 50 > 30 therefore BEG = MID + 1 = 2 + 1 = 3 & END = 5
MID = INT ((3 + 5) / 2) = 4 so A [MID] = 50 and 50 = 50.

Thus, search is successful, the ITEM is found at location 4.

Algorithm for Binary Search: This algorithm is used for binary searching. ITEM is
to be searched in a linear sorted array A having N numbers of filled memory locations. BEG,
END and MID variables are used to store array index numbers.
ALGORITHM: BINARY SEARCH (A, ITEM, LB, UB, BEG, END, MID)
Step 1: [Initialization]
BEG = LB & END = UB
Step 2: [Starting loop to search]
Repeat step 3, 4 & 5 ….. While (BEG < = END)
Step 3: [Calculate MID]
MID = INT ((BEG + END) / 2)
Step 4: [Check element]
If (ITEM = = A [MID]) Then
Break
[End of IF Structure]
Step 5: [Set BEG & END]
If (ITEM < A [MID]) then
END = MID - 1
Else:
BEG = MID + 1
[End of IF Structure]
[End of Loop]
Step 6: [Display the Result]
If (ITEM = = A [MID]) then
Write (“Element found at location”, MID)
Else:
Write (“Element not found”)
[End of IF Structure]
Step 7: [Finish]
Exit
Binary search C++ program

Prepared by: Kashif Aman, Lecturer (CS), Computer Science Department, CECOS University of IT &
Emerging Sciences, Peshawar