University of Ngaoundéré Academic year 2022/2023

Faculty of Sciences License 1

Department of Mathematics and Computer Science Computer Science/Mathematics Course
TD INTRODUCTION TO ALGORITHMS (INF131)

I. BASIC NOTIONS
Exercise 1: Definitions and questions
1.Définir : Algorithmique, Algorithme, Identificateur, Variable, Type de donnée
2. Draw the diagram of the steps in the development of a computer program.
3. What are the characteristics of a good algorithm
4. What is the purpose of a loop in an algorithm?

Exercise 2: System of equations

Write an algorithm that reads six real numbers a, b, c, d, e, and f and calculates the solution of the system.
ax by c
equations .
dx hey f

Exercise 3: Security in an enclosure

We want to secure a pressurized enclosure. We set a threshold pressure and a threshold volume:
pSeuil=2.3 et vSeuil=7.41.
We ask to enter the current pressure and volume of the chamber to write a script that simulates the
following behavior:
if the volume and pressure are above the thresholds: display 'immediate stop';
if only the pressure is above the threshold pressure: display "increase the volume of
the enclosure
if only the volume is above the threshold volume: display 'decrease the volume'.
otherwise display "everything is fine".

Exercise 4: The year is a leap year

A year is a leap year if it is a multiple of 4, and if it is also a multiple of 100, it must
also must be a multiple of 400. For example:
1985 is not a multiple of 4, that is to say, 1985 modulo 4 ≠ 0;
1996 yes because 1996 modulo 4 = 0 and 1996 is not a multiple of 100.
1900 not because it is a multiple of 4 and also a multiple of 100 however it is not a multiple
de400.
2000 yes because it is a multiple of 4, also a multiple of 100 and still a multiple of 400.
Write a function that takes a year as an argument and returns 1 if it is a leap year and 0 otherwise.

Exercise 5: Conditional diagram according to case value

Write an algorithm that asks the user for a month number (between 1 and 12) and
indicate back its name and the number of days in this month. It is about comparing a value to a
predefined list: the conditional scheme according to the value to use.

Exercise 6: Conditional scheme if() then

Write an algorithm that uses three real numbers a, b, c and informs whether the terms of the list
L = [a, b, c] are arranged in ascending order, in descending order, or neither.
Exercise 7: Permutation
1. Write an algorithm that asks the user to input 2 real numbers and then the
permutes using an intermediate variable.
2.Rewrite the same algorithm without using an intermediate variable.
List the advantages of both algorithms.

1
University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Track
TD INTRODUCTION TO ALGORITHMS (INF131)

Exercise 8: Logical expressions

1. Write an algorithm that asks the user for two numbers and indicates whether the product of these
Two numbers are negative, positive, or null. Note: We impose not to calculate the product.
2.Rewrite the three (03) following procedures without using compound conditions.
a) b) c)
F1(x, y, z : integer) procedure F2(a, b, c, d : integer) procedure F3 (a, b, c, d : integer)
debut debut debut
if (x < y) or (w < z) then if(a≠b) and((c = 5) or (d = 1)) then if (a ≠ b) or ((c = 5) and (d = 1)) then
write('Hello'); Hello write('Hello');
otherwise otherwise otherwise
Good evening Good evening Good evening
fsi fsi fsi
end end end

Exercise 9: Identify a triangle

The lengths of the sides of a triangle are stored in the real variables a, b, and c. For a, b
and they are indeed correct, the sum of any two of the three numbers must be
strictly greater than the third. Write an algorithm that reads three real numbers a, b, and c and
determine if a, b, and c are indeed the sides of a triangle. If yes, then write the message
Triangle » otherwise write the message « Not a triangle ».

Exercise 10: Equation of the 2nddegree

Write an algorithm that reads three real numbers a and b, then calculates the real solutions of
the quadratic equation ax² bx c 0 .

Exercise 11 Posting your letter

The postage rates for a letter are as follows: under 20g: 280 FCFA, from
for 20g, but below 50g: 440 FCFA, from 50g: 670 FCFA. Write an algorithm that reads
the weight of a letter and prints the postage amount of the letter.

