Lecture Notes :
Algorithms
3rd week: Static Arrays
Academic year : 2023-2024.
1st Year Mathematics License,
Faculty of Mathematics,
University of Science and Technology Houari Boumediene.
Content :
• Brief recap.
• 1st Class: Working with 1D Arrays.
• 2nd Class: Working with 2D Arrays.
1/32
Working with 1D Arrays
Is one cell enough?
• Maybe! Let’s write an algorithm to input the grades of all 450 students enrolled in
Mathematics and then calculate the overall average.
Algorithm ClassAverage;
Var sum, i : integer;
average, grade : float;
Const nbStudents = 450;
Begin
sum <- 0;
For i <-0 to nbStudents do
Write("Enter the grade value: ");
Read(grade);
sum <- sum + grade;
EndFor;
average <- sum/nbStudents;
Write("The overall average of the Math class is: ", average);
End;
2/32
Is one cell enough?
• We lost all the grades! what if we had to find grades that are less than 10? or find the
best student in this math class?
Algorithm ClassAverage;
Var g1, g2, g3, ..., g450 : integer;
average, grade : float;
Begin
read(g1);
read(g2);
read(g3);
...
read(g450);
average <- (g1+g2+g3+...+g450)/nbStudents;
Write("The overall average of the Math class is: ", average);
End;
3/32
Isn’t there a simpler, more elegant way to write this?
• One can imagine a simple data structure, that groups the cells g1, g2, ..., g450.
• This structure is present in all programming languages.
• usually under the name array.
g1
g
g2 g[1]
g[2]
g3 −→ g[3]
.. ..
. .
g[450]
g450
4/32
What is an Array?
Definition
• A set of values bearing the same variable name and type, and identified
by a number is called an array.
• The number used to identify each value in an array is called the index
• Each element of an array is designated by the name of the array, followed
by followed by the element index, enclosed in square brackets.
Values
42 17 8 30 55
g[0] g[1] g[2] g[3] g[4]
Indices
5/32
Properties of an Array
• The number of elements in an array is called its size.
• The dimension of an array is the number of its indices.
Example
A : A[1] A[2] ... A[100]
• The variable name is A.
• The size of A is : 100 (the number of elements).
• Its dimension is : 1 (the number of indices).
6/32
Array Declaration
Syntax
var <array_ID>[<size>] : <type>;
Example
A : A[1] A[2] ... A[100]
• The variable name is A.
• The size of A is : 100 (the number of elements).
• Its dimension is : 1 (the number of indices).
• var A[100] : Integer;
• var A[100] : float;
7/32
Useful Algorithms: Filling an Array
We can assign a value to an array element using its index : <array_ID> ← <value>;
Example: A[2] ← 5; A: 5 ...
Algorithm Assignment_Array;
Var A[100], i : integer;
Begin
For i <- 1 to 100 do
A[i] <- 5;
EndFor;
End;
A: 5 5 ... 5
8/32
Useful Algorithms: Filling an Array
We can assign a value to an array element using its index : <array_ID> ← <value>;
We can fill an array with user input values using I/Ö operations :
Algorithm Fill_Array;
Var A[100], i, inter : integer;
Begin
For i <- 1 to 100 do
Write("Enter the ", i ,"th value ");
Read(inter);
A[i] <- inter;
EndFor;
End;
9/32
Useful Algorithms: Filling an Array
We can assign a value to an array element using its index : <array_ID> ← <value>;
We can fill an array with user input values using I/Ö operations :
Algorithm Fill_Array;
Var A[100], i : integer;
Begin
For i <- 1 to 100 do
Write("Enter the ", i ,"th value ");
Read(A[i]); // Input value directly to array A
EndFor;
End;
10/32
Back to Students Example
Algorithm ClassAverage;
Var i : integer ;
grade[450], average, sum : float ;
Begin
For i <- 0 to 450 do
Write("Enter the grade value: ");
Read(grade[i]);
EndFor;
For i <- 0 to 450 do
sum <- sum + grade[i];
EndFor;
average <- sum/450;
Write("The overall average of the Math class is: ", average);
End;
11/32
Back to Students Example
Minimal Algorithm (optimal)
Algorithm ClassAverage;
Var i : integer ;
grade[450], average : float ;
Begin
For i <- 0 to 450 do
Write("Enter the grade of student ", i);
Read(grade[i]);
average <- average + grade[i]/450;
EndFor;
Write("The overall average of the Math class is: ", average);
End;
12/32
Example: Sequence
√
Let (Un ) be a sequence, where Un = 7 n − 2n2 . Write an algorithm that calculates the first
10 elements of (Un ), and store them into an array named U.
Algorithm Sequence_Example;
Var i : integer ;
U[10] : float ;
Begin
For i <- 0 to 10 do
U[i] <- 7*sqrt(i)-2*n**2;
EndFor;
For i <- 0 to 10 do
write("The ", i, " th element of the sequence U is ", U[i]);
EndFor;
End;
13/32
Example: Fibonacci Sequence
Let (Fn ) be a sequence, where Fn+1 = Fn + Fn−1 , and F1 = F2 = 1. Write an algorithm
that calculates and store the first 10 elements of (Fn ).
Algorithm Fibonacci_Sequence;
Var i : integer ;
F[10] : float ;
Begin
F[1] <- 1; F[2] <- 1;
For i <- 2 to 9 do
F[i+1] <- F[i] + F[i-1];
EndFor;
For i <- 0 to 10 do
write("F[", i, "] = ", F[i]);
EndFor;
End;
14/32
Useful Algorithms: Find the Maximum Value
Let T be an integer array of size 100. Write an algorithm that finds the maximum value in T.
Algorithm Find_Max;
Var i, T[100], max: integer ;
Begin
// fill the array T
max <- F[1];
For i <- 2 to 100 do
If (max < F[i]) then
max <- F[i];
EndIf;
EndFor;
write("The maximum value is ", max);
End;
15/32
Useful Algorithms: Inverse Array
Let T be an integer array of size 100. Write an algorithm the order of elements in T.
Algorithm Inverse_Array;
Var i, j, inter, T[100]: integer ;
Begin
// fill the array T
i <- 1;
j <- 100;
While (i<j) do
inter <- T[j];
T[j] <- T[i];
T[i] <- inter;
i <- i+1;
j <- j-1;
EndWhile;
End;
16/32
Useful Algorithms: Inverse Array
Let T be an integer array of size 100. Write an algorithm that inverses the order of elements
in T.
Algorithm Inverse_Array;
Var i, inter, T[100], n: integer ;
Begin
// fill the array T
i <- 1;
n <- 100;
While (i<n) do
inter <- T[n-i+1];
T[n-i+1] <- T[i];
T[i] <- inter;
i <- i+1;
EndWhile;
End;
17/32
Example: Separates Even and Odd Values in T into Two Arrays T1 and T2
Algorithm Odd_Even_Arrays;
Var i, j, k, T[100], T1[100], T2[100]: integer ;
Begin
// fill the array T
j <- 1;
k <- 1;
For i <- 1 to 100 do
If (T[i]%2 = 0) then
T1[j] <- T[i];
j <- j+1;
Else
T2[k] <- T[i];
k <- k+1;
EndIf;
EndFor;
End;
18/32
Useful Algorithms: Search Element in Array
Let T be an integer array of size 100. Write an algorithm that prints the index of an input
value V.
Algorithm Search_Array;
do
Var i, index, T[100]: integer ;
If(T[i] = V) Then
f : boolean;
b <- true;
Begin
index <- i;
// fill the array T
EndIf
i <- 1;
i <- i+1;
f <- false;
while(f=true)
write("Enter a value");
write(V, " is at index", index);
read(V);
End;
19/32
Useful Algorithms: Count Occurrence in Array
Let T be an integer array of size 100. Write an algorithm that prints the number of
occurrence of an input value V.
Algorithm Count_Occ_Array;
Var i, counter, T[100]: integer ;
Begin
counter <- 0;// and fill the array T
write("Enter a value");
read(V);
For i <- 1 to 100 do
If (T[i]=V) then
counter <- counter +1;
EndIf;
EndFor
write("Nb occurrence of ", v, " is ", counter);
End;
20/32
Special case of Arrays : String
In algorithms, a string is an array of characters. It’s a data structure that holds a
sequence of individual characters, such as letters, digits, or symbols.
The string "Hello" can be represented as an array: [’H’, ’e’, ’l’, ’l’, ’o’].
• The symbol " is used to delimit a string of characters.
• The string "Baobab" is composed of the characters ’B’, ’a’, ’o’, ’b’, ’a’, and ’b’.
• The string "123" consists only of digits, but it should never be confused with the
numerical value 123.
• The string "" represents an empty string.
• The string " " is a string containing only one character, which is the space character
(not to be confused with an empty string).
21/32
ASCII Code
ASCII (American Standard Code for Information Interchange) is a character encoding
standard used in computers and communication equipment.
It represents text and control characters as numerical values, which are widely
used to encode characters in digital communication.
ASCII uses 7 or 8 bits to represent characters, with 128 standard characters in
the 7-bit version and 256 characters in the 8-bit version (extended ASCII).
• Character: A → ASCII Value: 65.
• Character: 3 → ASCII Value: 51.
22/32
ASCII Code Table
0 NUL 16 DLE 32 48 0 64 @ 80 P 96 ’ 112 p
1 SOH 17 DC1 33 ! 49 1 65 A 81 Q 97 a 113 q
2 STX 18 DC2 34 " 50 2 66 B 82 R 98 b 114 r
3 ETX 19 DC3 35 # 51 3 67 C 83 S 99 c 115 s
4 EOT 20 DC4 36 $ 52 4 68 D 84 T 100 d 116 t
5 ENQ 21 NAK 37 % 53 5 69 E 85 U 101 e 117 u
6 ACK 22 SYN 38 & 54 6 70 F 86 V 102 f 118 v
7 BEL 23 ETB 39 ’ 55 7 71 G 87 W 103 g 119 w
8 BS 24 CAN 40 ( 56 8 72 H 88 X 104 h 120 x
9 HT 25 EM 41 ) 57 9 73 I 89 Y 105 i 121 y
10 LF 26 SUB 42 * 58 : 74 J 90 Z 106 j 122 z
11 VT 27 ESC 43 + 59 ; 75 K 91 [ 107 k 123 {
12 FF 28 FS 44 , 60 < 76 L 92 \ 108 l 124 |
13 CR 29 GS 45 - 61 = 77 M 93 ] 109 m 125 }
14 SO 30 RS 46 . 62 > 78 N 94 ∧ 110 n 126 ∼
15 SI 31 US 47 / 63 ? 79 O 95 _ 111 o 127 DEL
23/32
Comparing String
In algorithms, strings are often compared character by character using their ASCII
codes.
• Each character in a string is represented by a numeric ASCII code, which allows for
lexicographic comparison.
• Smaller ASCII code values indicate earlier positions in the ordering.
Example
• Compare "apple" and "banana."
• Compare characters one by one:
’a’ (97) < ’b’ (98), hence, "apple" is lexicographically smaller than "banana."
• This is how many algorithms sort and compare strings.
24/32
Example : Is It a Palindromes?
Let S be a string (an array of characters) of size 7. Write an algorithm that checks if S is a
palindrome. A Palindrome is a word or a phrase that reads the same forwards and backward.
Ex., "racecar".
Algorithm Palinfrome;
repeat
Var i : integer ;
If (S[i] != S[n-i+1]) then
S[7] : Character;
b = false;
V : boolean;
EndIf;
Begin
i <- i+1;
i <- 1;
Until (b = false or i >= n/2)
b <- true;
If(b=true) then
write("Enter a string");
write("It’s a Palyndome");
\\ Type a word of 7 letters max
EndIf;
n <- 7;
End;
read(S);
25/32
Working with 2D Arrays
2D Arrays (Matrix) : Structure
Two-dimensional arrays generally take the form of a set of rows and columns
(matrix). Consequently, each element is identified by two indices.
The following structure is a two dimensional array for size n×m.
M[1][1] M[1][2] ... M[1][m]
M[2][1] M[2][2] ... M[2][m]
M:
.. .. ..
. . .
M[n][1] ... ... M[n][m]
26/32
2D Arrays (Matrix) : Declaration
Syntax
Var <array_ID>[<nb_lines>][<nb_columns>] : <type>;
Let M be a two dimensional array for size 2×3.
M[1][1] M[1][2] M[1][3]
M:
M[2][1] M[2][2] M[2][3]
Declaration : Var M[2][3] : integer;
• The number of indices is : 2 (dimension).
• The size of a two dimensional matrix is the product of the number of columns times the
number of lines.
27/32
2D Arrays (Matrix) : Utility
• The utility of a two-dimensional array lies in the ability to declare a single array
instead of declaring multiple identical arrays.
Example
In fact, a 2D array ca, be equivalent to 10 separate 1D arrays, each with 20 elements.
In other words, the declaration:
Notes[10][20] : float;
Replaces this:
Notes1[20], Notes2[20], ..., Notes10[20] : float;
28/32
Useful Algorithms: Filling a 2D Array
We can fill an array with user input values using I/Ö operations :
Algorithm Fill_Array;
Var A[100][50], i, j : integer;
Begin
For i <- 1 to 100 do
For j <- 1 to 50 do
Write("Enter a value ");
Read(A[i][j]); // Input value directly to array A
EndFor;
EndFor;
End;
29/32
Useful Algorithms: max/min value in a 2D Array
Let M be a 20 by 50 matrix, write an Algorithm that prints the minimum value in M.
Algorithm Fill_Array;
Var A[20][50], i, j, min : integer;
Begin // fill the matrix
min <- A[1][1];
For i <- 1 to 20 do
For j <- 1 to 50 do
If(min > A[i][j]) then
min <- A[i][j];
EndIf;
EndFor;
EndFor;
write("The minimum value in M is : ", min);
End;
30/32
Useful Algorithms: max/min value in a 2D Array in each row
Let M be a 20 by 50 matrix, write an Algorithm that prints the minimum value in each row
of M and store them in an array T.
Algorithm Fill_Array;
Var A[20][50], i, j, min, T[20] : integer;
Begin // fill the matrix
For i <- 1 to 20 do
min <- A[i][1];
For j <- 1 to 50 do
If(min > A[i][j]) then
min <- A[i][j];
EndIf;
T[i] <- min;
EndFor;
EndFor;
write("The minimum value in M is : ", min);
End;
31/32
Useful Algorithms: max/min value in a 2D Array in each column
Let M be a 20 by 50 matrix, write an Algorithm that prints the minimum value in each row
of M and store them in an array T.
Algorithm Fill_Array;
Var A[20][50], i, j, min, T[50] : integer;
Begin // fill the matrix
For j <- 1 to 50 do
min <- A[1][j];
For i <- 1 to 20 do
If(min > A[i][j]) then
min <- A[i][j];
EndIf;
T[j] <- min;
EndFor;
EndFor;
write("The minimum value in M is : ", min);
End;
32/32