1 People`s Democratic Republic of Algeria

The Ministry of Higher Education and Scientific Research

University Of Science And Technology Houari Boumediene

Faculty of Computer Science

Algorithmic and Data

Structures
Arrays and String
First year in Computer Science engineering

By: PhD. HAOUARI Ahmed Taha

[email protected]

2023/2024
2

1
Arrays

It getting complicated but also easier at the same time

3

Can you solve this problem?

• With all we saw in the previous lectures try to solve this problem :
• Write an algorithm that computes the overall class average.

• The simple answer is to create for each student a variable that represents his average,
then compute the average,

• Or, we can use a loop to input the students' means and directly compute the sum of
averages, and after we finish entering the scores we can assess the overall average.

• Are there issues with these solutions?

• Imagine I ask you to sort these students by the average.
• Or simply, display the means that are above the overall average
• What happens if we have more than 30 people in one class
4

The issues

• The creation of an overwhelming number of variables,

• Lost of information for further use,
• Difficulty in controlling and accessing large amounts of data

• We need something to process and assess a large amount of data efficiently, more
precisely a data structure to represent a group of information with the same type.

• We call them Arrays (or sometimes Vectors).

5

The Arrays
• An Array is a data structure that stores a collection of items of the same type. It is one of
the most fundamental and widely used data structures in programming. Arrays are
typically implemented as contiguous blocks of memory, which means that the elements
of an Array are stored next to each other in memory. This makes it easy to access and
manipulate individual elements of an Array.

We distinguish two types of Arrays:

• One-dimensional (unidimensional) Arrays, often called Vectors 1 2 3 4

1,1 1,2 1,3 1,4

2,1 2,2 2,3 2,4

• Two-dimensional Arrays, often called Matrix
3,1 3,2 3,3 3,4
Note: In C we can go until 12 dimensions.
6

One-dimensional (1D) Arrays

Vectors
• The declaration syntax of an Array in algorithmic :
• myArray: Array[lowerBound..upperBound] of DataType;
• Where :
• myArray: This is the name of the Array.
• lowerBound: Represents the lower boundary or starting index of the Array.
• upperBound: Represents the upper boundary or ending index of the Array.
• DataType: Specifies the type of data that the Array will hold (e.g., Integer, Real, etc.).

Example :myArray: Array[1..5] of Integer; would create an Array named myArray that can store 5 integer values with
indices ranging from 1 to 5.
Address 100 104 108 112 116
The Value
MyArray 13 -5 13 18 0 of the
Alternative declaration: Elements
Indices (index) 1 2 3 4 5
myArray: Array[Size] of DataType;
Example :myArray: Array[5] of Integer; would create an Array named myArray that can store 5 integer values with
indices ranging from 1 to 5.
7

The characteristics of an Array

The following are the main characteristics of an Array:
• Array elements are of the same data type. This means that all elements in an Array must be
integers, floats, characters, or some other type of data.
• Array elements are stored contiguously in memory. This means that the elements of an Array
are stored next to each other in memory, without any gaps in between.
• Arrays are very efficient for storing and accessing data. This is because Arrays are stored
contiguously in memory, which makes it easy for the computer to access them.
• Array elements are accessed using an index. An index is a unique identifier for each element in
an Array. Indices start at 1, so the first element in an Array has an index of 1, the second element
has an index of 2, and so on.
• Arrays have a fixed size. The size of an Array must be specified when it is declared. Once an
Array is declared, its size cannot be changed.
8

Data access in Arrays

• Accessing data in Arrays involves referencing specific elements within the Array. In most
programming languages, Arrays are zero-indexed, which means the first element is accessed at
index 0, the second at index 1, and so on. However, on algorithmic the first element starts from
index(indices) 1
• By specifying the index in square brackets "[ ]", you are directly referencing the
memory location where that specific element is stored within the Array. This direct
access allows you to read or modify the value of that element without having to
traverse the entire Array.
• Example :
Var Tab: Array [10] of integer;
Begin
Tab [1]← 20; // assigning the value of the first element
Read(T[2]); // inputting data using Read on the second element
Write(T[3]);// display the Value of the Third element
9

Data access in Arrays 2

• The opposite of direct access in the context of Arrays or data structures would be
sequential access.
• Sequential access refers to accessing elements by starting from the beginning of the
data structure and moving through each element in order until reaching the desired
element. This method involves iterating or traversing the data structure sequentially.
• For instance, if you're looking for a specific value in an Array but don't know its
index, you might need to perform a sequential search by checking each element one
by one from the start until you find the desired value. Thus, we need a loop to traverse
all the elements of the Array
• Example :
For I← 1 to 10 Do
write(Tab [I]);
Done; //This piece of code displays all the elements of the Array Tab sequentially
10

Exercise 1
• You are given an Array of 100 integers. Write an algorithm that implements a linear search to find a
specified target value within the Array. The algorithm should return the index of the target value
Algorithm LinearSearchFixedArray;
const
N = 100;// to help us specify the size of an Array using a constant // Perform linear search
var I←1;
targetValue, I, index: Integer; While(I<= N and targetFound <> True ) do
myArray: Array[1..N] of Integer; // another way to declare an Array if myArray[i] = targetValue then
targetFound: Boolean; index ←I; // set the index where the target value is found
begin targetFound ← True; // Set targetFound to True if the target value is found
// Input elements of the Array EIF;
write('Enter the elements of the Array:'); I++;
for i ← 1 to N do Done;
begin If (targetFound) then
Read(myArray[i]); write(“The target”,targetValue,”is found at the position”,index);
done; Else write(“The target”,targetValue,”doesn’t exist”); EIF;
// Ask the user for the target value end.
write('Enter the target value to search for: ');
read(targetValue);
targetFound ← False; // Initialize targetFound as False, the target doesn’t exist in our Arrays,
11

Binary search(Dichotomic search)

• A "dichotomic search" is another term for what is commonly known as a "binary

search" in computer science. The dichotomic search is a searching algorithm that
operates on sorted Arrays, reducing the search interval in half with each iteration.
• The basic idea of a binary search :
1. is to repeatedly divide the Array into two halves and compare the target value with
the middle element of the Array.
2. If the target matches the middle element, the search is successful.
3. If the target is less than the middle element, the search continues in the lower half.
4. If the target is greater, the search continues in the upper half.
5. This process is repeated until the target is found or until the search interval becomes
empty.
12

Binary search(Dichotomic search)

Array[Mid]
First=1 last = 5
Mid= (First+Last) div 2 5 6 7 8 9
index 1 2 3 4 5
• Example: V > Array[Mid] so we take the right elements
• We have this sorted Array: Which means First= Mid+1
• We want to search the Value V=8
If V > Array[First] and V < Array[Last]
V doesn’t exist First=4 last = 5
8 9
Mid= (First+Last) div 2
index 1 2 3 4 5

V =Array[Mid] we found the element we stop

the research
13

Complexity
• In computer science and algorithm analysis, "complexity" generally refers to the analysis of an algorithm's efficiency
and resource usage. There are primarily two types of complexity: time complexity and space complexity.
• Time Complexity: evaluates the amount of time an algorithm takes to complete its task, It is measured in terms of the
number of basic operations (comparisons, assignments, etc.) an algorithm performs to solve a problem. Time
complexity is usually denoted using "big O" notation and provides an upper bound on the growth rate of an algorithm
as the input size increases.
• Analyzing complexity is crucial for understanding how algorithms behave with larger inputs. It helps in choosing the
most appropriate algorithm for a particular problem based on the trade-off between time and space efficiency. Lower
time complexity generally means faster execution, while lower space complexity implies efficient use of memory.
• "Big O" notation is widely used to express both time and space complexities. It represents the upper bound of the
growth rate of an algorithm. For instance, O(1) denotes constant time complexity (the algorithm's execution time
remains constant, regardless of the input size), O(n) signifies linear time complexity, O(log n) indicates logarithmic
time complexity, and so on.
• By assessing the complexity of algorithms, programmers and computer scientists can make informed decisions
regarding which algorithms to use based on the specific requirements of a problem, considering factors such as input
size, available memory, and desired execution speed.
14

Binary search VS Linear search

• 1. Linear Search (Sequential Search):

In a linear search, each Array element is checked one by one from the start until the target element is found or the
entire Array is traversed. In the worst-case scenario, when the target element is not present or is at the last position, the
algorithm might have to scan through all 'n' elements. Hence, the time complexity is linear or O(n), where 'n' represents
the number of elements in the Array.
• 2. Binary Search (Dichotomic Search):
Binary search operates on a sorted Array and divides the search interval in half with each iteration. The algorithm
discards half of the remaining elements at each step. In the worst-case scenario, it reduces the search space by half with
each iteration until the target is found or the search space becomes empty. This results in a time complexity of O(log
n),

Comparing the time complexities, binary search has a significantly better worst-case time complexity than linear
search for large datasets. Binary search's logarithmic time complexity makes it much more efficient for finding
elements in sorted Arrays compared to linear search, especially as the size of the dataset grows.
15
Exercise 2
• You are given an Array of 100 integers. Write an algorithm implementing a binary search to find a
specified target value within the Array. The algorithm should return the index of the target value
Algorithm BinarySearch;
const First ← 1;
N = 100;/ Last ←N;
var If (V >= myArray[FIrst] and V <= myArray[Last]) then
targetValue, First,Last, Mid: Integer; While(First<= Last and targetFound <> True ) do
myArray: Array[1..N] of Integer; Mid ←(First+Last) div 2;
targetFound: Boolean; if (myArray[Mid] = targetValue) then
begin targetFound ← True;
// Input elements of the Array Else if (myArray[Mid] < targetValue) First ← Mid+1;
write('Enter the elements of the Array:'); else Last ← Mid-1; EIF;
for i ← 1 to N do EIF;
begin Done;
Read(myArray[i]); EIF;
done; If (targetFound) then
// Ask the user for the target value write(“The target”,targetValue,”is found at the position”,Mid);
write('Enter the target value to search for:'); Else write(“The target”,targetValue,”doesn’t exist”); EIF;
read(targetValue); targetFound ← False; end.
16

2
Sorting Algorithms

Any computer scientist should know at least one sorting

algorithm
17

What’s sorting ?
• Sorting, in the realm of computer science, refers to the process of Arranging elements or data in a specific order,
typically in either ascending or descending order based on a specified criterion. The primary goal of sorting is to
organize the data in a way that makes it easier to search, retrieve, and analyze.
• Here are definitions of a few popular sorting algorithms:
1. Bubble Sort: This algorithm compares adjacent elements in a list and swaps them if they are in the wrong order. It
continues to iterate through the list until no more swaps are needed.
2. Selection Sort: The selection sort algorithm divides the list into a sorted and an unsorted part. It repeatedly selects the
smallest (or largest, depending on the desired order) element from the unsorted portion and moves it to the sorted
part.
3. Insertion Sort Similar to how people sort playing cards in their hands, insertion sort builds the final sorted list one
item at a time. It takes an element from the list and places it in its correct position in the sorted portion.
4. Quick Sort: It’s a divide-and-conquer algorithm, quick sort picks an element as a pivot and partitions the Array
around the pivot, such that elements smaller than the pivot are on its left and larger elements are on the right. It then
recursively sorts the sub-Arrays.
18

Bubble Sort algorithm

The Bubble Sort algorithm works by repeatedly stepping through the list of elements to be sorted, comparing adjacent
elements, and swapping them if they are in the wrong order. This process continues until the entire list is sorted. how the
Bubble Sort algorithm operates:
1. Comparison and Swapping:
- The algorithm starts by comparing the first two elements of the list.
- If the first element is greater than the second one, they are swapped.
- The algorithm moves to the next pair of elements, comparing and swapping if necessary.
2. Iterative Process:
This process continues iteratively through the entire list, moving the larger elements towards the end of the list.
3. Multiple Passes:
The algorithm performs multiple passes through the list, each time guaranteeing that the next largest element is in its
correct position.
4. Termination:
The algorithm continues until no more swaps are needed, indicating that the entire list is sorted.

In simple terms, the algorithm works by 'bubbling' the largest elements to the end of the list in each pass, gradually
sorting the list until no more swaps are required.
19

Bubble Sort Algorithm 2

• For example, consider an Array with elements `[5, 3, 8, 2, 7]`. The Bubble Sort process might look something like this:

• 1. Pass 1: `[3, 5, 2, 7, 8]` (5 and 3 swapped, 8 and 7 swapped)

• 2. Pass 2: `[3, 2, 5, 7, 8]` (5 and 2 swapped)
• 3. Pass 3: `[2, 3, 5, 7, 8]` (3 and 2 swapped)

• The process continues until the entire Array is sorted in ascending order.

• This sorting method is quite intuitive but is less efficient compared to other sorting algorithms, especially for larger
datasets, due to its high time complexity, typically O(n^2) in the worst-case scenario.
20

Bubble Sort Algorithm 3

Algorithm bubble;
Const N←100;
Var a: Array [N] of Integer;
i, temp: Integer;
swapped: Boolean;
Begin // we assume that the Array is already filled up
repeat
swapped ← False; // Reset the flag for each pass
for i ← 1 to N-1 do
if (a[i] > a[i + 1]) then
temp ← a[i];
a[i] ← a[i + 1];
a[i + 1] ← temp;
swapped ← True; // A swap occurred
EIF;
Done;
until (swapped=False); //we stop only when swap occurred
End.
21

Insertion Sort Algorithm

The name "Insertion Sort" comes from the way elements are inserted into their correct positions in the sorted portion of
the array during each iteration. The algorithm works by repeatedly taking an element from the unsorted part of the array
and inserting it into its proper place in the sorted section. This process is akin to how one might sort a hand of playing
cards by repeatedly picking up a card and inserting it into the correct position among the already sorted cards. It works as
follows when we consider the ascending order :
1. Initialization:
The algorithm begins with the assumption that the first element of the array is already sorted.
1. Iterative Comparison and Insertion:
For each subsequent element in the array, the algorithm compares it with the elements to its left in the sorted
portion of the array.
It moves elements greater than the current one to the right until it finds the correct position for the current element.
2. Insertion into Sorted Portion:
The current element is then inserted into its correct position in the sorted portion of the array.
3. Repeat for Remaining Elements:
Steps 2 and 3 are repeated until the entire array is sorted.
22

Insertion Sort Algorithm 2

. Consider the following unsorted Array:
[7, 2, 4, 1, 5]
Now, let's apply the Insertion Sort algorithm into ascending order:
1. Pass 1:
- Assume the first element (7) is already sorted.
- Compare 2 with 7. Since 2 is smaller, shift 7 to the right and insert 2.
- Result: [ 2, 7, 4, 1, 5 ]
2. Pass 2:
- The first two elements (2 and 7) are now sorted. Compare 4 with 7. Shift 7 to the right. Compare 4 with 2. Insert 4.
- Result: [ 2, 4, 7, 1, 5 ]
3. Pass 3:
- The first three elements (2, 4, and 7) are now sorted.
- Compare 1 with 7. Shift 7 to the right. Compare 1 with 4. Shift 4 to the right. Compare 1 with 2. Shift 2 to the right. Insert 1.
- Result: [ 1, 2, 4, 7, 5 ]
4. Pass 4:
- The first four elements are now sorted.
- Compare 5 with 7. Shift 7 to the right. Compare 5 with 4. Shift 4 to the right. Compare 5 with 2. Shift 2 to the right. Compare 5 with 1.
Shift 1 to the right. Insert 5.
- Result: [ 1, 2, 4, 5, 7 ]
5. Final Sorted Array:
- The Array is now fully sorted: [ 1, 2, 4, 5, 7 ]
23

Insertion Sort Algorithm 3

Algorithm InsertionSort; while (j >=1) and (Arr[j] > key) do

Const N ←100; // Shift the elements greater than the key to the right
Arr: Array of [N] of Integer; Arr[j + 1] ← Arr[j];
i, key, j: Integer; // Move one step to the left for the next comparison
Begin j ← j - 1;
// Start iterating from the second element (index 2) to the last element Done;
for i ←2 to N do // Place the key at its correct position in the sorted
// Store the current element to be compared in the key variable Array
key ← Arr[i]; Arr[j + 1] ← key;
//Initialize the index for the comparison to the left of the key done;
j ← i - 1; end;
24

Selection Sort Algorithm

The Selection Sort algorithm is a straightforward sorting algorithm that works by repeatedly selecting the minimum
element from the unsorted part of the array and swapping it with the first unsorted element. This process is repeated until
the entire array is sorted. The algorithm's name, "Selection Sort," stems from its characteristic of selecting the smallest (or
largest, depending on the desired order) element during each iteration. For the ascending order, It works as follow:
1. Initialization:
The algorithm considers the entire array as unsorted initially.
2. Selection of Minimum Element:
It finds the minimum element in the unsorted part of the array.
1. Swapping:
The minimum element is then swapped with the first unsorted element.
2. Incrementing the Sorted Part:
The sorted part is expanded by one element (the minimum element), and one element forms the unsorted part is
reduced.
3. Repeat:
Steps 2-4 are repeated until the entire array is sorted.
25

Selection Sort Algorithm 2

Let's sort our array in ascending order using the selection sort algorithm:

[8, 3, 5, 1, 4]

1. Pass 1:
- Find the minimum element in the unsorted part (1).
- Swap it with the first element (8).
- Result: [1, 3, 5, 8, 4]
2. Pass 2:
- Find the minimum element in the remaining unsorted part (3). Swap it with the first element in the remaining unsorted part (8).
- Result: [1, 3, 5, 8, 4]
3. Pass 3:
- Find the minimum element in the remaining unsorted part (4). Swap it with the first element in the remaining unsorted part (8).
- Result: [1, 3, 4, 8, 5]
4. Pass 4:
- Find the minimum element in the remaining unsorted part (5). Swap it with the first element in the remaining unsorted part (8).
- Result: [1, 3, 4, 5, 8]

Final Sorted Array:[1, 3, 4, 5, 8]

26

Selection Sort Algorithm 3

Algorithm SelectionSort;
arr: Array [N] of Integer;
i, j, minIndex, temp: Integer;
begin
for i ← 1 to n – 1 do
// Assume the current index is the minimum
minIndex ← i;
// Find the index of the minimum element in the unsorted part
for j ← i + 1 to n do
if arr[j] < arr[minIndex] then // Swap the minimum element with the first element in the
minIndex ← j; unsorted part
Eif; temp ← arr[i];
Done; arr[i] ← arr[minIndex];
arr[minIndex] ← temp;
Done;
End.
27

3
Matrix

Not the movie

28

Two-dimension arrays (Matrix)

• A matrix is a two-dimensional array of numbers, symbols, or expressions arranged in rows and
columns. It is a fundamental mathematical concept used in various fields, including computer
science. Matrices are denoted by their dimensions, where the number of rows is specified first,
followed by the number of columns.
• In algorithmic terms, a matrix can be thought of as a grid-like structure where each element is
identified by its row and column index. For example, a matrix A with M rows and N columns is
denoted as A[M][N].
N columns

1,1
M rows

3,4
29

Where we need Matrix ?

• Matrices are used in various areas of science due to their versatile nature. Here are some common areas where
matrices are essential:
1. Graphics and Computer Vision: Matrices are used to represent transformations in computer graphics.
Operations like translation, rotation, and scaling are often expressed using matrices.
2. In computer vision, matrices are used to represent images and perform operations such as convolution for image
processing.
3. Machine Learning and Data Science: Matrices are fundamental in machine learning for representing datasets.
Each row of the matrix can represent a data point, and each column can represent a feature.
4. Networks and Graphs: Matrices are also used in network analysis for representing connectivity between nodes in
a network.
5. Computer Programming: They are employed in algorithms that involve multidimensional data, such as in games
for representing game boards or terrain.
6. Cryptography: Matrices play a role in certain cryptographic algorithms. For instance, they are used in some
encryption and decryption processes.
7. Physics and Engineering: Matrices are extensively used in physics and engineering for modeling physical
systems, especially in the solution of systems of linear equations.
8. Computer Simulations: Matrices are utilized in simulations for representing physical systems, population
dynamics, and other complex interactions.
30

Matrix Syntax
The declaration of a two-dimensional array (matrix) is done as follows:
Name: Array [1..rows , 1..clo] of type;
Or
Name: Array [rows , clo] of type;
Where:
Name: it’s the name of the matrix,
Rows and col: are the dimensions of the matrix,
Rows: the number of rows a matrix should have
Col: the number of columns a matrix should have
Type: the type of elements in the matrix

Example:
Mat: Array[ 3, 4] of Real; // Mat is a matrix of real numbers with 3 rows and 4 columns,
31

Data access in Matrix

Accessing data directly in a matrix involves specifying the row and column indices of the desired
element. In the context of a two-dimensional array, such as a matrix, you would use the syntax
matrix[row][column] to access the data at a particular location.
Example:
Mat [1][1]← 0; // this means the first element of the matrix Mat is set of 0;
Read(Mat [3][2]); // we input by the keyboard at the element found in row 3 and col 2
Write (Mat [2][4]); // we display the value of the element found in row 2 and col 4

We want to display all the elements of the matrix: we need to use two loops, one to represent the rows
and the other to go through the columns

By rows: By columns:
For i ← 1 to 3 do For i ← 1 to 3 do
For j ← 1 to 4 do For j ← 1 to 4 do
write (Write (Mat [i][j])); write (Write (Mat [j][i]));
Done; Done;
Done; Done;
32

Exercise 3
Write an algorithm that finds the maximum value on a matrix with a dimension of N*N where N<=10,
Algorithm Max;
Const N ← 10;
var // Iterate through each element in the matrix
matrix: array[1..N, 1..N] of Integer; for i ← 1 to 3 do
S, maxelement,i,j :integer; for j ← 1 to 3 do
Begin // Update maxElement if a larger element is found
//Input the dimension of the matrix if (matrix[i][j] > maxElement) then
Write(“the dimension of the matrix is:”) maxElement ← matrix[i][j]; EIF;
Read (S); Done; Done;
// Input matrix elements from the user
for i ← 1 to S do // Output the result
for j ← 1 to S do print("The maximum element in the matrix is: ", maxElement);
write("Enter the element at position [", i, "][", j, "]: "); End.
Read(matrix[i][j]); Done;Done;

// Initialize maxElement with the first element of the matrix

maxElement ← matrix[1][1]; // we assume that the first element is the max value
33

3
String

The last of simple types, even though is not that simple

34

Where we need Matrix ?

• Matrices are used in various areas of science due to their versatile nature. Here are some common areas where
matrices are essential:
1. Graphics and Computer Vision: Matrices are used to represent transformations in computer graphics.
Operations like translation, rotation, and scaling are often expressed using matrices.
2. In computer vision, matrices are used to represent images and perform operations such as convolution for image
processing.
3. Machine Learning and Data Science: Matrices are fundamental in machine learning for representing datasets.
Each row of the matrix can represent a data point, and each column can represent a feature.
4. Networks and Graphs: Matrices are also used in network analysis for representing connectivity between nodes in
a network.
5. Computer Programming: They are employed in algorithms that involve multidimensional data, such as in games
for representing game boards or terrain.
6. Cryptography: Matrices play a role in certain cryptographic algorithms. For instance, they are used in some
encryption and decryption processes.
7. Physics and Engineering: Matrices are extensively used in physics and engineering for modeling physical
systems, especially in the solution of systems of linear equations.
8. Computer Simulations: Matrices are utilized in simulations for representing physical systems, population
dynamics, and other complex interactions.
35

Classroom code :
Whz2ikh