Exercise 12: Alcoholic beverage

If a driver has between 0.5 and 0.8 grams of alcohol per liter of blood, they face a suspension of
6-month license suspension and a fine of 2000 francs for each decigram over 0.5 grams,
0.5 grams included.
If the driver has between 0.8 and 1 gram of alcohol in the blood, he faces a 24 license suspension.
month and a fine of 3000 francs per decigram over 0.5 grams, 0.5 grams
including.
Beyond 1 gram, the driver re-takes their license and pays a fine of 5,000 francs.
One liter of pure alcohol weighs 800 grams. An adult man has approximately 8 liters of blood. A
A 45° alcohol bottle contains 45% alcohol.
For reference, a 10 cl glass of alcoholic beverage at 10° results in a blood alcohol level of 0.1 g per liter.
of blood.

Write an algorithm that calculates the fine to be paid and the license withdrawal time, the amount of
drink and the alcohol content of each drink being recorded.

2
University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Pathway
TD INTRODUCTION TO ALGORITHMS (INF131)

Exercise 13: The day of a date

We want to write an algorithm to calculate the day of the year knowing the month and the day of the month.
the year. For example, if the input to the algorithm is "2 7 1983" the output of the algorithm would be "the
February 7, 1983 is the 38ththday of the year 1983.

Exercise 14: Loops

We want to input the number of a month (between 1 and 12) with verification. The
the principle is that if the input is incorrect, the program displays a message explaining the error of
Input and request the user to re-enter the data.
We will use a Repeat to perform controlled input.
Use a While loop to perform controlled input.

Exercise 15: Sequence

Let (un) nIN∊the defined sequence appeared0 = 1 and the recurrence relation: un+1= 3un-1
valid for everyone∈ N. Soitn∈ N.
1. Write an algorithm that displays the value of deu.n.
n
2. Write an algorithm that displays the value of the sum S.defined
n
byI S. u
i 0

Exercise 16: Series of numbers

Write an algorithm that reads a sequence of positive numbers ending with -1 and determines the highest.
great of these numbers as well as its position in the list.

Exercise 17: Series of numbers

Write an algorithm that reads a sequence of real numbers ending with -1 and displays the number of
real positives, nulls and negatives in the series. It is assumed that the last number read (that is -1) makes
part of the series.

Exercise 18: Perfect number

A number is said to be "perfect" if it is equal to the sum of all its divisors except itself. Write
the algorithm that indicates whether a number entered from the keyboard is perfect or not.

Exercise 19: Fibonacci Sequence

The medieval researcher Leonardo (Fibonacci) of Pisa proposed the infinite sequence in which each
the term is the sum of the two previous terms. The nththe Fibonacci name is defined
recursively in the following manner:
If n is equal to 0 or 1 then nèmeFibonacci number is equal to n,
If n is greater than or equal to 2 then nemeFibonacci number is equal to the sum of the two
previous Fibonacci names.
Write an algorithm that calculates and prints the first 100 Fibonacci numbers.

Exercise 20: Calculation of sin(x)

We would like to calculate sin(x) up to the given order N. Knowing that the limited development of

