29/11/2021

Architecture of
computers & Algorithms

Algorithmics

Track: Preparatory Years for CI (ENSA-BM)

Department: Computer Science
Teacher: Mohammed BOUTALLINE
boutalline@[Link]
[Link]

Where does the word algorithm come from?

Muhammad Ibn Musa al-Khwarizmi (~780-850)

Persian mathematician, geographer, astrologer, and astronomer

3
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

1
 29/11/2021

What is an algorithm?

Is there a problem at the start?

How to sort in ascending order

a sequence of integer numbers?
How to make a
chocolate cake?

How to add 2 numbers?

4
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

What is an algorithm?

Finished set of instructions that transform a

input gives an output

5
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

2
 29/11/2021

What is an algorithm?

For 6 people:
200 g of dark chocolate
4 eggs
150 g of sugar
80 g of flour
200 g of butter
Entrance Exit
mix the egg yolks
...
put in the oven for 20 minutes at 180

finished set of instructions

6
Architecture of Computers & Algorithms @ ENSA - BM Enseignant :Mohammed Boutalline

What is an algorithm?

The input data is called an instance of the problem.

n1equals 18 res = 262

n2= 244 Exit
Entrance

Start by adding the 2 digits of the units

then repeat:
Note the units digit
Retain the tens digit, if there is one
Add the following two digits of n1and n2
and the retention

finished set of instructions

7
Arch. of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

3
 29/11/2021

What is an algorithm?

The input data is called an instance of the problem.

n1= 50839 res = 211575

n2= 160736 Exit
Entry

Start by adding the 2 digits of the units.

then repeat:
Note the units digit
Retain the tens digit, if there is one.
Add the two following digits of n1and n2
and the retention

finished set of instructions

8
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