x x x x x x
3 5 7 9 2n1
x 2n1
sin(x)   ... (
n
... For that we set A  1  n
3! 5! 7! 9! (2n 1)! (2n 1)!
1. Give the value of U0;U1;U2;U3.
2. The Taylor series of cos(x) of order N is equal to S=U0+U1+U2+ . . .+U N.

3
University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Track
TD INTRODUCTION TO ALGORITHMS (INF131)

U 1
3. Find the relation r between two consecutive terms of the sequence Un by calculating r.
.
Un
4. Write an algorithm that asks the user to enter the value of X and then calculates it.
and display the value of sin(x) up to order N=50.
5. What is the number of times your algorithm executes the operators × (multiplication)
and / (division).

Exercise 21: The clock

1. Write an algorithm that asks for the time in numbers (one number for the
hours, one for minutes and one for seconds). This algorithm will then indicate whether it is
of a valid hour or not.
2. Write an algorithm that reads a time and displays the time it will be in eighteen (18) seconds.
later. For example, if the user types 21, 32, and 12, the algorithm should respond: 'In 18
seconds, it will be 9:32:30 PM.
Note: It is assumed that the user enters a valid time. Therefore, there is no need to verify it.

Exercise 22: Sentence

Write an algorithm that reads a sequence of characters representing a sentence and displays the longest word
long and the number of words read. It is reminded that two consecutive words are separated by a single space.
" " and the sentence ends with a period.

Exercise 23: While loop and for loop

We want to calculatenfor a real number and a positive integer n.
1. Write two versions of this algorithm, the first version will use the do-while loop.
Second will use the loop.
2. Evaluate based on a and/or n the number of loop iterations necessary to calculate anwith
n
each of your algorithms. We now want to calculate ai
i 0
3. Write an algorithm Sum-Powers that uses the power algorithm. Evaluate based on.
n
the number of loop iterations required for calculation a i .
i 0

4. Write a second version of the algorithm to calculate a iby searching this time-
i 0
it to optimize the number of loop iterations.

Exercise 24: Greatest Common Divisor

Calculation of the Greatest Common Divisor (GCD) of two strictly positive integers
3. By the Euclidean algorithm:
The GCD of a and b is equal to a if the latter divides a, otherwise the GCD of a and b is equal to
GCD must be of r (where r represents the remainder of the Euclidean division of a and b).
a. Write the GCD algorithm using the modulo operator.
What happens if a < b?
4. By subtraction:
If Sia = b, then GCD = a, otherwise we start again with the pair formed by the difference between
the largest and the smallest.
a. Write the corresponding algorithm using a while loop.
b. Provide an increase in the number of comparison tests.

4
 University of Ngaoundéré Academic year 2022/2023
Faculty of Science License 1
Department of Mathematics and Computer Science Computer Science/Mathematics track
TD INTRODUCTION TO ALGORITHMICS (INF131)

II. COMPOSITE OBJECTS

Exercise 1: Number of occurrences

Let it be an array of integers where the elements are already sorted.
1. Write an algorithm that displays all the elements whose number of occurrences
exceeds three (03).
2. Write an algorithm that displays the number of elements and the number of occurrences.
exceeds three (03).
3. Write an algorithm that displays the number of occurrences of each element in the array.

Exercise 2: Vector of ordered elements

1. Modify the bubble sort to obtain a vector sorted in descending order.
2. Modify the selection sort to obtain a vector sorted in descending order.
3. Modify the insertion sort to obtain a vector sorted in descending order.
4. Write an algorithm to calculate the union of two sets represented by vectors.
5. Write an algorithm to calculate the intersection of two sets represented by vectors.
6.Write an algorithm to calculate the set difference of two sets represented by
vectors.
7.Write an algorithm to calculate the symmetric difference of two sets represented by
vectors.

Exercise 3: Matrix
Let A and B be 2 real matrices with m rows and n columns and D a real matrix with n rows of p.
columns
1.Write an algorithm that calculates and displays the sum of matrices A and B.
2. Write an algorithm that calculates and displays the product of matrices A and D.
3. Write a function that takes A as input and returns the largest element of this matrix.
4. Write a procedure that takes A as input and returns the largest element as a parameter.
this matrix as well as its row/column position.

Exercise 4: Execution of an algorithm

UnnamedAlgorithm
const N = 200;
ARRAY [1..N] of real;
var
Tab: Vector;
Permute: boolean;
beginning
Write('Give the number of elements in the array');
read(Number);
j=1 ;
repeat
Permute Fake;
pouri 1 to Nbre-j do
if(Tab[i] < Tab[i+1]) then
Val Tab[i] ; Tab[i] Tab[i+1] ; Tab[i+1] Val ;
Permute True;
finish
fpr
j j+1 ;
until (Permission=False)
end

5
University of Ngaoundéré Academic year 2022/2023
Faculty of Science License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Pathway
TD INTRODUCTION TO ALGORITHMS (INF131)

The sequence of actions (Val Tab[i] ; Tab[i] Tab[i+1]; Tab[i+1] Val ;) constitutes a (01)
permutation. The actions (Tab[i]<Tab[i+1]) and (Permut=false) make two (02) comparisons. We
Suppose that comparisons and permutations are the only operations to be considered.
to evaluate the execution time of the algorithmWithoutName.
1. Let Tab be a vector containing the following real values in the order of increasing indices:
20, 60, 22, 5, 11, 4, 2, 20, 9, 11, 8, 2.
What is the content of the vector Tab when j=2 and i=10.
What is the value of Val and of Permut for j=4 and i=8.
What is the content of the vector Tab when j = 8 and i = 5?
Is it possible to have j=10 and i=5? Justify.
2. Provide the final result of the AnonymousAlgorithm. What does this algorithm do?
3. For any value of N, what is the number of comparisons and the number of
necessary permutation to execute the AlgorithmWithoutName?

Exercise 5: Recording
In the mathematics department of the University of Ngaoundéré, a student is characterized by
his registration number, Last Name, First Name, Date of birth and their place of birth. An academic year has
Two (2) sessions each consisting of six (06) teaching units.
1.Define a data structure to store students' grades.
2. Write an algorithm to record the grades of L1 and L2 students.
3. Starting from 2) display the names of the students who have validated all the UEs;
4. Starting from 2) display the names of students who have validated only one UE;
5. From 2) display the names of students who have not validated any UE;
6. Starting from 2) display the names of students who have an overall average >= 10.

Exercise 6: The Time

Time is a structure composed of hours, minutes, and seconds (h: m: s).
1.Define a record structure that represents time.
2. Write a function that takes a time t as input1and display 1 if it is a valid time and 0
otherwise.
3. Write a procedure that takes a time as input and displays the time that will be in 8 seconds.
4. Write a function that takes two times as parameters.
t1 t2 and returns the sum of these
two times.
5. Write a function that takes two times t as parameters1and t2and returns 1 if they are equal and
0 otherwise.

Exercise 7: Reverse an array

Write a PROCEDURE / FUNCTION that reverses an array (the first value becomes the
last, the second, the penultimate, etc.). For example, if the table is sorted in ascending order at
from the start to the end of execution of the PROCEDURE / FUNCTION it is sorted in descending order.

Exercise 9: Array manipulation

Let Tab be an array with n real numbers.
1. Write a function that takes the input parameters Tab and N and returns 1 if the
the array is sorted and 0 otherwise.
2. Write a procedure that takes as input parameters the variables Tab and N and in
output parameters the POS and NEG variables. The POS and NEG variables must
contain respectively the number of strictly positive reals and the number of
strictly negative reals of the table TAB.

6
 University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Program
TD INTRODUCTION TO ALGORITHMS (INF131)

III. SUBPROGRAMS
Exercise 1: Vowel Count
Define a function that counts the number of vowels in a table of N characters.

Exercise 2: Table
Let there be an array of size MAX containing N integers. (N MAX
1. Define a function SUM that calculates the sum of the elements in the array.
2.Define a procedure DELETE that removes the element located at position k (1 k N)du
tableau.
3.Define a procedure DELETEVAL that searches for and deletes the first VAL element found.
in the table.
4. Define an INSERTVAL procedure that inserts the element VAL at position k(1 k N)du
table

Exercise 3: Search in an array

1. Define a function that returns the index of the first real number greater than x in the array tab, passed
In parameters. If Six is not present, it returns -1.
Define a function that returns true if the array contains more even integers than odd integers.
impairs.
3.Define a function that returns the 2nd smallest integer from an array.

Exercise 4: Horns
Let P(x) be a polynomial of degree 3. P(x) can be expressed in the following form:
P(x) a0 a1 x a 2x 2 a3 x 3 a0 x(a1 a 2x a3 x 2) a0 x(a1 x(a2 xa3 )).We can use this
form to calculate the image of a real x0parP. This is the Hörner method.
1. Write the algorithm that reads the coefficients and calculates P(X0) where X0is read on the keyboard.
2 2X30.5X4and X0= 7.
2.Test this algorithm with P(X) = 2 - 4X + 3X+
3. Write this polynomial in the form presented in the introduction and then determine the number
operations performed (additions and multiplications) to calculate P(7).
2+ 2×73-
4. Count the number of operations performed for the following calculation: P(7) = 2 - 4×7 + 3×7
3.54

Exercise 5: Syracuse Sequence

u
siu nis pair
The Syracuse sequence is defined by0IN+and for everything n IN,u 1 2
3un  1 siu n is odd
1. Calculate the first terms of the sequence foru0=1 ; u0=3 and u0We don't know at the moment
currently if there exists an integer0for which this sequence never reaches 1.
2. Write a program asking for0enter the user and display all the values1,u2n.
3. Write a program asking0to the user and displaying all the values1,u2...Nwhere N
is the smallest integer+ such queue = 1. k
4. Modify your program so that it also displays N and the largest element of the sequence.
0uN)