Write an algorithm
Il n'est pas nécessaire de choisir un langage de
programming
We do not want to depend on the specifics of a language.
we write in pseudo-code also called LDA (Language of
Description of Algorithms

9
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

4
 29/11/2021

Write an algorithm
Problem: finding the minimum in an array of integers
données:un tableau d'entiersrésultat:l’élémentminimum du
table

Principle: we initialize the minimum to the first entry of the array.

Then we go through the other entries of the table one by one.
one while updating the minimum if necessary.

6193 7 11 9 215 5
min 6
min 3
min 2
At the end of the journey, we obtain the minimum

10
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Write an algorithm
Problem: find the minimum in an array of integers
data: an array of integers
result: the minimum element of the array
array: a table of n integers
beginning
min tab[1] we initialize the minimum to the first entry of the array
For i from 1 to n Then we go through the other entries of the
one by one
if min > tab[i]
min tab[i] updating the minimum if necessary
Until yes
End for
Show min At the end of the course, we obtain the minimum.
End

11
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

5
 29/11/2021

Write an algorithm
Problem: searching for the element x in an array of integers
données:un tableau d'entiers n et un entier
résultat:l'indice de l'entier recherché dans le tableau s'il s'y
find, -1 otherwise

How?

12
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Write an algorithm
Note:
When you are well acquainted with an algorithm to solve a
problem, we can deduce others to solve others
similar problems by making small changes

We talked about improvement, but what does that mean?

How to compare two algorithms solving the same problem

on the same instances?

13
Architecture of Computers and Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

6
 29/11/2021

Write an algorithm
Problem: find the minimum in an array of integers
data: an array of integers
result: the minimum element of the array
Principle: divide and conquer

6 19 3 7 11 9 2 15 5

6 3 9 2 5
if T has more than one element
Divide the table in two
sub-arrays T1and T2
calculate the minimum, min1of T1 9 2
calculate the minimum, min2from T2
return the minimum of min1and
min2 3 2
otherwise return the unique element of T
2
14
Architecture of Computer Systems & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Compare two algorithms

compare the execution speeds on the same instances
efficient algorithm

count the number of elementary operations performed

during the course of the algorithm
today: 1 elementary operation ~ 1 nanosecond (10-9s)
2. choose a good data structure
Study of time complexity
Compare the memory space required for the instances
Choose a good data structure
Study of space complexity
3. Readability of the algorithm, simplicity of the principle, simplicity of
the implementation...
Note that there are algorithms for which
We do not know of an effective solution! 15
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

7
 29/11/2021

The traveling salesman problem

Khouribga
Casablanca
Settat
the shortest round passing
through all the villages?

Marrakech
Khénifra
Tadla
Azilal
No other known algorithm than to
calculate all possible rounds!
No effective solution!

16
Computer Architecture & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

1 elementary operation ~ 1 nanosecond (10-9s)

Data size

names of elementary operations

And there are problems that we do not know how to solve with a
algorithm!
17
Computer Architecture & Algorithms @ ENSA - BM Enseignant :Mohammed Boutalline

8
 29/11/2021

The problem of termination

Can we write an algorithm A that solves the problem of the

square root with any instance I?

Un+1=1/2*(Un+a/Un)
with Un1

18
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

The problem of stopping

Write an algorithm that calculates the square root of the

positive real value thanks to the recursive formula
Un+1=1/2*(Un+a/UnThe calculations must begin
with 1 as the initial value of U0and stop when the
absolute value of the difference between the last two
calculated values are strictly less than 0.001.

19
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

9
 29/11/2021

Knowing algorithms allows for the design of new ones

governed by a similar principle
Lecture, modification, and writing of algorithms

An algorithm must be efficient in order to provide a

response in a reasonable time using a space in
reasonable memory.
Study of the complexity of an algorithm

20
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

Exercise
Write an algorithm that asks for a starting number, and
who calculates its factorial.

10
 29/11/2021

Structure of an algorithm

Algorithmics: involves designing and developing

algorithms describing the solutions of a certain type of
problems.

Algorithmics consists of two major phases: (Analysis and

Conception.

Algorithm: is a finite sequence of instructions to be applied

in a determined order on data in order to achieve a
certain result in a finite time.

22
Arch. of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Structure of an algorithm

Programming language: is a tool

entirely formalized with common language words
and specific rules to express algorithms.
Examples (PASCAL, C, C++, JAVA…).

•Program: Translation of an algorithm into a language of

special programming.

Problem Algorithm Program Results

Algorithmics
Programming Compilation
(Analysis
(Language of +
+
programming Execution
Conception

23
Architecture of Computers & Algorithms @ ENSA - BM Enseignant :Mohammed Boutalline

11
 29/11/2021

Structure of an algorithm

Analyze: the clearing of entries, exits and the

treatment.

Conception: organizing in a suitable order in order to

to achieve the expected results.

Compilation: transformation into machine language of a

program written in advanced language

Execution: the computer executes the instructions of a

program in 'binary' language, to provide the result.

24
Computer Architecture and Algorithms @ ENSA - BM Enseignant :Mohammed Boutalline

Structure of an algorithm

An algorithm can be structured in three parts

main:

The header

The declarations section

The body of the algorithm

25
Architecture of Computers & Algorithms @ ENSA - BM Enseignant :Mohammed Boutalline

12
 29/11/2021

Structure of an algorithm

Example:

Algorithm: calculation of the area of the Circle; Header

VariablesRayon, Surface:Réel;
Declaration Party
ConstantPi 3.14

Start

ReadRayon

Surface Rayon*Rayon*Pi; Body

To write(Surface);

End

Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Basic instructions
Data Affectation
Entrées Outputs

A data point is characterized by three attributes:

Identifier
Value
Type Value
Identifier
3.14
Pi
Example
Data

Type
Real
27
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

13
 29/11/2021

Data

Type (in algorithms)

Type Description
A data of this type takes its values
Entier in [-32768,32767]
Takes its values in the scale 2.9x10-39
Real at 1.7x 10+38with 11 significant figures
after the comma
Take its values from the code table
Character ASCII exp'A','S'

logic Can take the value True or False

28
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Data

A piece of data is divided into two categories:

Variable: data whose value is likely to vary.

Syntax:
variableidentifier_var :type;
Example: variable surface : real;

Constant: data whose value is fixed.

Syntax:
constant_identifier_const value
example:constantPi 3.14

29
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

14
 29/11/2021

Affectation

An assignment is the operation that allows you to organize the

value of an expression in a variable.
An expression is a combination of operands
and operators.

Some arithmetic operators:

Algorithmic Meaning
+ Addition
- Subtraction
* Multiplication
/ Division
mod Remainder of the integer division
30
Architecture of Computers & Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Comparison

Some relational operators:

Algorithmics Meaning
= Equal
<> Different
< Inferior
> Superior
<= Less than or equal to

>= Greater than or equal to

31
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

15
 29/11/2021

Logical operator

Some logical operators:

Algorithmics Meaning
No Negation
OU Or logic
ET And Logic

32
Computer Architecture and Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Reading and Writing Instructions

Lecture
Simply put, for which user among the (new)
value of the radius, we will put:

Read (Radius);

As soon as the program encounters a Read instruction,

the execution is interrupted, waiting for the value hit at
keyboard. The interruption can last a few seconds, a few
minutes or several hours: the only thing that will make it happen
the continuation of the instructions is that the Enter key has been
sunk.

33
Computer Architecture and Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

16
 29/11/2021

Reading and writing instructions

Writing
In the opposite direction, to write something on the screen, it is
as simple as:

Write (Rayon);

Before reading a variable, it is highly recommended

to write labels on the screen, in order to warn the user about this
that he must strike

Write("Enter the radius of the circle:");

Read(radius);

Write(" The radius of the circle is: ", radius);

34
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

Exercise
Write an algorithm that asks for the Excluding Tax Price (PHT)
of an item, calculate and display the price to pay (including taxes) knowing

that the VAT is set at 20%. We assume that these values

are real

17
 29/11/2021

Tests = Structures conditionnelles

We distinguish four types of conditional structures:

1. Conditional operator

[Link] choice structure

3. Structure of alternative choice

[Link] Choice Structure

36
Arch. of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

Conditional operator

(Expression logique)?Expression Si Vrai:Expression Si Faux

The conditional expression begins with a test followed by

of the character? then the value when the test is true then the
character: and finally the value when the test is false.
Example:
If (age>=18) then write ("He/She is an adult"); else write ("He/She is minor");

minor";

Write an algorithm (a program in C language) that

display if an integer is even or odd.
37
Arch. of Computers & Algorithms @ ENSA - BM Enseignant :Mohammed Boutalline

18
 29/11/2021

Simple choice structure / alternative choice structure

There are only two possible forms for a test; the first
is the simplest, the second the most complex.

SibooléenThen SibooléenThen
Instructions Instructions 1
Finally yes Otherwise
Instructions 2
End if
This calls for some explanations.
Boolean is an expression whose value is TRUE or FALSE.
So it can be (there are only two possibilities):
a variable (or an expression) of boolean type
a condition
It would thus be much more rational to intertwine the tests
38
Architecture of Computers and Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

Exercise
Write an algorithm (a program in C language) that
solve the second degree equation (a.x2+b.x+c=0)
in IR.

19
 29/11/2021

Multiple choice structure

According to which expression is valid

valeur 1: instruction 1;

valeur 2: instruction 2;

valeur 2: instruction 3;

value n: instruction n;
otherwise instruction n+1;
End according to

40
Architecture of Computers & Algorithms @ ENSA - BM, Teacher: Mohammed Boutalline

Exercise
Write an algorithm that displays the corresponding day for
the integer entered via the keyboard.

20
 29/11/2021

More Logic

Should we use an AND? Should we use an OR?

A remark to begin with: in the case of conditions
In compositions, parentheses play a fundamental role.
It's too hot, and it's not raining, so
Open the window
Otherwise
Close the window
End if

It's not too hot OR it's raining.

Close the window
Otherwise
Open the window
Well then

These two formulations are strictly equivalent.

42
Architecture of Computers and Algorithms @ ENSA - BM Teacher: Mohammed Boutalline

21