7
 University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer/Mathematics Pathway
TD INTRODUCTION TO ALGORITHMS (INF131)

Exercise 6: Number of digits

1. Write a function NbreChiffres that returns the number of digits of an integer passed in
parameter. NB: Take into account negative integers.
2. Write a procedure min&max that inputs nbr values (nbr is a non-zero parameter of the sub-
program) and which returns (through the parameters) the minimum, the maximum, and the average
entered values.
3. Write an algorithm that asks the user to enter a positive integer (aVal), then:
a. Indicate to the user if it is a number with 3 digits,
b.Display the factorial of a value,
c. Calculate the square root of aValue,
You will need to, of course, call upon the sub-algorithms defined in 1) and 2)

Exercise 7: Input of Prime Numbers

1. Write a function PRIME that tests whether a number is prime or not.
2. Write a procedure that uses the function PRIME to create an array of the first N primes.
prime numbers. Indications:
 A number N is prime if it has no divisors. ]1,N]
 The SQRT(N) function returns the square root of the number N.

Exercise 8: Palindrome numbers

A number will be called a 'palindrome' if it can be read from left to right and from right to left.
representing the same number. The following numbers are palindromes: 425524, 121, 3, etc.
1. Write a function extract that takes an integer (nb) as a parameter and that:
return –1 and do not modify nb if nb < 10
return the 1heremove the highest significant digit from the number and modify the number accordingly.
example extract(4657) returns 4 and nb equals 657.
2. Write, using the previous function a "boolean" function palindrome that receives a
an integer as a parameter returns true or false depending on whether this integer is a palindrome or not
3. Write a main program that tests the first then the second function.

Exercise 9: Simulation of an algorithm

Algorithm riddle procedure guess (V1:integer, var V2:integer, var Rep:boolean)

varEssai, Prec:entier ; start
ok :boolean ; write("start guessing: ", V1, V2);
beginning if (V2mod2 = 0) then
Prec 9 ; V2 V2 / 2 ;
repeat otherwise
Write("Principal: a data please:"); V2 V2 + (V2 + 1)/2 ;
read(Essay); fsi
ok false Rep (V1 = V2);
guess(trial, Prec, ok) ; V1 0
write("Principal : ", test, Prec); write("end guess : ", V1, V2);
until end
end

1. What are the guesses when the entered data is 11, 11, 11, 11, ...?
2. Which lines can be removed without affecting the overall operation of
the algorithm should not be modified?

8
 University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Course
TD INTRODUCTION TO ALGORITHMS (INF131)

IV. RECURSIVITY

Exercise 1: String

1. Write a recursive function that reverses a string.

2. Write a recursive procedure that reverses a string.
3. Write a recursive function that takes a string as input in the form of a
algebraic sum of real numbers, e.g. "−1.37 +40 -10.08 +7-244" and which evaluates this sum
algebraic.

Exercise 2: Binary conversion

1. Write a recursive function that returns the binary notation of a natural integer. For example
25 → 11001.
2. Write a recursive function that returns the decimal notation of a binary number.
example: 11001 → 25.

Exercise 3: Morris Function

Here is the Morris function:

function morris (m, n: integer): integer
begin
if m = 0 then
result := 1
else
result := morris(m - 1, morris(m, n));
end;
Explain why the call to Morris(1,0) does not terminate!

Exercise 4: Sum of two integers

Propose a recursive algorithm to calculate the sum of two natural integers while assuming that the
the only basic operations at your disposal are:

the addition of 1 to an integer: a + 1;

the withdrawal of 1 to an integer: a−1et
the comparisons to 0 of an integer a: a = 0, a > 0 and a < 0.
How to extend this function to integers of any sign?

Exercise 5: Product of two integers

Propose a recursive algorithm to calculate the product of two natural integers.

assuming that the only basic operations you have are:
the sum of two integers a and b: a + b;
- the withdrawal of 1 from an integer: a–1 and
the comparison to 0 of an integer: a = 0.

9
University of Ngaoundéré Academic year 2022/2023
Faculty of Science License 1
Department of Mathematics and Computer Science Computer Science/Mathematics Path
TD INTRODUCTION TO ALGORITHMIC (INF131)

Exercise 6: Integer power of a real number

Propose a recursive algorithm for calculating the nth power.∈ IN) of a real number assuming that
the only basic operations you have are:

the product of two reals a and b: a × b;

the withdrawal of 1 to an integer: a–1 and ;
-the comparison to 0 of an integer: a = 0.

Exercise 7: McCarthy's 91 Function

n 10 sine 100
f(n)
f(f(n 11)) otherwise

What is f(96);
2. Give a non-recursive form of this function.

Exercise 8: Palindromes
A palindrome is a word whose letters read from left to right are the same as those
reads from right to left. The words radar, elle, été, ici are palindromes.

Propose two functions, one recursive and the other iterative, that take a word and the number of as input.
character of the string and returns 1 if the word is a palindrome.

Exercise 9: The arrays

1. Provide a recursive version of calculating the sum of the elements of an array.
2. Provide a recursive algorithm for reversing the order of elements in an array.

Exercise 10: Recursive search

Describe an algorithm to find the minimum and maximum of any set of n
name without making more3nof comparisons. Justify your answer.
2

Exercise 11: Count the Vowels

We propose to count the number of vowels in a word recursively.

1. Write functionIsVowel(char letter):boolean to determine if a character is or is not a vowel

vowel.
2. Write a recursive method numberOfVowels() that takes a string as an argument.
the case where the string passed as a parameter is reduced to the empty string, we stop the recursion. In the case
where the string has at least one letter, we check if its first letter is a vowel or not and, in
In each case, we make an appropriate recursive call to numberVowel. We will assume that an empty string
is symbolized by '\0'.

10
 University of Ngaoundéré Academic year 2022/2023
Faculty of Sciences License 1
Department of Mathematics and Computer Science Computer/Mathematics Track
TD INTRODUCTION TO ALGORITHMS (INF131)

Exercise 12: Towers of HANOI

The problem of the Tower of Hanoi consists of moving N disks of different diameters from a starting tower to
a destination tower passing through an intermediate tower and this in a minimum of moves, while respecting the
following rules:

you cannot move more than one disk at a time,

one can only place a disk on a larger disk or on an empty space.

Hanoi algorithm (n: integer, A: character, B: character, C: character)

begin
if n = 1 then
write("move ", A, " to ", C)
otherwise
Hanoi(n-1, A, C, B) ;
write("move ", A, " to ", C)
Hanoi(n-1, B, A, C);
end if
end

1. Execute Hanoi(2, 'a', 'b', 'c'), Hanoi(3, 'a', 'b', 'c') and Hanoi(4, 'a', 'b', 'c').
2. Prove by induction that the number of moves is 2n –1.

Exercise 13: Analysis of sorting algorithms

Provide the recursive versions of the following sorting algorithms:

1. Insertion sort.
2. Bubble sort.
3. Selection sort.

Exercise 14: Insertion into an array.

Let Tab be an array that contains n real values. Assuming that the array is sorted in order.
croissant. We would like to insert a real number x into the vector in such a way that the array Tab remains sorted.

Example:

Let the table Tab 4 5 5 7 9 11 20 sorted names in

which we want to insert the number x=10. The result is an array Tab of 8
names always sorted: 4 5 5 7 9 10 11 20
Write a recursive procedure that takes as parameters the array Tab, the integer n (the number of elements
the array Tab) and a real number x, and it performs the insertion of x into the array Tab.

11