Translated from French to English - www.onlinedoctranslator.

com

Brahim BESSAA

Exercises with Solutions

1st Year MI

September 2017
 Preface

After several years of teaching the “Algorithmics” module of the first year of the degree
(MI) and given the difficulties encountered by students in this module, I tried to provide them
with training support to help them master this module.

This book brings together exercises from the series of tutorials and exams (with corrections)
of the Algorithmic module of the first year MI (USTHB). In this book I give detailed solutions to the
proposed exercises, but it should in no case replace the TD sessions, where students can discuss
the solutions and see other proposed solutions. In fact, the TD instructor can always give more
details and explanations.

A positive use of this work therefore consists of encouraging students to prepare their series of
exercises, compare their solutions with those proposed and plan questions to ask during tutorial
sessions.

Finally, the book is a first version of a personal effort. I await from dear students and
colleagues their remarks and suggestions in order to improve it in the next versions.

September 2017.

Dr. Brahim BESSAA

bbessaa@yahoo.fr
 Summary

Control Structures (Conditional – Iterative). . . . . . . . . . . . .5

Parameterized Actions (Procedures and Functions). . . . . . . . . . . . . . . . .15

Tables (Vectors – Matrices) and Strings. . . . . . . . . . .23

The Recordings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

The Files. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Control Structures (Conditional – Iterative)

EXERCISE 1
Write an algorithm that asks the user for a number, then calculates and displays the square of that number.

AlgorithmSquare ;
VarX,X2 :real ;
Beginning
To write('Give a reel');
Read(X);
X2←X*X ;
To write('The square of ',X,' is: ',X2) ;
END.

EXERCISE 2

A copy shop charges 2 DA for the first ten photocopies, 1.50 DA for the next twenty, and 1 DA for more.
Write an algorithm that asks the user how many photocopies were made and then displays the
corresponding amount.

AlgorithmBill ;
ConstP1=2 ; P2=1.5 ; P3=1 ;
Var Mount:real;
Nbc:integer;
Beginning

To write('Give the number of photocopies');

Read(Nbc);
IfNbc≤10
SOMount←P1*Nbc
Otherwise IfNbc≤30
SOMount←P1*10+P2*(Nbc-10) Otherwise
Mount←P1*10+P2*20+P3*(Nbc-30) Fsi

Fsi;
To write('The amount to be paid is: ',Mont) ;
END.

EXERCISE 3

Write an algorithm to display the season by entering the month number.

AlgorithmSeason;
VarM: integer;
Beginning

To write('Give a month number 1--12');

Repeat Read(M);UntilM>0 and M<13;

Corrected Algorithmic Exercises – 1st Year MI5

Control Structures (Conditional – Iterative)

CaseMWorth
3,4,5:To write('The season is: SPRING');
6,7,8:To write('The season is: SUMMER');
9,10,11:To write('The season is: AUTUMN');
12,1,2:To write('The season is: WINTER');
FinCas;
END.

EXERCISE 4
Write an algorithm to solve each of the following problems:

1- Calculation of the sum of the first N integers.

2- Search for the minimum and maximum in a set of N numbers.
3- Calculation of the quotient and remainder of the division of two integers A and B without using the division
operation. 4- Calculation of the product of two integers using only the addition operation '+'.
5- Determination if A is divisible by B. With A and B positive integers. 6-
Determine all the divisors of a given integer X.
7- Determine whether an integer X is prime or not.
8- Calculate the sum of the digits that make up a natural integer N.

1-
AlgorithmSum ;
VarI,N,S: integer;
Beginning
To write('Give an integer N') ;Read(N) ;
S ←0 ;
ForI ←1hasN-1
Do
S ←S+I;
Do;
To write('The sum of the',N,' first numbers is: ',S) ;
END.
2-
AlgorithmMaxMin;
VarI,N,Max,Min,X:integer;
Beginning
To write('Give an integer N>0');
Repeat Read(N) ;UntilN>0 ;
/* Read the first element, then initialize the Min and Max to that value
Read(X) ; Max←X ; Min←X ; ForI ←2hasN

Do
/* read the rest of the items and update the Min and Max
Read(X);

Corrected Algorithmic Exercises – 1st Year MI6

Control Structures (Conditional – Iterative)

IfMax<X SOMax←X
Otherwise IfMin>XSOMin←XFsi
Fsi;
Do;
To write('The Minimum of the values is: ',Min,' the Maximum is: ',Max) ;
END.
3-
AlgorithmQuotReste;
VarA,B,Q,R: integer;
Beginning
To write('Give two integers A and B');
Read(A,B);
Q ←0 ; R ←A ;
As long asR>B
Do
Q ←Q+1;
R ←RB;
Do;
To write('The Quotient of A/B is: ',Q, ' The remainder of A/Best: ',R) ;
END.
4-
AlgorithmProduct ;
VarA,B,P,I: integer;
Beginning
To write('Give two integers A and B');
Read(A,B);
IfA=0 or B=0
SOP←0
OtherwiseP←0 ;/*initialize the product to 0
ForI ←1hasB
Do
P←P+A ;
Do
Fsi;
To write('The product A*B is: ',P);
END.

We can optimize the solution by choosing the loop with the fewest iterations:

AlgorithmProduct ;
VarA,B,P,I: integer;
Beginning
To write('Give two integers A and B');

Corrected Algorithmic Exercises – 1st Year MI7

Control Structures (Conditional – Iterative)

Read(A,B);
IfA=0 or B=0
SOP←0
Otherwise IfA>B
SO P←A ;/*We can initialize the product to A and start the loop at 2
ForI ←2hasB
Do
P←P+A ;
Do
OtherwiseP←B ;
ForI ←2hasHAS
Do
P←P+B ;
Do
Fsi;
To write('The product A*B is: ',P);
END.
5-
AlgorithmAdivB;
VarA,B,R: integer;
Beginning
To write('Give two positive integers A,B');
Repeat Read(A,B);UntilA>0 and B>0 ; R
←A ;
As long asR≥0DoR ←RB;Do;
IfR=0So Write(A,' is divisible by ',B)
Otherwise Write(A,' is not divisible by ',B)
Fsi;
END.
6-
AlgorithmDividers;
VarX,M,I: integer;
Beginning
To write('Give an integer X');
Read(X);
To write('The divisors of ',X,' are :') ;
/*We loop from 1 to half of X, because after half there is no more divisor except X /*We can use
the integer division function DIV and the remainder function of this division MOD M←XDIV2 ;

ForI ←1hasM
Do
IfXMODI=0So Write(I)Fsi;
Do;

Corrected Algorithmic Exercises – 1st Year MI8

Control Structures (Conditional – Iterative)

To write(X);
END.
7-
AlgorithmFirst;
Var X,M,I: integer;
Pr:boolean;
Beginning

To write('Give an integer X');

Read(X);
/*X is prime if it has two distinct divisors 1 and itself, note 1 is not prime. Pr
←True;
IfX=1
SOPr←False
OtherwiseM←XDIV2 ;
I ←2 ;
As long asI ≤ M and
Pr Do /*if we find a divisor we stop the loop IfX
MODI=0SOPr←FalseFsi; I ←I+1 ;

Do
Fsi;
IfPrSo Write(X,' is prime')Otherwise Write(X,' is not prime')Fsi;
END.
8-
AlgorithmSumChiff;
VarN,S,R: integer;
Beginning
To write('Give a natural integer N');
Repeat Read(N) ;UntilN≥0 ; S←0 ; R
←0 ;
As long asR>0
Do S←S+RMOD10;
R← RDIV10;
Do;
To write('The sum of the digits that make up ',N,' is :',S) ;
END.

EXERCISE 5
Write an algorithm that allows the user to enter a character sequence ending in '*', and which displays at the
end the number of times the letter ' appearsHAS'.

Solution 1:using a loopRepeat

AlgorithmAppearance;

Corrected Algorithmic Exercises – 1st Year MI9

Control Structures (Conditional – Iterative)

Var ch: character;

NbA: integer;
Beginning

NbA ←0 ;
Repeat
Read(ch);
Ifch='A'SONbA ←NbA+1Fsi; Until
ch='*' ;
To write('Number of appearances of A is:',NbA);
END.

Solution 2:using a loopAs long as +Initialization

AlgorithmAppearance;
Var ch: character;
NbA: integer;
Beginning

NbA ←0 ;
Ch ←'X' ;/*Initialize Ch to a character other than '*'
Tank ch<>'*'
Do
Read(ch);/*reading is done before
processing Ifch='A'SONbA ←NbA+1Fsi;
Do;
To write('Number of appearances of A is:',NbA);
END.

Solution 3:using a loopWhile + Read before loop

AlgorithmAppearance;
Var ch: character;
NbA: integer;
Beginning

NbA ←0 ;
Read(ch);/*read the first value of ch before the loop
Tank ch<>'*'
Do
Ifch='A'SONbA ←NbA+1Fsi;
Read(ch);/*The following reading is done after processing
Do;
To write('Number of appearances of A is:',NbA);
END.

Corrected Algorithmic Exercises – 1st Year MI10

Control Structures (Conditional – Iterative)

EXERCISE 6
Write an algorithm to calculate the value of the expression E,
such that E=(1+2)x(1+2+3)x(1+2+3+4)x…x(1+2+3+…+(N-2)+(N-1)+N), and (N≥2).

AlgorithmSumE;
VarI,J,N,E,S: integer;
Beginning
Read(N) ;
E ←1 ;
S ←1;
ForI ←2hasN
Do
S ←S+I;
E ←E*S ;
Do;
To write('E=',E) ;
END.

EXERCISE 7
Write an algorithm to calculate the value of the expression E,
ퟏ ퟏ
푬 = ퟏ +ퟏ+ + ⋯+ , with (N≥2).
ퟏퟐ ퟏퟐퟑ ퟏퟐퟑ⋯푵

AlgorithmSumE;
VarI,J,N,S: integer;
E:reel;
Beginning

RepeatRead(N);UntilN>=2 ; E
←1 ;S ←1;
ForI ←2hasNDo
S ←S+I;
E ←E+1/S ;
Do;
To write('E=',E) ;
END.

EXERCISE 8
Write an algorithm to calculate the value of the Nth term (N<100) of the sequence UNdefined by:
푈 = 2, 푈 = 3, 푈 = 푈 − 푈

AlgorithmFollowing ;
Var I,N: integer;
X,Y,A :real ;

Corrected Algorithmic Exercises – 1st Year MI11

Control Structures (Conditional – Iterative)

Beginning

To write('Give 0<N<100') ;
Repeat Read(N)Until(N>0)And(N<100); X
← 2;
Y←3 ;
/* Attention the 1st term (N=1) corresponds to U0, the recurrence starts from 3 For
I←3hasN
Do
A ← (2/3)*Y-(1/3)*X ;/*we must linearize the expression
X←Y;
Y ← One ;/*pay attention to the order between the last two assignments
Do;
CaseNWorth
1: A ← X ;
2: A ← Y ;
FinCas;
To write('The ',N,' th term is: ',One) ;
END.

EXERCISE 9
Write an algorithm that determines and displays the Nthvalue of the sequence (UN) knowing that

U0= 0 U1= 1 ; U2= 2 ;UN= UN-1+ UN-3for N > 2.

Algorithmfollowing;
VarX,Y,Z,A,I,N:integer;
Beginning
To write('Give an integer');
Repeat Read(N) ;UntilN≥0 ; X
←0 ;
Y←1 ;
Z←2 ;
ForI←3hasNDo
A←Z+X ;
X←Y ; Y←Z ; Z←A ; Do;

CaseNWorth
0: A←X;
1: A←Y;
2: A←Z;
Farms;
To write('The term One is:',One);
END.

Corrected Algorithmic Exercises – 1st Year MI12

Control Structures (Conditional – Iterative)

EXERCISE 10
Write an algorithm to convert an integer N written in binary form to its decimal value.

Example:N = 10111010 after conversion we obtain decimal value = 186

Algorithmconversion ;
VarVB,B,D,P2:integer;
Beginning
To write('Give an integer in binary');
Repeat Read(VB)UntilVB>=0 ;
B ← VB ;/*VB backup for display
P2 ← 1 ;/*P2 contains the power of 2, initially 20=1 D ←
0;
Repeat
D ← D + (BMOD10)*P2 ;/*retrieve the coefficient = the rightmost digit of the number P
← 2 * P2 ;/*calculation of the next power of 2 B ← BDIV10 ;/*to move to the next
coefficient UntilB=0 ;

To write('The decimal value of ',VB,' is: ',D) ;

END.

EXERCISE 11
Write an algorithm that calculates the N-order sum of푺풏defined as follows using only the
basic operators (without the use of the power operator ).
푵
(−ퟏ)풊 ퟏ
푺풏 =
풙풊
풊ퟎ

AlgorithmSumSuite;
Var I,N,K:integer;
Px,X,Sn :real ;
Beginning

To write('Give an integer');
Repeat Read(N)UntilN>=0 ; To
write('Give a real'); Read(X);

K←-1 ; /* K represents (-1)i

Sn←-1 ; /*initial value of Sn for i=0 /
Px←1 ; *power of X for i=0
ForI←1hasN
Do
K← - K;
Px←Px*X ;

Corrected Algorithmic Exercises – 1st Year MI13

Control Structures (Conditional – Iterative)

Sn←Sn+K/Px ;
Do;
To write('The sum Sn= ', Sn) ;
END.

Corrected Algorithmic Exercises – 1st Year MI14

Parameterized Actions (Procedures and Functions)

EXERCISE 1
Write the parameterized actions (procedure or function) to solve the following problems: 1-
Calculation of the sum of two whole numbers.
2- Calculation of the factorial of N (N!).
3- Check if an integer A divides an integer B.
4- Calculation of the quotient and remainder of the integer division of two integers A and
B. 5- Check if a given character is a vowel (vowels: 'a', 'e', 'i', 'o', 'u', 'y').
6- Allows you to swap (exchange) the contents of two real variables. 7-
Given an integer A, calculates its absolute value.

1-FunctionSum(x,y:integer):integer;
Beginning

Sum ← x+y ;
END;
2- FunctionFact(x:integer):integer;
Var I,F: integer;
Beginning

F←1 ;/*we can use the function name directly instead of F ForI
←1 to x
DoF ← F*I ;Do; Fact
←F;
END;
3- FunctionDivide(A,B:integer):boolean;
Beginning
Divide ← False ;
IfB mod A = 0SODivide ← TrueFsi;
END;
4- ProcedureQuotRest(E/ A,B:integer; S/ Q,R:integer);
Beginning
Q←0;R←A;
As long asR>= B
Do
R ← R mod B ;
Q ← Q+1 ;
Do;
END;
5- FunctionVowel(C:character):boolean;
Beginning
Vowel ← False ;
CaseCWorth
'a', 'e', 'i', 'o', 'u', 'y': Vowel ← True ;
Farms;
END;
6- ProcedurePermute(I/O/ A,B:integer);
VarC:entire:
Beginning

Corrected Algorithmic Exercises – 1st Year MI15

Parameterized Actions (Procedures and Functions)

C←A;A←B;B←C;
END;
7- FunctionVabs(A:integer):integer;
Beginning
Vabs ← A ;
IfA<0SOVabs ← AFsi;
END;

EXERCISE 2

1- Write an APSquare vverifying whether a natural integer is a perfect square, using only the
basic operators, and returns its root in the favorable case. (Hint: X is a perfect square if there exists an
integer i such that X = i * i.)
2- Write an algorithm which, among N natural integers, calculates the sum and the product of the square roots of the
perfect square integers. Then it checks whether the sum and the product are perfect squares.

1- ProcedureSquare(E/ A:integer; S/ CP::booleen; S/ RC:integer);

Var I:integer;
Beginning

CP← False ; I ← 0 ; As long as(I<= A

div 2)and(Non CP)
Do IfA=I*ISOCP← True ; RC ← IFsi; Do;

END;
2- AlgorithmCalculation ;
VarI,N,S,P,X,Rac:integer; CParfiat:boolen;
ProcedureSquare(E/ A:integer; S/ CP::booleen; S/ RC:integer);
/* we resume the declaration of the procedure
-----
Beginning

Write('Give the number of 'elements N');

RepeatRead(N)UntilN>0 ;
S← 0 ; P ← 1 ;
ForI ← 1 to N
DoRead(X);
Square(X,Cperfect,Rac);
IfPerfect Alotrs
S← S+Rac ;
P← P*Rac
Fsi;
Do;
Square(S,Cperfect,Rac);
IfPerfectSOWrite('The sum S=',S,' is a perfect square')Fsi;
Square(P,Cperfect,Rac);
IfPerfectSOWrite('The product=',P,' is a perfect square')Fsi;
END.

Corrected Algorithmic Exercises – 1st Year MI16

Parameterized Actions (Procedures and Functions)

EXERCISE 3
1- Write a function that returns True if the character passed as a parameter is equal to -o- or -O- (whoever wants
say Yes), and False otherwise.
2- Write a parameterized action that allows you to display the multiplication table from 1 to 9 of a number
positive integer. Then, using the previous parameterized actions, write an algorithm to
display the multiplication table of an integer to the user for as long as he wants (until the
answer is wrong).

1- FunctionResponse(C:character):boolean;
Beginning
Answer ← False;
IfC='o' or C='O 'SOAnswer ← TrueFsi;
END;
2- ProcedureDisplayTable(A:integer);
VarI: integer;
Beginning

ForI ← to 9
DoWrite(A,'x',I,'=',A*I) ;Do;
END;
3- AlgorithmTableM ;
VarA: integer; Rep: character;
FunctionResponse(C:character):boolean;
.......
ProcedureDisplayTable(A:integer);
.......

Beginning

Repeat
Write('Give an integer');
Read(A);
DisplayTable(A);
Write('Do you want to continue Y/N');
Read(Rep);
UntilNo Response(rep);
END.

EXERCISE 4

Write an algorithm that displays all numbers less than 500 equal to the sum of the cubes of their
digits. We will use a UNIT function, and a CUBE function.
Example: 153 = 13+ 53+ 33= 1 + 125 + 27

AlgorithmSumCube ;
VarA,B,S: integer;
FunctionUnite(X:integer):integer;
Beginning
Unite ← X mod 10 ;

Corrected Algorithmic Exercises – 1st Year MI17

Parameterized Actions (Procedures and Functions)

END;
FunctionCube(X:integer):integer;
Beginning
Cube ← X*X*X ;
END;
Beginning

ForA← 0 to 500
Do
S← 0; B ← A;
RepeatS← S + Cube(Unit(B)); B ← B div 10UntilB=0;
IfS=ASOWrite(A,' is equal to the sum of the cubes of its digits')Fsi;
Do;
END.

EXERCISE 5

Write an algorithm that displays all perfect numbers less than 10000. Knowing that a positive integer
(N) is perfect if it is equal to the sum of its divisors (<N). We will write a Boolean function, called
PERFECT, to check if the number is perfect or not perfect.
Examples: 6 — which is equal to 1 + 2 + 3 —
and 28 — which is equal to 1 + 2 + 4 + 7 + 14 — are perfect numbers.

AlgorithmPerfectNumber;
VarA: integer;
FunctionPerfect(X:integer):boolean; Var
I,S: integer; Beginning

S←0;
ForI ← 1 to X div 2
Do IfX mod I = 0SOS ← S+IFsi; Do;

IfS=XSOPerfect ← TrueOtherwisePerfect ← FalseFsi;

END;
Beginning

ForA← 1 to 10000
Do IfPerfect(A)SOWrite(A,' is perfect')Fsi; Do;

END.

EXERCISE 6

Write a function ( MINUS or LWCASE ) that converts an uppercase character to its

lowercase counterpart.

For this exercise, we do not have a predefined function in algorithms processing the characters (next, previous,
character code, character of the code, etc.), so either we use aCase Worthwith the 26 possible cases, or we use a
loop as follows.

Corrected Algorithmic Exercises – 1st Year MI18

Parameterized Actions (Procedures and Functions)

FunctionMinus(C:character):character; Var
I,J: integer; X: character; Beginning

/*find the position of C in the alphabet I ←

0;
ForX ← 'A' to CDoI ← I+1 ;Do; J ← 1 ;

ForX ← 'a' to 'z'Do IfI=JSOMinus ← XFsi;J ← J+1 ;Do;

END;

EXERCISE 7

1- Write an APFirstwhich determines whether a positive integer is prime.

2- Write an APSPremierwhich determines whether a positive integer is semi-prime.(a semi-prime number is
a product of two prime numbers that are not necessarily distinct.).
3- Using the AP defined previously, write an algorithm that determines the semi-prime numbers
among the integers of the form (which are written as follows) abcabc where a,b,c are digits between 0
and 9 with a > 0.
Ex: 136136, 524524, 908908, ...

In this exercise, according to the second question, it is better to write a procedure that returns the number of
divisors of the input integer and a boolean to check if it is prime or not.

1- FunctionFirst(E/X: integer):boolean;
VarI,M:integer;
Beginning

IfX=1SOFirst ← False
Otherwise M ← X DIV 2 ; I ← 2 ; First ← True ; As
long asI≤M and Prime Do

IfX mod I=0SOFirst ← FalseFsi; I←I+1 ;

Do;
Fsi;
END;
2- FunctionSemiFirst(E/X: int):booleen; Var
I,M:integer;
Beginning

IfFirst(X)
SO SemiFirst ← False
Otherwise M ← X DIV 2 ; I ← 2 ;
SemiFirst ← True ; As long
asI≤M and SemiFirst Do

IfX MOD I=0

SO If(Not Prime(I)) or (Not Prime(X DIV I)) SO
SemiFirst ← False Fsi

Corrected Algorithmic Exercises – 1st Year MI19

Parameterized Actions (Procedures and Functions)

Fsi;
I←I+1 ;
Do;
Fsi;
END;

3- For this question, it is about finding a formula to generate numbers of the formabcabcin order to
optimize the algorithm (minimize the number of iterations).

We have:

푎푏푐푎푏푐 = 푎푥10 + 푏푥10 + 푐푥10 + 푎푥10 + 푏푥10 + 푐푥10 =

(10 + 1)(푎푥10 + 푏푥10 + 푐푥10 )=1001(푎푥10 + 푏푥10 + 푐푥10 )

So to generate these numbers you just have to generate a part (abc), then multiply it by 1001.

AlgorithmNumber ;
Vara,b,c,X,NBDiv:integer; Pr:booleen;
FunctionFirst(X : integer): boolean;
---------
FunctionSemiFirst(X : integer): boolean;
---------
Beginning

/* trios nested loopsForgenerate a number of the form abcabc Fora

← 1 to 9
Do Forb ← 0 to 9
Do Forc ← 0 to 9
Do
X ← 1001*(100*a+10*b+c) ;
IfSemiFirst(X)SOWrite(X,' is semi prime')Fsi; Do;

Do;
Do;
END.

EXERCISE 8

Write a functionBINto convert a positive integer from decimal to binary.

FunctionBIN(X:integer):integer; Var
R,P: integer; Beginning

P ← 1 ; BIN ← 0 ;
Repeat
R ← X mod 2 ;
BIN ← BIN + R*P; P
← P*10 ;
X ← X div 2 ;
UntilX=0 ;

Corrected Algorithmic Exercises – 1st Year MI20

Parameterized Actions (Procedures and Functions)

END.

EXERCISE 9

Write a functionROOT2which calculates the square root of a positive number using the following
formula: X = (X + )

Or√a = X with precisionER = X − X (ex. ER=10-3)

FunctionRoot2(A:real):real;
Const ER=0.001;
VarX,Y,D :real ;
Beginning
X←A;
Repeat
Y ← 0.5*(X+A/X); D
← YX ;
IfD<0SOD ← -DFsi; X ←
Y;
UntilD<ER ;
Root2 ← Y ;
END;

EXERCISE 10

Unroll the following algorithm, giving the different values of the expected results in the order in which
the algorithm is executed.
AlgorithmCall ;
VarR, V: integer;
FunctionCALCULATION ( X : INTEGER ) : integer ;
VarR: integer; Beginning

R←X+V;
V← R – 2 ;
CALCULATION ← R + 2 *
V ; Write ( R , V ) ;
END;
Beginning

V←5;
R ← CALCULATION(V) ; Write ( R , V ) ; R
← CALCULATION( V ) ; Write ( R , V ) ; R ←
10 ;
V ← CALCULATION ( R ) ; Write ( R , V ) ;
END.

Corrected Algorithmic Exercises – 1st Year MI21

Parameterized Actions (Procedures and Functions)

Overall Function
Action Display
R V CALCULATION X R (local)
V ←5 5
CALCULATION(V) 5
R ← X+V 10
V ← R-2 8
CALCULATION ← R+2*V 26
WRITE(R,V) 10 8
R← CALCUL 26
WRITE(R,V) 26 8
CALCULATION(V) 8
R ← X+V 16
V ← R-2 14
CALCULATION ← R+2*V 44
WRITE(R,V) 16 14
R← CALCUL 44
WRITE(R,V) 44 14
R ← 10 10
CALCULATION(R) 10
R ← X+V 24
V ← R-2 22
CALCULATION ← R+2*V 68
WRITE(R,V) 24 22
V ← CALCUL 68
WRITE(R,V) 10 68

Corrected Algorithmic Exercises – 1st Year MI22

Tables (Vectors – Matrices) and Strings

EXERCISE 1

Let T be a vector (one-dimensional array) containing N integers (N≤100). Write the algorithms for:

1- Determine the minimum, maximum and average of the elements of an array T

2- Calculates the product of all elements of T as well as the number of strictly positive values. 3-
Calculates the sum and the scalar product of two vectors (T1 and T2).
4- Determines the positions of the appearance of a value in a vector T. 5-
Inverts the contents of a vector T.
6- Removes all zero values from a vector T.
7- Put negative values at the beginning and positive values at the end using a single array.

1- AlgorithmMinMax ;
Var T: Array[1..100] of integer;
I,N,Max,Min,S: integer; Avg: real;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100; /*Reading the elements
of T ForI←1 to NDoRead(T[I]) ;Do; /
*Initialization

Min←T[1] ; Max←T[1] ; S←0 ;

ForI←1 to NDo
IfMax<T[I]SOMax←T[I]Fsi; If
Min>T[I]SOMin←T[I]Fsi; S←S+
T[I] ;
Do;
Avg←S/N ;
Write('Maximum=',Max,' Minimum=',Min,' Average=',Avg);
END.

2- AlgorithmProd;
Var T: Array[1..100] of integer;
I,N,P,Nbp: integer;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100 ; /*Initialization

P←1 ; Nbp←0 ;
/*Reading elements of T and processing at the same
time ForI←1 to NDo
Read(T[I]) ;
IfT[I]>0SONbp←Nbp+1Fsi; P←P*
T[I] ;
Do;
Write('Product=',P,'Nb positive values=',Nbp);
END.

3- AlgorithmProd;
Var T1,T2,T3:Array[1..100] of integer;
I,N,PS:integer;

Corrected Algorithmic Exercises – 1st Year MI23

Tables (Vectors – Matrices) and Strings

Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100;
/*Reading elements of T1 then T2 do not read in the same loop
ForI←1 to NDoRead(T1[I]);Do; ForI←1 to NDoRead(T2[I]) ;Do; PS
←0 ;/*initialize Dot Product to 0 /*The sum of T1 and T2 in T3

ForI←1 to NDo
T3[I]←T1[I]+ T2[I];
PS←PS+ T1[I]* T2[I];
Do;
Write('Scalar Product=',PS); Write('Sum
of vectors'); ForI←1 to NDoWrite
(T3[I]);Do;
END.

4- AlgorithmPosition ;
Var T,Pos:Array[1..100] of integer;
I,J,N,Val:integer;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100; ForI←1 to NDo
Read(T[I]) ;Do; Write('Give Val');
Read(Val); /*Search for val and its
position J←0 ;

ForI←1 to NDo
IfT[I]=ValSOJ←J+1 ;Pos[J]←IFsi;
Do;
IfJ=0SOWrite(Val,'not found')
OtherwiseWrite(Val,'found at positions:');
ForI←1 to JDoWrite (Pos[I]);Do;
Fsi;
/* If we initialize J to 1, its incrementation is done after the assignment and the /
*dimension of Pos becomes J-1
END.

5- AlgorithmReverse ;
Var T: Array[1..100] of integer;
I,J,X,N:integer;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100; /*Reading the elements
of T ForI←1 to NDoRead(T[I]) ;Do; /
*Reverse

I←1 ; J←N ;
As long asI<J
Do
X←T[I] ; T[I]←T[J]; T[J]←X;

Corrected Algorithmic Exercises – 1st Year MI24

Tables (Vectors – Matrices) and Strings

I←I+1 ; J←J-1;
Do;
/*Display the new table T ForI←1 to
NDoWrite(T[I]) ;Do;
END.

6- AlgorithmDeleteZero;
Var T: Array[1..100] of integer;
I,J,N: integer;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100; /*Reading the elements
of T ForI←1 to NDoRead(T[I]) ;Do;

/*removing zeros is equivalent to shifting non-zero values I

←1 ;
As long asI≤N
Do
IfT[I]=0
SO /*shift loop
ForJ←I to N-1
DoT[J]←T[J+1];Do; N←N-1/*change
table size
Fsi;
I←I+1 ;
Do;
/*Display the new table T ForI←1 to
NDoWrite(T[I]) ;Do;
END.

Solution 2:

AlgorithmDeleteZero2;
Var T: Array[1..100] of integer;
I,J,NBN,N:integer;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100; /*Reading the elements
of T ForI←1 to NDoRead(T[I]) ;Do;

/*removing zeros is equivalent to moving non-zero values 1 after 1 (without loop) I

←1 ; J←1 ; NBN←0 ; As long asJ≤N

Do
IfT[J]=0
SO NBN←NBN+1/*number of null values /
Otherwise *move element
T[I]← T[J] ; I←I+1
Fsi;
J←J+1;

Corrected Algorithmic Exercises – 1st Year MI25

Tables (Vectors – Matrices) and Strings

Do;
N←N-NBN ;/*change the size of T
/*Display the new table T ForI←1 to
NDoWrite(T[I]) ;Do;
END.

7- AlgorithmNegPuisPos ;
Var T: Array[1..100] of integer;
I,J,N,X:integer;
Beginning

/*read exact size Write('Give the size of

the array N≤100'); RepeatRead(N)Until
N>0 and N≤100; /*Reading the elements
of T ForI←1 to NDoRead(T[I]) ;Do; /*pass
negative values to the beginning J←1 ;

As long asJ≤N and T[J]<0DoJ←J+1 ;Do;

/*move negative values to the beginning (find the first positive value I ) I
←J ;
As long asJ≤N
Do
IfT[J]<0
SO /*swap
X← T[I] ; T[I]←T[J]; T[J]←X; I
←I+1
Fsi;
J←J+1 ;
Do;
/*Display the new table T ForI←1 to
NDoWrite(T[I]) ;Do;
END.

EXERCISE 2

Write an algorithm that allows a vector T of N (N≤250) integers assumed to be positive to be split into two
vectors T1 and T2 containing respectively the even and odd numbers of T.

AlgorithmProd;
Var T1,T2,T : Array[1..250] of integer ;
I,J,K,N : integer ;
Beginning

/*read exact size Write('Give the size of

the array N≤250'); RepeatRead(N)Until
N>0 and N≤250; ForI←1 to NDo
Read(T[I]) ;Do;
J←1 ;K←1 ;/*counters for even and odd tables ForI←1
to NDo
IfT[I] MOD 2=0SOT2[J]← T[I] ; J←J+1
OtherwiseT1[K]← T[I] ; K←K+1
Fsi;
Do;

Corrected Algorithmic Exercises – 1st Year MI26

Tables (Vectors – Matrices) and Strings

Write('Even vector');ForI←1 to D-1DoWrite(T2[I]);Do; Write('Odd

Vector');ForI←1 to K-1DoWrite (T1[I]);Do; /*size of T1 and T2 are
respectively K-1 and J-1
END.

EXERCISE 3

Let T be a vector of N integers (N≤200). Write an algorithm that determines the number of successions of
two particular values (V1 and V2) in the vector.

AlgorithmRepetition ;
Var T: Array[1..200] of integer;
I,N,V1,V2,NBrep: integer;
Beginning

/*read exact size Write('Give the size of

the array N≤200'); RepeatRead(N)Until
N>0 and N≤200; ForI←1 to NDo
Read(T[I]) ;Do; Write('Give two values
V1 and V2'); Read(V1,V2)

I←1 ; NBrep←0 ;
As long asI<N
Do
IfT[I]=V1 and T[I+1]=V2
SO NBrep← NBrep+1 ; I←I+2 I
Otherwise ←I+1
Fsi;
Do;
Write('Number of successions of values',V1,V2,' is :',NBrep);
END.

EXERCISE 4
Let two sorted integer vectors V1 (N integers, N≤100) and V2 (M integers, M≤150).
Write a procedure that merges these two vectors into another sorted vector V3 without repeating
identical values.

AlgorithmFusion2;
Var A:Array[1..100] of integer; B:Array[1..150] of integer;
C:Array[1..250] of integer;
I,J,K,N,M: integer;
Beginning

RepeatRead(N);UntilN>0 and N≤100;

RepeatRead(M);UntilM>0 and M≤100;
ForI←1 to NDoRead(A[I]) ;Do; ForI
←1 to MDoRead(B[I]) ;Do; /
*Processing 1erelement
IfA[1]<B[1] SOC[1] ←A[1]; I←2; J←1 C[1]
Otherwise ←B[1]; J←2; I←1
Fsi;
K←2 ;

Corrected Algorithmic Exercises – 1st Year MI27

Tables (Vectors – Matrices) and Strings

As long asI≤N and J

≤M Do
IfA[I]<B[J] SO IfC[K]<> C[K-1]SOC[K] ←A[I]; K←K+1Fsi; I←I+1 IfC[K]<>
Otherwise C[K-1]SOC[K] ←B[J]; K←K+1Fsi;J←J+1;
Fsi;
Do;
If I>NSo ForI ←J to M
Do IfC[K]<> C[K-1]SOC[K] ←B[I]; K←K+1Fsi;Do;
Fsi;
If J>MSo ForJ ←I to N
Do IfC[K]<> C[K-1]SOC[K] ←A[J]; K←K+1Fsi;Do;
Fsi;
ForI←1 to K-1DoWrite(C[I]) ;Do;
END.

EXERCISE 5

Let T be an array of N numbers (N≤50). Write an algorithm that reverses, in T, the first increasing
sequence of numbers.

AlgorithmVector ;
Var T: Array[1..50] of integer;
I,J,X,N: integer;
Beginning

RepeatRead(N);Until(N>0) and (N<=50); //

Reading the vector
ForI ←1 to NDoRead(T[I]) ;Do; I ←1 ;

//Position of 1erelement of the sequence (I) As long

as(I<N) and(T[I]> T[I+1])DoI ←I+1Do;
//Position of the last element of the sequence if it exists (J) and
permutation IfI<NSOJ←I+1;
As long as(J<N) and(T[J]≤ T[J+1])Do←J+1Do; //
Permutation
As long asI<JDo
X ← T[I] ; T[I] ← T[J] ; T[J] ←X ; I
←I+1 ; J ←J-1 ;
Do;
Fsi;
//Display
ForI ←1 to NDoWrite(T[I]) ;Do;
END.

EXERCISE 6

Let A(N, M) be a matrix of characters (N≤20 and M≤30). Write an algorithm that
1- Search for an element in matrix A.
2- Calculates the number of vowels belonging to matrix A.

Corrected Algorithmic Exercises – 1st Year MI28

Tables (Vectors – Matrices) and Strings

3- Determines the transpose of matrix A.

4- Rotates the columns of matrix A.

AlgorithmMatrix;
VarI,J,N,M,Val,Nbv:integer; Exists:booleen;
A : Array[1..20,1..30] of integer;
AT : Array[1..20,1..30] of integer;
Start
RepeatRead(N);Until(N>0) and (N≤20);
RepeatRead(M);Until(M>0) and (M≤30); //
Reading the Matrix
ForI ←1 to NDo ForJ ←1 to MDo
Read(A[I,J]);
Do;
Do;
Write('Give Val'); Read(Val); /
*Search for Val
Exists←False; I←1 ; Tank I
≤N and Non Exist Do
J←1 ;
While J ≤M and Does Not Exist
Do
IfA[I,J]=ValSOExists←TrueFsi; J←J+1 ;

Do;
I←I+1 ;
Do;
IfExistsSOWrite(Val,'Exists')OtherwiseWrite(Val,'Not Found')Fsi; /*
number of vowels in A Nbv←0 ;

ForI ←1 to NDo ForJ ←1 to MDo

CaseA[I,J]Worth
'a','e','i','o','u','y': Nbv←Nbv+1;
Farms;
Do;
Do;
Write('Number of vowels is :',Nbv);
END.

EXERCISE 7

Let A(N, N) be a square matrix of integers (N≤25). Write two of the parameterized actions allowing to:
1- Calculate the trace of matrix A. (The trace is the sum of the elements of the main diagonal).
2- Determine the maximum and its position, of the values of the two diagonals (main and secondary).

AlgorithmTrace ;
VarI,J,N,Max,Lmax,Cmax,Tr:integer; A: Array[1..25,1..25] of integer;
Beginning

Corrected Algorithmic Exercises – 1st Year MI29

Tables (Vectors – Matrices) and Strings

RepeatRead(N);Until(N>0) and (N≤25); //

Reading the Matrix
ForI ←1 to NDo ForJ ←1 to NDoRead(A[I,J]);Do;Do; //and trace
calculation Tr←0 ;

ForI ←1 to NDoTr←Tr+ A[I,I]) ;Do; //Max

and its position Max←A[1,1] ;

ForI ←1 to N
Do IfMax< A[I,I])SOMax← A[I,I]; Cmax←I;Lmax←IFsi; /*Diag Main
/*Secondary diag – renter relation index I------- N+1-I
IfMax< A[I,N+1-I])SOMax← A[I,N+1-I]; Cmax←N+1-I;Lmax←IFsi;
Do;
Write('Max=',Max,'Row Position:',Lmax,'Column:',Cmax);
END.

EXERCISE 8

Given a matrix A(N, M) of integers (N≤20 and M≤30), write an algorithm which:
- Calculates and saves the sum of each column,
- Determines the Jmin position of the minimum sum and the Jmax position of the sum maximum.
- Swaps the two columns of indices Jmin and Jmax of matrix A if Jmin > Jmax.

AlgorithmMatrix;
VarI,J,N,M,Jmin,Jmax,X:integer;
A: Array[1..20,1..30] of integer; Sum: Table[1..30] of whole
Start
RepeatRead(N);Until(N>0) and (N≤20);
RepeatRead(M);Until(M>0) and (M≤30); //
Reading the Matrix
ForI ←1 to NDo ForJ ←1 to MDoRead(A[I,J]);Do;Do; //calculate and
save the sum of each col ForJ ←1 to M

Do Som[J]←0 ;
ForI ←1 to N
Do
Som[J]← Som[J]+ A[I,J];
Do;
Do;
ForJ ←1 to MDoWrite(Som[J])Do; Jmin
←Som[1]; Jmax← Som[1]; ForJ ←1 to M

Do IfSom[Jmax] < Som[J]SOJmax←JFsi; If

Som[Jmin] > Som[J]SOJmin←JFsi;
Do;
Write('Position Jmin=',Jmin,' Jmax=',Jmax) ; If
Jmin>Jmax
So ForI ←1 to N

Corrected Algorithmic Exercises – 1st Year MI30

Tables (Vectors – Matrices) and Strings

DoX← A[I,Jmin]; A[I,Jmin]← A[I,Jmax]; A[I,Jmax]←XDo; //

display
ForI ←1 to NDo ForJ ←1 to MDoWrite(A[I,J]);Do;Do;

Fsi;
END.

EXERCISE 9

1- Write an AP that checks if two vectors are identical;

2- Write an algorithm to remove all identical columns from a matrix. A[N,M].

We declare aKindVector in clauseType

TypeVect=Array[1..100] of integer;

1- Function Identical(V1,V2:vect; N,M:integer):boolean;

VarI: integer; Same: boolean;
Beginning
IfN<>M
SOSame←False
OtherwiseSame←True; I←1;
As long asI≤N and TdemDo IfV1[I]<> V2[I]SOSame←FalseFsi;
Do
Fsi;
Same←Same;
END;
2- AlgorithmSupIdem;
Kind Vect=Array[1..100] of integer;
Matrix=Array[1..100,1..150] of integer;
Var V1,V2:Vect; A:Matrix;
I,J,K,N,M:integer;
Function Identical(V1,V2:vect; N,M:integer):boolean;
- - - - - - - - - - resume function actions ------------
Beginning

RepeatRead(N);Until(N>0) and (N≤100);

RepeatRead(M);Until(M>0) and (M≤150); //
Reading the Matrix
ForI ←1 to NDo ForJ ←1 to MDoRead(A[I,J]);Do;Do;

/*Reading the vector

Write('Give a vector of size N'); ForI
←1 to NDoRead(V1[I]) ;Do;

/* locate columns identical to V1 and delete them J

←1 ;
As long asJ≤ M
Do
/*retrieve the column in V2
ForI ←1 to NDoV2[I]←A[I,J] ;Do;

Corrected Algorithmic Exercises – 1st Year MI31

Tables (Vectors – Matrices) and Strings

IfSame(V1,V2,N,N)/*both vectors have the same dim.

SO/*deletion of column J which amounts to shifting the right columns.
ForI ←1 to N
Do ForK←J to M-1
DoA[I,K] ← A[I,K+1] ; Do;

Do;
M←M-1/*decrease the number of columns without moving to the next column, because the
/* shifted column can also be the same as V1
OtherwiseJ←J+1
Fsi;
Do;

EXERCISE 10

1- Write a parameterized action that determines the presence or absence of a character in a

string. 2- Write a parameterized action that counts the number of vowels in a string.
3- Write a parameterized action that determines whether a given sentence contains all the vowels.

1- Function Presence(CH:string[200];C:character):boolean;
VarT,I: integer; Pr: boolean;
Beginning
T←Size(CH); Pr←False; I←1 ;
As long asI≤T and Not PrDo IfCH[I]=CSOPr←TrueFsi;I←I+1 ;Do;
Presence ←Pr ;
END;
2- Function NBVowel(CH:string[200]):integer;
VarT,I,Nbv:integer;
Beginning
T←Size(CH); Nbv←0; ForI
←1 to T
Make CaseCH[I]Worth
'a','e','i','o','u','y': Nbv←Nbv+1;
Farms;
Do;
NBVowel ←Nbv ;
END;
3- Function TouVoyelle(PH:string[200]):boolean;
VarT,I:integer; CV:string[6];
Beginning
T←Size(PH); CV←'aeiouy' ; ForI
←1 to T
Make CasePH[I]Worth
'a' :CV[1]←'X' ;
'e': CV[2]←'X'; 'i':
CV[3]←'X'; 'o':
CV[4]←'X'; 'u':
CV[5]←'X'; 'y':
CV[6]←'X'; Farms
;

Corrected Algorithmic Exercises – 1st Year MI32

Tables (Vectors – Matrices) and Strings

Do;
IfCV='XXXXXX'SOTouVoyelle ←TrueOtherwiseTouVoyelle ←FalseFsi;
END;

EXERCISE 11

1- Write a function that checks for the existence of a substring in a string.

2- Write a parameterized action that deletes (eliminates) the sequence of N characters from the string CH starting from
from position P.
3- Write a function that determines if a word is a palindrome. (A palindromic word is read from left to
right and from right to left (eg: RADAR, ELLE, HERE)).

1- Function SHexists(SH,CH:string[250]): boolean;

VarT,Ts,I:integer; EX: boolean ;
Beginning
T←Size(CH); Ts←Size(SH); EX←False; IfT≥Ts

SOI←1 ;
As long asI≤(T-Ts+1) and Not EX
Do J←I; K←1; EX←True; As
long asK≤Ts and EX Do
IfCH[J]<>SH[K]SOEX←FalseFsi; J←J+1 ;
K←K+1 ;
Do;
I←I+1 ;
Do;
Fsi;
SHexiste←EX ;
END;
2- Procedure DeleteNP(I/O/ CH:string[250], I/N,P:integer);
VarT,I:integer; CHI:string[250];
Beginning
T←Size(CH);
IfP≤T
SOCHI←'' ;/*initialize empty
ForI ←1 to P-1DoCHI[I]←CH[I] ;Do;/*copy the part before P /*Add
the characters after the N to be deleted
If(P+N)>TSON←TPFsi;/*if there are less than N characters left, we delete
all ForI←P+N at TDoCHI←CHI+CH[I] ;Do; CH←CHI ;

Fsi;
END;
3- Palindrome function (CH:string[250]):boolean;
VarI,J: integer; Pal: boolean;
Beginning
I←1 ; J←Size(CH); Pal←True; As
long asI<J and Pal Do

IfCH[I]<>CH[J]SOPal←FalseFsi; I
←I+1 ; J←J-1 ;
Do;
Palindrome←Pal;
END;

Corrected Algorithmic Exercises – 1st Year MI33

Tables (Vectors – Matrices) and Strings

EXERCISE 12

Write an algorithm that counts the number of characters, words, and sentences in a text. Words are
separated by spaces and sentences are separated by a period. (Not counting the separators: space and
period)

AlgorithmText ;
VarTX:chain;
T,NbC,NbM,NbP,I:integer;
Beginning

Write('Give text'); Read(TX); T

←Size(TX);
NbC←0 ; NbM←0 ; NbP←0 ; I←1 ; As
long asI≤N
Do IfTX[I]=' '
SOI←I+1
OtherwiseAs long as(I≤N)and(TX[I]≠' ')and(TX[I]≠'. ')
DoNbC←NbC+1 ; I←I+1 ;Do; NbM
←NbM+1 ;
IfTX[I]='. 'SONbP←NbP+1Fsi;
Fsi;
Do;
Write('Number of characters:',NbC,' Number of words:',NbM,' Number of sentences:',NbP); END.

EXERCISE 13

Write an algorithm that reads two words and determines if they are anagrams. Knowing that a word is said to be
an anagram of another word if they use (are formed by) the same letters.

Examples :
DOG anagram of CHINA, NICHE, AIMER
anagram of MAIRE, MARIE, RAMIE, FREEZE is
not anagram of ALGER, …

- First solution:we sort the two words then we compare

AlgorithmAnagram;
VarM1,M2:chain;
Procedure SORT(I/O/CH:string); Var
I,J,T:entire; X:character; Beginning

T←Size(CH);
ForI←1 to T-1
Do ForJ←I+1 to T
Do IfCH[I]>CH[J]
SO X←CH[I] ; CH[I]←CH[J]; CH[J]←X;

Corrected Algorithmic Exercises – 1st Year MI34

Tables (Vectors – Matrices) and Strings

Fsi;
Do;
Do;
END;
Beginning

Write('give 2 words');
Read(M1,M2);
SORT(M1); SORT(M2);
IfM1=M2SOWrite('The two words are anagrams')
OtherwiseWrite('The two words are not anagrams')
Fsi;
END.

- Second solution:the two words are then anagrams if each character appears the same number of times
in both words.

AlgorithmAnagram;
VarM1,M2:chain;
T1,T2,I,F1,F2:integer;
X:character;
Anag:boolean;
Beginning

Write('give 2 words');
Read(M1,M2);
T1←Size(M1); T2←Size(M2); Anag
←False;
IfT1=T2
SOAnag←True; I←1;
As long asI≤T1 and Anag
DoX←M1[I] ; F1←0 ;
ForJ←1 to T1Do IfM1[J]=XSOF1←F1+1Fsi;Do; F2←0 ;

ForJ←1 to T1Do IfM2[J]=XSOF2←F2+1Fsi;Do; IfF1≠F2SO

Anag←FalseFsi; I←I+1 ;

Do;
Fsi;
IfAnagSOWrite('The two words are anagrams')
OtherwiseWrite('The two words are not anagrams')
Fsi;
END.

- Third solution:each character of M1 found in M2 is replaced by a special character (eg: '*'). At the end we check
if all the characters of M2 have been replaced.

AlgorithmAnagram;
VarM1,M2:chain;

Corrected Algorithmic Exercises – 1st Year MI35

Tables (Vectors – Matrices) and Strings

T1,T2,I,J: integer;
Anag:boolean;
Beginning

Write('give 2 words');
Read(M1,M2);
T1←Size(M1); T2←Size(M2); Anag
←False;
IfT1=T2
SOAnag←True; I←1;
As long asI≤T1 and Anag
DoJ←1; Anag←False;
Tank J≤T1 and Non Anag
Do IfM1[I]=M2[J]SOM2[J]←'*' ; Anag←TrueFsi;J←J+1 ;Do; I←I+1 ;

Do;
I←1 ;
As long asI≤T1 and Anag
Do IfM2[I]≠'*'SOAnag←FalseFsi;I←I+1 ;Do;
Fsi;
IfAnagSOWrite('The two words are anagrams')
OtherwiseWrite('The two words are not anagrams')
Fsi;
END.

Corrected Algorithmic Exercises – 1st Year MI36

The Recordings

EXERCISE 1
1- Define a TIME type which contains the hour, minute, second fields.
2- Write a parameterized action which performs the sum T of two durations T1 and T2 of time type.
3- Write a TRANSFORM function which transforms a time T of type TIME into an integer S which
express this time in seconds.
Example: for T = 2 hours 10 minutes 37 seconds, S = 7837 seconds.
4- Write a DECOMPOS procedure which decomposes a time S expressed in seconds into a time T of
type TIME.
Example:for S = 7837 seconds, T = 2 hours 10 minutes 37 seconds.
5- Given two times T1 and T2 of type TIME, write an algorithm which calculates the time T sum
times T1 and T2 (T, T1 and T2 are of type TIME) using the TRANSFORM and DECOMPOS
actions.

1-KindTIME=Recording H,M,S: integer; End; 2-

ProcedureSumT(E/ T1,T2:TIME; S/ T:TIME); VarX:
integer;
Beginning

X←T1.S+T2.S;
TS←X mod 60; TM← X
←T.M+T1.M+T2.M;
TM← TH← X div 60+ T1.H+T2.H;
END;
3- FunctionTRANSFORM(T:TIME):integer;
Beginning
TRANSFORM←T.S+60*T.M+3600*TH ;
END;
In algorithms, we cannot have a record type function, so we use a procedure.

4- ProcedureDECOMPOS(I/O:integer; S/T:TIME);
Beginning
TH←S div 3600; S← S mod 3600;
TM←S div 60; TS← S mod 60;
END;
5-
AlgorithmCalculationT;
KindTIME=Recording H,M,S: integer; End; Var
T1,T2,T:TIME;
S: integer;
Beginning

Write('Give a Time T1: HM S');

Read(T1.H,T1.M,T1.S);
Write('Give a Time T2: HM S'); /*can be read
using the With instruction WithT2Do
Read(H,M,S);Do; /*transform T1 and T2 into
seconds, then add S← TRANSFORM(T1) +
TRANSFORM(T2); /*decompose S into TIME T

Corrected Algorithmic Exercises – 1st Year MI37

The Recordings

DECOMPOS(S,T) ;
/*We can also do DECOMPOS(TRANSFORM(T1) + TRANSFORM(T2),T);
Write('The sum is :',TH,' :',TM,' :',TS);
END.
EXERCISE 2
A complex number Z is completely defined by its real partshasand imaginaryb(Z = a + bi). 1- Give
the declaration of a complex number,
2- Write the functions:ReelZ,ImagZAndModulegiving the attributes of a complex number
respectively: the real part, the imaginary part and the modulus),
3- Write the parameterized actions:SumZ,DiffZAndProdZnecessary for arithmetic on the
complex, respectively for addition, subtraction and multiplication, 4- Write a
procedureConjZwhich calculates the conjugate of a complex number. 5- Write a
functionEqualZwhich tests the equality of two complex numbers. 6- Write a
procedureWriteZwhich allows you to display a complex number.
Let TC be an array of N complex numbers (N<=100). Using the previous parameterized actions, write
an algorithm that:
- Displays the element ofTChaving the largest modulus. Then checks the existence of its conjugate inTC.
- Calculate the sumZsand the productZpnon-zero elements of the arrayTC.
- Calculates and displays the difference betweenZsAndZpif it is pure imaginary.

1-KindTcomplex=Record a,b:real;END; 2-
FunctionReelZ(Z:Tcomplex):real;
BeginningReelZ←Za ;END;

FunctionImagZ(Z:Tcomplex):real;
BeginningImagZ←Zb ;END;

FunctionModuleZ(Z:Tcomplex):real; Beginning
ModuleZ←Root(Za*Z.a+Zb*Zb);END;

3-Procedure SumZ(E/ Z1,Z2: Tcomplex; S/ Z: Tcomplex);

Beginning

Za←Z1.a+Z2.a ; Zb←Z1.b+Z2.b ;
END;

DiffZ Procedure(E/ Z1,Z2: Tcomplex; S/ Z: Tcomplex);

Beginning
Za←Z1.a-Z2.a; Zb←Z1.b-Z2.b ;
END;

Procedure ProdZ(E/ Z1,Z2: Tcomplex; S/ Z: Tcomplex);

Beginning
Za←Z1.a*Z2.a- Z1.b*Z2.b ;
Zb← Z1.a*Z2.b+ Z1.b*Z2.a ;
END;

4-Procedure ConjZ(E/ Z: Tcomplex; S/ ZC: Tcomplex);

Corrected Algorithmic Exercises – 1st Year MI38

The Recordings

Beginning

ZC.a←Za ; ZC.b← -Zb;

END;

5-EqualZ Function(Z1,Z2 : Tcomplex) : Boolean ;

Beginning

IfZ1.a=Z2.a and Z1.b=Z2.bSOEqualZ← TrueOtherwiseEqualZ← FalseFsi;

END;

6- ProcedureWriteZ(Z:Tcomplex);
Beginning

IfZb=0SOWrite(Za)
Otherwise IfZa=0SOWrite(Zb,'i')
Otherwise IfZb>0SOWrite(Za,'+',Zb,'i')
OtherwiseWrite(Za,Zb,'i')
Fsi;
Fsi;
Fsi;
END;
7-
AlgorithmComplex ;
KindTcomplex=Record a,b:real;END;
ConstZ0.a=0 ; Z0.b=0 ;/*shift of a zero complex constant; Var
TC:Array[1..100] of Tcomplex;
I,N: integer;
Z,Zs,Zp,Zm:Tcomplex;
M,Max :reel ;
Find :boolean;
/*declaration of the different APs
----
Beginning

Write('Give N');
RepeatRead(N);UntilN>0 and N≤100; /
*reading the array of complexes ForI←1
to N
DoRead(TC[I].a, TC[I].b);
/* we can also do
WithT[I]DoRead(a,b)Do;
/*or use an intermediate variable of type Tcomplex
Read(Za,Zb);
T[I]←Z;
Do;
/*Find the number with the largest modulus
Zm←TC[1] ; Max←ModuleZ(Zm);

Corrected Algorithmic Exercises – 1st Year MI39

The Recordings

ForI←2 to N
Do
M← ModuleZ(TC[I]) ;
IfM>MaxSO Zm← TC[I] ;
Max←M
Fsi;
Do;
Write('The complex number with the largest modulus is:',WriteZ(Zm)) ; /*
Search for the conjugate of Zm in TC Find←False; I←1; As long asI≤N and Not
Found Do

Find← EqualZ(TC[I],ConjZ(Zm)); I
←I+1 ;
Do;
IfFindSOWrite('Len conjugate exists'OtherwiseWrite('the conjugate does not exist')Fsi; /
*calculate the sum and the product, we initialize Zs to Z0 and Zp to 1 Zs←Z0 ; Zp.a←1 ; Zp.b←0 ;
ForI←1 to N

Do
IfNot EqualZ(TC[I],Z0)
SO
SumZ(Zs,TC[I],Zs) ;
ProdZ(Zp,TC[I],Zp)
Fsi;
Do;
DiffZ(Zs,Zp,Z) ;
IfReelZ(Z)=0 and ImagZ(Z)≠0SOWriteZ(Z)Fsi;
END.

EXERCISE 3
Let Tdate be a date type composed of the integer fields DD,MM,YY.

- Write an APCompareDallowing to compare two dates D1 and D2.

- Let TD be an array of N dates (N≤100). Using the APCompareD,write an algorithm to sort this
table in ascending order of dates.

KindTdate = Record DD,MM,YY: integer;END;

We consider a Function that can take 1 for >, 0 for = and -1 for <
CompareD function(D1,D2:Tdate):integer; Beginning

IfD1.AA>D2.AA

Corrected Algorithmic Exercises – 1st Year MI40

The Recordings

SOCompareD←1
Otherwise IfD1.AA<D2.AA
SOCompareD← -1
Otherwise IfD1.MM>D2.MM
SOCompareD←1
Otherwise IfD1.MM<D2.MM
SOCompareD← -1
Otherwise IfD1.JJ>D2.JJ
SOCompareD←1
Otherwise IfD1.JJ<D2.JJ
SOCompareD← -1
OtherwiseCompareD← 0
Fsi
Fsi
Fsi
Fsi
Fsi
Fsi;
END;

AlgorithmTriDate ;
KindTdate = Record DD,MM,YY: integer;END; Var
TD: Table[1..100] of Tdate;
D:Tdate;
I,J: integer;
CompareD function(D1,D2:Tdate):integer;
----
Beginning

Write('Give N');
RepeatRead(N);UntilN>0 and N≤100; /
*reading the date table ForI←1 to N

DoRead(TD[I].DD, TD[I].MM, TD[I].YY);Do; /

*sorting
ForI←1 to N-1
Do
ForJ←I+1 to N
Do
IfCompareD(TD[I], TD[J])=1
SOD← TD[I]; TD[I]←TD[J]; TD[J]←D Fsi;

Do;
Do;

Corrected Algorithmic Exercises – 1st Year MI41

The Recordings

/*display sorted dates

ForI←1 to N
DoWrite(TD[I].DD,'/', TD[I].MM,'/', TD[I].YY);Do;
END.

EXERCISE 4
Write a function that determines the difference in number of days between two dates.

KindTdate = Record DD,MM,YY: integer;END; We

will write some useful functions:
- A function that determines whether a year is a leap year:

BIS6 function(A:integer):boolean;
Beginning
If(A mod 4=0 and A mod 100≠0)or(A mod 400=0)
SOBIS6←TrueOtherwiseBIS6← False Fsi;

END;

- A NBJour function which gives the number of days from 01/01/AA to DD/MM/AA of a given date

NBjour function(D:Tdate):integer;
VarI: integer;
Beginning

NBDay←D.DD ;
ForI←1hasD.MM-1
Do
CaseIWorth
1,3,5,7,8,10,12 : NBDay←NBDay+31 ; /*monthWith31 days
4,6,9,11 : NBDay←NBDay+30 ; /*monthWith30 days
2:IfBIS6(D.AA)SONBJour←NBJour+29OtherwiseNBJour←NBJour+28Fsi;
Farms;
Do;
END;
We resume theFunctionwhich compares 2 dates.
CompareD function(D1,D2:Tdate):integer;
-----
Finally our function:

D1 D2

D1 J2
Years (in days) between the two dates (DA)

Corrected Algorithmic Exercises – 1st Year MI42

The Recordings

Difference (in days) between the two dates = D2+DA-D1

DiffDay Function(D1,D2:Tdate):integer;
VarJ1,J2: integer;
D:Tdate;
Beginning

/*sort the two dates

IfCompareD(D1,D2)=1SOD←D1 ; D1←D2 ; D2←DFsi; /*Count
the number of days of D1 and that of D2 D1←NBDay(D1); D2
←NBDay(D2);
/*Add the years (in days) between the two dates
ForI←D1.AA to D2.AA-1
Do IfBIS6(I)SOJ2←J2+366OtherwiseJ2←J2+365Fsi;Do;
DiffDay←D2-D1 ;
END;

EXERCISE 5
Let a record E be defined by two pieces of information:
- T an array of integers that can contain a maximum of 100 elements;
- N the number of elements in the array T.
Given a string M, write a parameterized action that returns a record of type E containing all the
positions of the string 'ab' in the string M.
Example: M = 'faabaababbaabrs'
Positions: 3 - 6 - 8 - 12
Number of elements: 4

KindE=Recording
T: Array[1..100] of integer; N:
integer;
END ;
ProcedureABPos(E/ M:string[250];S/ Pos:E); VarI,J,T:
integer; Beginning

T←Size(M); I←1 ; J←1 ; SN←0 ; As

long asI<T
Do IfM[I]='a' and M[I+1]='b'
SOST[J] ←I ; SN←S.N+1 ; D←D+1 ; I←I+2
OtherwiseI←I+1
Fsi;
Do;
END;

EXERCISE 6
Consider the following record types: Type
TDate = Record
Day, month, year: integer;

Corrected Algorithmic Exercises – 1st Year MI43

The Recordings

END;
TAddress = Registration
Number: integer;
Street: string [50];
City: string [20];
Wilaya: string [20];
Cw: integer; { Wilaya Code }
END;
THabitant = Recording
Name, first name: string [20];
Date_of_birth: date;
Residence: Address;
END;
Write an algorithm to:
1- Fill in a table T of N inhabitants (N≤100).
2- Display from T the addresses of residents born before a given year of birth.
3- Display the names and dates of birth of the inhabitants of the city of 'Zemmouri' in the wilaya of
'Boumerdes'.
4- Edit the number of inhabitants per wilaya.

AlgorithmResident;
KindTDate = Recording
Day, month, year: integer;
END;
TAddress = Registration
Number: integer;
Street: string [50];
City: string [20];
Wilaya: string [20];
Cw: integer; { Wilaya Code }
END;
THabitant = Recording
Name, first name: string [20];
Date_of_birth: date;
DIfdence: Address;
END;
VarT: Table[1..100] of THabitant;
TW:Array[1..48] of integer;
I,N,A:integer;
EH:THabiant;
Beginning

Write('Give N');
RepeatRead(N);UntilN>0 and N≤100;

Corrected Algorithmic Exercises – 1st Year MI44

The Recordings

/*reading the Inhabitants table

ForI←1 to N
Do
With
EH,EH.Date_of_birth,EH.Residence Do
Read(Name,First name);
Read(Day,Month,Year);
Read(Number,Street,City,Wilaya,CW);
Do;
T[I]←EH;
Do;
/*display addresses of residents born before year A
Write('Give a Year'); Read(A); ForI←1 to N

Do
WithT[I].Date_of birth, T[I].Residence
Do
IfYear=ASOWrite(Number,' ',Street,' ',City,' ',Wilaya)Fsi;
Do;
Do;
/*display names and addresses of residents of Zemmouri
ForI←1 to N
Do
WithT[I],T[I].Date_of birth,T[I].Residence
Do
IfCity='zemmouri' and Wilaya='Boumerdes'
SOWrite(Name,First name,' ',Day,'/',Month,'/',Year)Fsi;
Do;
Do;
/*number of inhabitants per wilaya; /
*initialize to 0;
ForI←1 to 48DoTW[I]←0 ;Do; ForI←1
to N
DoTW[T[I].ReIfdence.CW]← TW[T[I].Residence.CW]+1 ;Do;
/*we can also use an intermediate variable /* A
← T[I].Residence.CW; TW[A]← TW[A]+1;
/*display
ForI←1 to 48DoWrite('Wilaya',I,'Number',TW[I]);Do;
END.

EXERCISE 7
We are interested in the management of vehicles in a fleet. Each vehicle is characterized by a registration number,
a brand, a model, a color, the number of seats, a taxable horsepower.

Corrected Algorithmic Exercises – 1st Year MI45

The Recordings

1- Provide the record to describe a vehicle.

2- Break down the registration number into its elementary components then give the new structure of
the recording.
3- Write an algorithm that allows:
- Store information on a fleet of up to 50 vehicles using the appropriate structures;

- Establish the list (registration number, make, model, power) of vehicles of a given color;
- Establish a statistical table containing the number of vehicles registered by wilaya;

1-
KindTVehicule=Recording

Registration number: string[11];

Brand:chain[20];
Model: string[10] ;
Nbp,Then:integer;
END;
2- New structure after decomposition of the registration
number: KindTMatricule=Registration
Num:string[6];
Cat: character;
Year:chain[2];
END;
TVehicule=Recording
Registration number: TRegistration number;

Brand:chain[20];
Model,Color:string[10];
Nbp,Then:integer;
END;
3-
AlgorithmPark ;
KindTMatricule=Registration
/*declare the different fields as strings in order to be able to display the 0 /
*without doing any processing
Num:string[6];
Cat: character;
Year:chain[2];
Cw:string[2];
END ;
TVehicule=Recording
Registration number: TRegistration number;

Brand:chain[20];
Model,Color:string[10];
Nbp,Then:integer;

Corrected Algorithmic Exercises – 1st Year MI46

The Recordings

END ;
Var TP: Array[1..500] of Tvehicule ;
TW: Array[1..48] of integer ;
V: Vehicle;
I,N,A: integer;
Collar: chain[10] ;
/*Function to convert a string into an integer; Function
ValCh(ch:string[10]):integer; VarI,T,P,V: integer;
Beginning

P←1 ; ValCh←0 ; T←Size(ch); For

I←1 to T
Do Casech[T-I+1]Worth
'0' :V←0 ;
'1' :V←1 ;
'2' :V←2 ;
'3' :V←3 ;
'4' :V←4 ;
'5' :V←5 ;
'6' :V←6 ;
'7' :V←7 ;
'8' :V←8 ;
'9' :V←9 ;
Farms;
ValCh←ValCh+V*P ;
P←P*10;
END;
Beginning

Write('Give N');
RepeatRead(N);UntilN>0 and N≤500; /
*reading the Vehicles table ForI←1 to
N
Do
WithV,V.Matriculation number

Do
Read(Num,Cat,Year);
Read(Brand,Model,Color,Nbp,Then);
Do;
TP[I]←V;
Do;
Write('Give a color'); Read(Col); ForI
←1 to N
Do

Corrected Algorithmic Exercises – 1st Year MI47

The Recordings

WithTP[I], TP[I].Matriculation

number Do
IfCol=Color
SO
Write(Num,'-',Cat+Year,'-',Cw);
Write(Make,Model, ,Then);
Fsi;
Do;
Do;
/*number of vehicles per wilaya; /
*initialize to 0;
ForI←1 to 48DoTW[I]←0 ;Do; ForI←1
to N
DoA← ValCh(TP[I].Matricule.Cw); TW[A]← TW[A]+1;Do; /
*display
ForI←1 to 48DoWrite('Wilaya',I,'Number',TW[I]);Do;
END.

Corrected Algorithmic Exercises – 1st Year MI48

The Files

EXERCISE 1
Let the file NUMBERS.BIN contain a list of integers. Write an algorithm that displays the
numbers in the file, their sum and their average.

AlgorithmNumber;
VarF: Integer file;
X,S,Nb: integer; M: real;
Beginning

Assign(F,'NUMBERS.BIN'); Reread(F);
Nb←0; S←0;
As long asNon FDF(F)
Do
Read(F,X); /*Read an element from the
file Write(X); /*display on screen S
←S+X; Nb←Nb+1;
Do;
IfNb≠0SOM←S/Nb ;
Write('Sum of elements =',S,' Average =',M)
OtherwiseWrite('Empty file')
Fsi;
Close(F);
END.

EXERCISE 2
1- Write an algorithm that creates the file MOTS.TXT containing a series of words (maximum length of a word:
20 characters). The word entry will end when the symbol is entered'*'which will not be written to the file.

2- Write an algorithm that displays the number of words as well as the average length of the words contained in the
MOTS.TXT file.
3- Write an algorithm that creates a second MOTS10.TXT file containing the words from the MOTS.TXT file
more than 10 characters.

AlgorithmTreatWord;
VarF,G:String file[20];
X:string[20];
Nb: integer; M:reel;
Beginning

/*question 1
Assign(F,'WORDS.TXT'); Rewrite(F); /*open F in writing Write('Give a
sequence of words. Enter the word '*' to stop typing'); Read(X);/*Read
the first word outside the loop As long asX≠'*'

Do
Write(F,X);
Read(X); /*Read the next word
Do;
Close(F);

Corrected Algorithmic Exercises – 1st Year MI49

The Files

/*question 2
Nb←0 ; M←0 ;/*we can use M for the sum of the lengths then for the average
Reread(F)/*open F in reading As long asNon FDF(F)

Do
Read(F,X);/*Readan element of the
file M←M+Size(X); Nb←Nb+1; Do;

IfNb≠0 SO M←M/Nb ;
Write('Number of words =',Nb,' Average length =',M)
Otherwise Write('Empty file')
Fsi;
Close(F);

/*question 3
Assign(G,'MOTS10.TXT') ; Rewrite(G) ; Reread(F)/*open G for writing and F for reading As
long asNon FDF(F)
Do
Read(F,X);/*Readan element of the
file IfSize(X)>10SOWrite(G,X)Fsi; Do;

Close(F); Close(G);
END.

EXERCISE 3
Consider the following record type:
Student Type = Record
Registration number: integer;
Name, First name: string [20];
Average: real;
END;
EitherTa table of at most 100 students.
Write an algorithm to copy all admitted students belonging toTin a fileADMITTEDstudent type. A
student is admitted if his average is greater than or equal to 10.

AlgorithmStudy ;
KindStudent = Registration
Registration number: integer;
Name, First name: string [20];
Average: real;
END;
Var T:Table[1..100] of Student;
F:File of Student;
X: Student;
I,N: integer;

Corrected Algorithmic Exercises – 1st Year MI50

The Files

Beginning

Write('Give the number of 'students');

/*reading array elements Repeat
Read(N)UntilN>0 and N≤100; ForI←1
to N
Do
WithX
DoRead (Matriculation number);

Read(Name,First name);
Read(Average);
Do;
T[I]←X ;
/*We can use T[I] directly and avoid the assignment(in blue) With
T[I]
Do Read(Matriculation number);

Read(Name, First name);

Read(Average) ;
Do ;
Do;
/*creation of the admissions file
Assign(F,'ADMITTED'); Rewrite(F); For
I←1 to N
Do
IfT[I].Average)≥10SOWrite(F,T[I])Fsi; /*same
remark, we can use an X record X←T[I] ;

If X.Average)≥10 Then Write(F,X) Fsi ;

Do;
Close(F);
END.

EXERCISE 4
Consider the following records:
KindTDate =RegistrationDay, month, year: integer;END;
TDiscipline =RegistrationDiscipline: chain [10]; Faculty: chain [20];END;
Student =RegistrationName, first name: string [20];
DateN: TDate;
Sector: TDiscipline;
END;
EitherStudenta student file. Write an algorithm that allows:
- Fill in the fileStudent.
- Explode the fileStudentin two files,F1(students of the faculty'FEI') AndF2(students from other
faculties).

AlgorithmBurst;
KindTDate = Record Day, month, year: integer; End;
TDiscipline = Record Discipline: string [10]; Faculty: string [20]; End;

Corrected Algorithmic Exercises – 1st Year MI51

The Files

Student = Registration Name, first name: string [20];

DateN: TDate;
Sector: TDiscipline;
END;
Var Student: T Student;
F,F1,F2: Student File;
FEI,Other: Boolean;
Beginning

Assign(F,'FEtudiant'); Rewrite(F); With

Student, Student.DateN, Student.Field Do
Write('Name:') ;Read(Name) ;/*Read1ername outside the loop As
long asName<>''
Do
Write('First name:') ;Read(first name) ;
Write('Date of birth:') ;Read(Day,month,year) ;
Write('Discipline, Faculty:') ;Read(Discipline, Faculty) ;
Write(F,Student) ;
Write('Name:') ;Read(Name) ; /*Read the next name
Do;
Do;
Close(F);
Reread(F);
/*To avoid creating empty files, we can use these 2 boolean indicators, in thisCase /*assignment and
creation are only done if we find an element, then we set the boolean back to /*true to avoid repeating
these operations
/*THIS OPERATION IS NOT MANDATORY BUT IT IS BETTER TO KNOW FEI
←False; Other ←False;
/*If we do not use these booleans, we must assign and open the 2 files for writing at this
level Assign(F1,'FFEI'); Rewrite(F1); Assign(F2,'FAutrer'); Rewrite(F2);

IfFDF(F)SO Write('Empty file')

Otherwise As long asNon FDF(F)
DoRead(F,Student);
WithStudent.Sector
Do IfFaculty ='FEI'
SO If not FEI
Then Assign(F1,'FFEI'); Rewrite(F1); FEI ←True Fsi;
Write(F1,Student);
Otherwise If No Other
Then Assign(F2,'FAtrer'); Rewrite(F2); Other←True
Fsi;
Write(F2,Student);
Fsi;
Do;
Do;
Close(F);

Corrected Algorithmic Exercises – 1st Year MI52

The Files

If FEI ThenClose (F1)Fsi ; If

Other ThenClose (F2)Fsi ;
Fsi;
END.

EXERCISE 5
1- Let F1 and F2 be two files of strictly positive integers without repetition. Write an algorithm that constructs
(creates) a file G of integers such that G contains for each value of F1 the value and all its multiples
belonging to F2 (F1 and F2 are assumed to exist).
Example :
F1: 3 10 20 17

F2: 3 6 19 60 40 30
G:3 3 6 60 3010 60 40 3020 60 4017
2- Write an algorithm which allows from the result file (G) to generate another file (H) containing all
the values of the file (G) (without repetition) with their number.

Example :
H: 32 61 603 302 101 402 201 171

1-
AlgorithmMultiple ;
Var F1,F2,G: integer file; X,Y:
integer;
Beginning

Assign(F1,'File1'); Assign(F2,'File2'); Assign(G,'File3');

Reread(F1); Rewrite(G);
As long asNon FDF(F1)
Do
Read(F1,X); Write(G,X);
Reread (F2);/*return to the beginning of the file at each iteration F2 As
long asNon FDF(F2)
Do
Read(F2,Y);
IfY MOD X = 0SOWrite(G,Y)Fsi; Do;

Close(F2);
Do;
Close(F1); Close(G);
END.

2-
AlgorithmValRepetition;
Var G,H,G1,G2: integer file;
X,Y,N :integer:Inter:boolean;

Corrected Algorithmic Exercises – 1st Year MI53

The Files

Beginning

Assign(G,'File3'); Assign(H,'FileH'); Assign(G1,'Inter1'); Assign(G2,'Inter2');

Reread(G); Rewrite(G1);
/*Copy of G into G1, using intermediate files As long as
Non FDF(G)DoRead(G,X); Write(G1,X);Do; Close(G);
Close(G1); Reread(G1); Rewrite(H); Inter←True;

As long asNon FDF(G1)

Do
Read(G1,X); Write(H,X);
/* Process repeats and create G2 (unprocessed)
Rewrite(G2); N ←1; As long asNon FDF(G1)

Do
Read(G1,Y);
IfX=YSON ←N+1Otherwise Write(G2,Y)Fsi; Do
;
/*Write the repetition of X
Write(H,N);
Close(G1); Close(G2);
/*Copy G2 to G1 To process the rest. Overwrite the old G1
Reread(G2); Rewrite(G1);
As long asNon FDF(G2)DoRead(G2,X); Write(G1,X);Do;

/*or to optimize, change the assignment of the 2 files G1 and G2 in an alternating manner
Inter← No Inter ; If Inter

SO Assign(G1,'Inter1'); Assign(G2,'Inter2');
Otherwise Assign(G1,'Inter2'); Assign(G2,'Inter1');
Fsi ;

Close(G1); Close(G2);
/*Reopen G1 for reading (unprocessed)
Reread(G1);
Do;
Close(G1); Close(H);
END.

EXERCISE 6
Let F be a file of integers representing sequences of numbers separated by one or more zeros. Write an algorithm
that performs the following processing:
1- From F (existing file), create a file G containing for each sequence, the average of the numbers which
constitute it.
2- Then, Delete the null values from the G file.
Example:

Corrected Algorithmic Exercises – 1st Year MI54

The Files

F: 0 01 4 3 7 0 0 06 -9 2 7 -6 0-10 3 0 0

G: 3.75 0.00 -3.50 Before deletion

G: 3.75 - 3.50 After deletion

AlgorithmProcessFile;
VarF: Integer file;
G,H: Reel file;
X,S,Nb: integer; M: real;
Beginning

Assign(F,'FileF'); Reread(F);
Assign(G,'FileG'); Rewrite(G); As
long asNon FDF(F)
Do
Read(F,X);
IfX≠0
SOS←0 ; Nb←0 ;
As long asNo FDF(F) and X≠0
Do S←S+X ;
Nb←Nb+1 ;
Read(F,X);
Do;
/*processing the last non-zero element of the file, the head is onFDF, but X not
treated? IfX≠0SOS←S+X ; Nb←Nb+1Fsi; M←S/Nb ;

Write(G,M);
Fsi;
Do;
Close(F); Close(G);
/*To remove null values from G we use an intermediate file, then we copy this /*file
into G
Assign(H,'Inter'); Rewrite(H); Reread(G); As
long asNon FDF(G)
Do
Read(G,X);
IfX≠0SOWrite(H,X)Fsi; Do;

Close(H); Close(G);

/*copy H to G
Reread(H); Rewrite(G);
As long asNon FDF(H)
Do
Read(H,X);
Write(G,X);
Do;
Close(H); Close(G);

Corrected Algorithmic Exercises – 1st Year MI55

The Files

END.

EXERCISE 7
Let F1 be a character file containing a sequence of telegrams. Each telegram consists of a sequence of words
separated by one or more spaces (̂ ). The telegram ends with the word 'FINTEL'.

Write an algorithm that allows, for each telegram, to print the text, respecting the following
conventions:
- Printed words will be separated by a single space.
- Words cannot exceed 12 characters otherwise they will be truncated on the right.
- The text of each telegram is followed by an indication of the total number of words (truncated or not) and the number of
truncated words.
- The end of each telegram will be indicated by 'FINTEL'.

Version 1: Displaying telegrams on screen

AlgorithmTelegram;
VarF:character file;
Nbmot, NbmotTq: integer; C:
character;
Word:string;
WordTq:string[12];
Beginning

Assign(F,'telegram.txt'); Reread(F);
Nbmot←0; NbmotTq←0;
As long asNon FDF(F)
Do
Read(F,C);
IfC<>' '
SO
Word←''/*initialize empty word As
long as(No FDF(F) and C< >' ' ) Do

Word←Word+C;/*use concatenation
Read(F,C);
Do;
/*process last character IfC< >' '
SOWord←Word+CFsi; If
word='FINTEL'
SO /*end processing Write(nbmot,'
',nbmotTq,' FINTEL') ; IfNon FDF(F)
SOTo write(' ')Fsi; Nbmot←0;
NbmotTq←0;
Otherwise /*word processing
Nbmot←Nbmot+1;
IfSize(Word)>12
SO WordTq←Word;/*This action truncates the word
NbmotTq←NbmotTq+1;

Corrected Algorithmic Exercises – 1st Year MI56

The Files

Word←WordTq
Fsi;
Write(Word,' ')
Fsi
Fsi;
Do;
Close(F);
END.

Version 2: Creating a telegram file while respecting the constraints

In thisCasewe will need aFunctionto convert integers to string

AlgorithmTelegram;
VarF,FC:Character file;
Nbmot, NbmotTq,I,T: integer; C:
character;
Word:string;
WordTq:string[12];
FunctionIntToStr(X:integer):string; Var
R:integer; Ch:string; Beginning

Ch←'';
Repeat
R←X MOD 10;
X←X DIV 10;
CaseRWorth
0:Ch←'0'+Ch;
1:Ch←'1'+Ch;
2:Ch←'2'+Ch;
3:Ch←'3'+Ch;
4:Ch←'4'+Ch;
5:Ch←'5'+Ch;
6:Ch←'6'+Ch;
7:Ch←'7'+Ch;
8:Ch←'8'+Ch;
9:Ch←'9'+Ch;
Farms;
UntilX=0;
IntToStr←Ch;
END;

Beginning

Assign(F,'telegram.txt'); Reread(F);
Assign(FC,'telegramC.txt'); Rewrite(FC);
Nbword←0; NbwordTq←0;
As long asNon FDF(F)
Do

Corrected Algorithmic Exercises – 1st Year MI57

The Files

Read(F,C);
IfC<>' '
SO
Word←'' /* initialize empty word
As long as(No FDF(F) and C< >' ' )
Do
Word←Word+C; /*use concatenation
Read(F,C);
Do;
/*process last character
IfC< >' 'SOWord←Word+CFsi; If
Word='FINTEL'
SO /*end processing
Word←IntToStr(nbword)+' '+IntToStr(nbmotTq)+' FINTEL' ;
IfNon FDF(F)SOWord←Word+' 'Fsi; T←Size(Word);

ForI←1 to TDoWrite(FC,Word[I])Do;
Nbmot←0; NbmotTq←0;
Otherwise /*word processing
Nbmot←Nbmot+1;
IfSize(Word)>12
SO WordTq←Word;/*This action truncates the word
NbmotTq←NbmotTq+1;
Word←WordTq
Fsi;
Word←Word+' ' ;/*add a blank T
←Size(Word);
ForI←1 to TDoWrite(FC,Word[I])Do
Fsi
Fsi;
Do;
Close(F); Close(FC);
END.

EXERCISE 8
Write a procedure that deletes the last element of the integer file F.
Using the previous procedure, write an algorithm to empty an existing file F of integers and physical name
'ESSAI.DAT', element by element. This algorithm should display, after the deletion of each element, the
average of the remaining elements of F.

KindFent:Integer file;

/*the assignment can be done inside the procedure, but we prefer to do it outside
Assign(F,'FENT.DAT');

ProcedureSupD(E/S/F:Fent);
VarG: Fent; X, integer;

Corrected Algorithmic Exercises – 1st Year MI58

The Files

Beginning

Reread(F);
Ifnon FDF(F
SO /*the assignment of the intermediate file is done inside, because it is a local file
Assign(G,'G'); Rewrite(G); Read(F,x);

/* starting with Writing before Reading allows you to copy the elements of F /* into G
except the last one, we willRead, but we don't write it, the head is onFDF, if F /* contains
only one element. It will not be copied to G (the loop does not execute, we are on /*FDF)

As long asnon FDF(F)

Do
Write(G,x);
Read(F,x);
Do;
Close(F); Close(G);
/* Replace file F with G which does not contain the last element (copy G to F)
Reread(G); Rewrite(F); As long asnon FDF(G)

Do
Read (G,x);
Write (F,x);
Do;
Close(G);
Fsi;
Close(F);
END;

AlgorithmPhone ;
VarF:integer file;
X,S,Nb: integer; M: real;
ProcedureSupD(E/S/F:Fent);
-----
Beginning

Assign(F,'ESSAI.DAT');
Reread(F);
As long as not
FDF(F) Do
SupD(F);
Reread(F);
S←0 ; Nb←0 ;
As long as not
FDF(F) Do
Read(F,X);
S←S+X ; Nb←Nb+1 ;
Do;
IfNb≠0SOM←S/Nb ;

Corrected Algorithmic Exercises – 1st Year MI59

The Files

Write('Average=',M)
OtherwiseWrite('File is empty')
Fsi;
Do;
Close(F);
END.

EXERCISE 9
Let F1 and F2 be two files of strings. Each string represents a word. Write an algorithm that constructs
a file F3, such that F3 contains the words in F1 that do not exist in F2.

AlgorithmWord123;
Var F1,F2,F3: string file[30]; X,Y:
String[30];
Find :boolean;
Beginning

Assign(F1,'File1'); Assign(F2,'File2'); Assign(F3,'File3');

Reread(F1); Rewrite(F3);
As long asNon FDF(F1)
Do
Read(F1,X);/*Reada word from F1
Find←False;/*we assume that the word does not exist in F2 Reread
(F2);/*return to the beginning of the file at each iteration F2 As
long asNo FDF(F2) and Not Found Do

Read(F2,Y);
IfY=XSOFind ←TrueFsi; Do;

/* If the word is not found after theFDFfrom F2 we put it in

F3 IfNot FoundSOWrite(F3,X)Fsi; Close(F2);

Do;
Close(F1); Close(F3);
END.

EXERCISE 10
Let's say the following type:

Product Type = Registration

Code: Integer;
Designation: Chain [80];
Price: Actual;
END ;
Let F be a product file. Write aFunctionwhich checks if the elements of F are sorted in ascending order of their
Code.

FunctionFtrie(F:Product file):booleen; Var

Eprod: Product;
Code: integer;

Corrected Algorithmic Exercises – 1st Year MI60

The Files

Beginning

Assign(F,'Product.dat'); Reread(F);
Ftrie ←True;
IfNon FDF(F)
SO Read(F,Eprod);
As long asnon FDF(F) and Ftrie
Do code ←Eprod.code ;
Read(F,Eprod);
Ifcode> Eprod.codeSOFtrie ← FalseFsi;
Do
Fsi;
END;

EXERCISE 11

Using mobile phones allows storing the contact directory in two files:
- A 'TEL.DAT' file, saved in the phone's memory;
- A 'SIM.DAT' file, saved on the SIM card memory.
Each file contains references of a contact grouping: a name, a first name and a telephone number. The elements of
the two files are assumed to be already sorted according to the telephone number.
1- Give the syntax (instructions) for assigning and opening the two files.
2- Write a procedure that allows you to store duplicates in another file. An element is a duplicate if it
exists in both files.

1- Assign(Ftel,'tel.dat'); Reread(Ftel);
Assign(Fsim,'sim.dat'); Reread(Ftel);
2-
Kindcontact=Registration
Name,first name:string[30];
Number:string[10];
END ;
ProcedureFdouble(E/Ftel,Fsim:contact file; S/FD:contact file); Var
cont1,cont2:contact;
Find,double:boolean;
Beginning

Double ←true ;
As long asnon FDF(ftel)
Do Read(Ftel,cont1);
Reread(fsim); find ←false; As long as
not FDF(fsim) and not found Do
Read(fsim,cont2);
Ifcont1=cont2So ifdouble
SO Assign(FD,'Fdouble.dat');
Rewrite(FD); double ←False
Fsi;
Write(FD,cont1);
Find ←True
Fsi;

Corrected Algorithmic Exercises – 1st Year MI61

The Files

Do;
Close(fsim);
Do;
Close(Ftel);
Ifnon-doubleSOclose(FD)Fsi;
END;

EXERCISE 12
EitherFmotan alphabetic character file containing words separated by one or more whitespace characters. 1-
Write a functionPalindromewhich checks if a given word is a palindrome word.
2- Write an algorithm that displays the number of palindrome words and the shortest palindrome word.

1-
FunctionPalindrome(word:string):boolean;
Var I,T: integer;
Beginning

T←Size(word); Plaindrome ←true; I ←1; As

long asPalindrome and I<T DIV 2 Do If
word[I]<>word[T-I+1] SOPalindrome
←FalseFsi; I ←I+1 ;

Do;
END;

2-
AlgorithmCourtPal;
Kindch:chain[50];
Var Fmot: character file;
tmin,t,NBpal: integer;
X: character;
Word,cpal:ch;
FunctionPalindrome(word:string):boolean;
------

Beginning

Assign(Fmot,'fmot'); reread(Fmot);
tmin ←51; cpal ←''; NBpla← 0; As long
asnon FDF(Fmot)
Do Read(Fmot,X);/*retrieve a word
Word←'' ;/*initialize empty As long
asnon FDF(Fmot) and (X<>' ' Do

Word←Word+X ;
Read(Fmot,X);
Do;
/*process last character IfX<>' '
SOWord←Word+XFsi;

Corrected Algorithmic Exercises – 1st Year MI62

The Files

IfWord<>''
SO
IfPalindrome(word)
SO t ←Size(word); NBpal←NBpal+1 ; If
t<tmin
SO tmin ←t ;
Cpal ←word ;
Fsi;
Fsi;
Fsi;
Do;
IfNBcpal<>0
SO Write('The number of palindrome words is:',NBpal
Write('the shortest palindrome word is:',cpal)
Otherwise Write('No palindrome words or file is empty')
Fsi;
Close(Fmot);
END.

EXERCISE 13
Let F be an integer file (assumed to exist) composed of sequences of numbers, each sequence is a repetition of the
same number (non-zero). All sequences are separated by a zero. And no sequence of the same number is repeated
in the file.
F 14 14 14 0 5 5 0 29 29 29 29 0 6 6 6
Position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1- Write a parameterized actionCompresswhich creates a G record file containing for each sequence the
number represented as well as the length of the sequence.
Number 14 5296
G
Length 3 243

2- Using a single traversal of the file G and without re-traversing the file F, find the position in F of the most
long sequence. (ex:Position = 8)
3- Write a parameterized actionDecompresswhich allows to reconstruct a file H (of the same type as F) at
from a file of the same type as G.

1-
Kind
Elcp=Registration
Val,Long:integer;
END ;
Fent: Integer File;
Felcp: Elcp File;

Assignment is done externally as follows:

Assign(F,'Fname'); Assign(G,'Gname');

Corrected Algorithmic Exercises – 1st Year MI63

The Files

ProcedureCompress(I/O/F: Fent; I/O/G: Felcp);

Var X,I:Integer; EC:Elcp;
Beginning

Reread (F); Rewrite (G);

As long asNon FDF(F)
Do Read (F,X);
EC.Val ← X ; I ← 0 ; As long
asNo FDF(F) and X<>0 DoI ←
I+1 ;
Read (F,X);
Do;
IfFDF(F)SOI ← I+1Fsi;
EC.Long ← I ; Write (G,EC) ;
Do;
Close(F); Close(G);
END;
2-
FunctionPosMax(G:Felcp): Integer;
VarK,Max: Integer; EC:Elcp;
Beginning
Reread(G); Max ← 0; K←0;
As long asNon FDF(G)
Do Read(G,EC);
IfEC.Long > Max SO
Max ← EC.Long ;
PosMax ← K+1
Fsi;
K ← K+EC.Long+1;
Do;
Close(G);
END;

3-
ProcedureDecompress(I/O/G:Felcp; I/O/F:Fent);
VarI:Integer; EC:Elcp;
Beginning

Reread(G); Rewrite(F); As
long asNon FDF(G)
DoRead(G,EC);
ForI ← 1 to EC.Long DoWrite(F,
EC.Val);Do; IfNon FDF(G)SO
Write(F,0)Fsi;
Do;
Close(G); Close(F);
END;

Corrected Algorithmic Exercises – 1st Year MI64

Linked Lists

EXERCISE 1
Let A be a matrix (N,M) of integers. Write an algorithm that generates two lists from this matrix. 1- The
first one groups the minimums of the lines (FIFO);
2- And, the second the sum of the columns (LIFO).

AlgorithmMatList;
Kind Plist=^List;
List=Record
Val: integer;
Next: List;
END;
Var A: Array[1..100,1..150] of integer;
I,J,N,M,Min,S: integer;
Lmin,Lsom,P,Q:Plist;
Beginning

RepeatRead(N);Until(N>0) and (N≤100);

RepeatRead(M);Until(M>0) and (M≤150); /
*Reading the Matrix
ForI ←1hasNDo ForJ ←1hasMDo
Read(A[I,J]);
Do;
Do;
/* Generation of the Lmin list (FiFo) /*
Create the head after calculating 1ermin
Min← A[1,1] ;
ForJ←2 to MDo IfA[1,J]<MinSOMin← A[1,J]Fsi;Do;
Allocate(Lmin); Lmin̂ .Val←Min; P←Lmin; ForI ←2hasN

Do /*calculation of
Min i Min← A[I,1] ;
ForJ←2hasMDo IfA[I,J]<MinSOMin← A[I,J]Fsi;Do; /*create a
list item and update the chaining Allocate(Q);

Q̂ .Val←Min ; P .̂Next←Q ; P←Q ;

Do;
P .̂Next←Nil ;
/* Generation of the Lsom list (LiFo)
Lsom←Nil ;
ForJ ←1hasM
Do S←0 ;
/* Calculation of column sum ForI←1
hasNDoS←S+A[I,J] ;Do;
/*create a list item and update the chaining
Allocate(P);
P .̂Val←S ; P .̂Next←Lsom ; Lsom←P ;
Do;
END.

Corrected Algorithmic Exercises – 1st Year MI65

Linked Lists

EXERCISE 2
Let be a list of integersL, write the following parameterized actions allowing:
1- Calculating the number of elements, and determining the maximum and
minimum; 2- Inserting a given value val into a sorted list;
3- Deletion of duplicates (identical elements);
4- Creation of the mirror list of L (with then without creation of a new list); 5-
Duplication of a list at the beginning / at the end;
6- Merging two sorted lists of integers L1 and L2 into a sorted list L3;

1-
ProcedureCalList(E/ L: List; S/ Nbl, Max, Min: integer);
Beginning
Nbl←0 ;
IfL≠Nil
SO Max←L .̂Val ; Min←L .̂Val ; Nbl←1 ; L←L̂ .Next; As
long asL≠Nil
Do IfL .Val>Max
SOMax←L .̂Val
Otherwise IfL .Val<MinSOMin←L̂ .ValFsi Fsi
;
Nbl←Nbl+1 ;
L←L .̂Next ;
Do;
Fsi;
END;
2-
ProcedureInsert(E/S/ L:Plist; E/ V:integer);
VarP,Q,R:Plist;
Beginning

/*create the new element to insert

Allocate(P); P.̂Val←V; P.̂Next←Nil; If
L=Nil
SOL←P
Otherwise IfV<L̂ .Val
SO /*Insert at the beginning
P .̂Next←L ;
L←P
Otherwise/*search for the insertion location, then insert, you must keep the previous one (R)
R←L ; Q←L .̂Next ;
As long asQ≠Nil and V≥Q .̂ValDoR←Q ; Q←Q .̂NextDo;
R .̂Next←P ; P .̂Next←Q
Fsi
Fsi;

Corrected Algorithmic Exercises – 1st Year MI66

Linked Lists

END;

3-
ProcedureSupDouble(E/L:Plist); Var
P,Q,R: List; Beginning

IfL≠Nil
SO
P←L ;
As long asP .̂Next≠Nil
Do Q←P .̂Next ; R←P ; As
long asQ≠Nil
Do IfQ .̂Val=P .̂Val
SO R .̂Next←Q .̂Next ;
Release(Q);
Q← R .̂Next
OtherwiseR←Q ;
Q←Q .̂Next
Fsi;
Do;
P←P .̂Next ;
Do
Fsi;
END;
4-
Creating a new mirror list (this is equivalent to creating a LIFO list from L)
ProcedureMirrorNew(E/L:Plist; S/M:Plist); VarP: List;

Beginning

M←Nil ;
As long asL≠Nil
Do Allocate(P);
P .̂Val←L .̂Val ;
P .̂Next←M ;
M←P ;
L←L .̂Next ;
Do;
END;

Create a mirror list of L without new allocations (this is equivalent to reversing the list).

ProcedureInvert(I/O/L:Plist); Var
P,Q: List; Beginning

IfL≠Nil
SO Q←L̂ .Next; L̂ .Next←Nile; As
long asQ≠Nil
DoP←Q .̂Next; Q .̂Next←L ;
L←Q ; Q←P ;
Do;

Corrected Algorithmic Exercises – 1st Year MI67

Linked Lists

Fsi;
END;

5-
We can use a DF parameter for the duplication type (Start: 0; End: 1) to not write 2 Pro.
ProcedureDuplicateD(I/S/ L:Plist; E/DF:integer); Var
P,Q,R,T,T0: List; Beginning

IfL≠Nil
SO T←L ;/*save head L /*Create a
FIFO list from L
Allocate(P); P .̂Val←T .̂Val; Q←P;/*P is the head of the new list T0←T ;
T←T .̂Next ; As long asT≠Nil

Do Allocate(R); R .̂Val←T .̂Val;

Q .̂Next←R;
Q←R ;
T0←T ;/*T0 is the last element of L T
←T .̂Next ;
Do;
IfDF=0
SO /*Connect the end of the created list to the beginning of the initial list (L)
Q .̂Next←L ;
L←P/*change the head of the initial list Otherwise/*Connect
last element of L (T0) to the beginning of the list
Q .̂Next←Nil ;
T0 .̂Next←P
Fsi;
Fsi;
END;

6-
Merging 2 sorted lists into a new list Procedure
FusionNew(E/ L1,L2:Plist; S/ L:Plist); VarP,Q: List;
Beginning

IfL1≠Nil and L2
≠Nil SO/*create 1erelement of L
Allocate(L);
IfL1 .̂Val<L2 .̂ValSOL .Val←L1 .̂Val ; L1←L1 .̂Next
OtherwiseL .Val←L2 .̂Val ; L2←L2 .̂Next
Fsi;
P←L ;
/*browse the 2 lists
Tank L1≠Nil and L2≠Nil
Do Allocate(Q);
IfL1 .̂Val<L2 .̂ValSOQ .̂Val←L1 .̂Val ; L1←L1 .̂Next
OtherwiseQ .̂Val←L2 .̂Val ; L2←L2 .̂Next
Fsi;
P .̂Next←Q ;

Corrected Algorithmic Exercises – 1st Year MI68

Linked Lists

P←Q ;
Do;
/*continue with L1 or with L2 As
long asL1≠Nil
Do Allocate(Q);
Q .̂Val←L1 .̂Val ; L1←L1 .̂Next; P .̂Next←Q ; P
←Q ;
Do;
As long asL2≠Nil
Do Allocate(Q);
Q .̂Val←L2 .̂Val ; L2←L2 .̂Next; P .̂Next←Q ; P
←Q ;
Do;
P .̂Next←Nil
Otherwise/*one of the 2 lists is empty or both are empty
L←Nil ;
IfL1≠Nil
SO /*create 1erelement of L
Allocate(L);
L̂ .Val←L1 .̂Val ; L1←L1 .̂Next ; P←L ; As
long asL1≠Nil
Do Allocate(Q);
Q .̂Val←L1 .̂Val ; L1←L1 .̂Next; P .̂Next←Q ; P
←Q ;
Do;
P .̂Next←Nil ;
Fsi;

IfL2≠Nil
SO /*create 1erelement of L
Allocate(L);
L̂ .Val←L2 .̂Val ; L2←L2 .̂Next; As P←L ;
long asL2≠Nil
Do Allocate(Q);
Q .̂Val←L2 .̂Val ; L2←L2 .̂Next; P .̂Next←Q ; P
←Q ;
Do;
P .̂Next←Nil ;
Fsi;
Fsi;
END;

Merging two sorted lists into a 3rd list without allocation

ProcedureFusionNew(E/ L1,L2:Plist; S/ L:Plist);

VarP: List;
Beginning

IfL1≠Nil and L2
≠Nil SO/*create 1erelement of L
IfL1 .̂Val<L2 .̂ValSOL←L1 ;
L1←L1 .̂Next

Corrected Algorithmic Exercises – 1st Year MI69

Linked Lists

OtherwiseL←L2 ;
L2←L2 .̂Next
Fsi;
P←L ;
/*traverse the 2 lists
Tanque L1≠Nil and L2≠Nil
Do IfL1 .̂Val<L2 .̂ValSOP .̂Next ←L1; P←L1;
L1←L1 .̂Next
OtherwiseP .̂Next ←L2; P←L2;
L2←L2 .̂Next
Fsi;
Do;
/*continue with L1 or with L2
IfL1≠Nil SOP .̂Next ←L1
OtherwiseP .̂Next ←L2
Fsi
Otherwise/*one of the 2 lists is empty or both are empty
IfL1≠Nil SOL←L1
OtherwiseL←L2
Fsi;
END;

EXERCISE 3
Let T be an array of 26 lists of strings. List 1 contains words starting with the letter 'A', list 2 contains
words starting with the letter 'B'…etc.
Declare T and write aFunctionallowing to check the existence of a word M in the structure.

FunctionFind(E/ T:List; E/ M:String[25]):Boolean; Var

L:Cliste;
Beginning

/*get the head of the list of words starting with the same character as M L
←T[M[1]] ;
/*Search for M
Find←False;
As long asL≠Nil and Not
IfL .Word=MSOFind←TrueFsi; L
Found Do
←L̂ .Next ;
Do;
END;

EXERCISE 4
Let L be a list of positive integers. Write a procedure that splits the list L into two lists: Lp containing the
even integers and Li containing the odd integers. (Without creating new lists).

ProcedureBurst(E/ L: Plis; S/ Lp,Li: Plis); Var

Pp,Pi:Plist; Beginning

Lp←Nil ; Li←Nil ; As
long asL≠Nil
Do IfL .Val MOD 2=0 SO/*check if Lp head is created
IfLp=NilSO Lp←L ;

Corrected Algorithmic Exercises – 1st Year MI70

Linked Lists

Pp←L
Otherwise Pp .̂Next←L ;
Pp←L
Fsi
Otherwise /*check if Li head is created
IfLi=Nil SO Li←L ;
Pi←L
Otherwise Pî .Next←L ;
Pi←L
Fsi
Fsi;
L←L̂ .Next ;
Do;
IfLp≠NilSOPp .̂Next←NilFsi; IfLi
≠NilSOPî .Next←NilFsi;
END;

EXERCISE 5
Let two lists of integers L1 and L2 be:
1- Write a function that checks if L1 and L2 are identical (contain the same elements in the same
order).
2- Write a function that checks if L1 is included in L2 (all the elements of L1 are in L2, here the order
does not count).
3- Write a function that checks if L1 and L2 are disjoint (L1 ∩ L2 = Ø).

1)
FunctionSame (L1,L2:Plist):Boolean;
Beginning
Same←True;
As long asL1≠Nil and L2≠Nil and
Idem DoIfL1^.Val≠L2^.ValSOSame←FalseFsi; L1
←L1^.Next ;
L2←L2^.Next ;
Do;
IfL1≠Nil or L2≠NilSOSame←FalseFsi;
END;

2)
FunctionIncluded(L1,L2:Plist):Boolean;
Var T: List;
Beginning

Included ←True ;
As long asL1≠Nil and
Included Included←False;
Do
T←L2 ;/*to return to each at the beginning of the list L2 As
long asL2≠Nil Not Included Do
IfL1^.Val=T̂ .ValSOIncluded←TrueFsi; T
←T̂ .Next ;
Do;
L1←L1^.Next ;
Do;
END;

3)

Corrected Algorithmic Exercises – 1st Year MI71

Linked Lists

FunctionDisjoint(L1,L2:Plist):Boolean;
Var T: List;
Beginning

Disjoint ←True ;
As long asL1≠Nil and Disjoint
Do T←L2 ;/*to return to each at the beginning of the list L2 As
long asT≠Nil and Disjoint Do
IfL1^.Val=T̂ .ValSODisjoint ←FalseFsi; T
←T̂ .Next ;
Do;
L1←L1^.Next ;
Do;
END;

EXERCISE 6
Let two lists L1 and L2 of positive integer values:
Write a parameterized action to move (without allocation or freeing) even values from L1 to L2, and to
move odd values from L2 to L1;

ProcedureMove(I/O/L1,L2:List); Var
P,Q,T2:List;
Beginning

/*detach even values from L1 and put them at the beginning

of L2 Q←L1 ;P←L1 ; T2←L2 ;/*save head L2 As long asQ≠Nil

Do IfQ̂ .Val MOD 2=0

SO IfQ=L1
SO Q̂ .Next←L2 ; L2←Q ;
Q←Q̂ .Next;
L1←Q
Otherwise P .̂Next←Q̂ .Next ;
Q̂ .Next←L2 ; L2←Q ; Q
←P .̂Next
Fsi
Otherwise P←Q ;
Q←Q̂ .Next
Fsi;
Do;
/*at this level L1 is empty or contains only odd elements /*detach
the odd values from L2 and put them at the beginning of L1 /
*search for the last even value inserted in L2 if it exists IfT2=L2

SO Q←L2 ; P←L2
Otherwise Q←T2 ; P←L2
As long asP .̂Next≠T2DoQ←Q̂ .Next ;Do
Fsi;
/*Optimization: Processing L2 from T2
As long asQ≠Nil
Do IfQ̂ .Val MOD 2≠0
SO IfQ=P
SO Q̂ .Next←L1 ; L1←Q ;
Q←Q̂ .Next;
L2←Q
Otherwise P .̂Next←Q̂ .Next ;

Corrected Algorithmic Exercises – 1st Year MI72

Linked Lists

Q̂ .Next←L1 ; L1←Q ;
Q←P .̂Next
Fsi
Otherwise P←Q ;
Q←Q̂ .Next
Fsi;
Do ;
END ;

EXERCISE 7
EitherNOTESa grade file containing the result of the algorithmic module (existing file), such that the ith element of
the file contains the grade obtained by student numberi.
1-Write a parameterized actionCREATIONwhich builds, from the fileNOTES, a linked linear listL
containing all the students (for each student we keep the number and the grade obtained).
2-Write a parameterized actionDELETEallowing the removal of deferred students from list L (not
keep only admitted students).

Kind Pnote=^NoteAlgo ;
NoteAlgo=Recording
Num: integer;
Note: real ;
Next: Pnote;
END;
Fnote: Reel file;
1)
The file assignment is assumed to be outside: Assign(F,'Notes');

ProcedureCreation(E/F:Fnote; S/L:Pnote);
Var P,Q:Pnote;
X:real; I:integer;
Beginning

L←Nil ;
Reread(F);
Ifnon FDF(F)
SO /*create the head of the list
(fifo) Read(F,X); I←1;
Allocate(L);
L̂ .Num←I ; L .̂Note←X ; P←L ; /*create
the other elements of the list As long
asNon FDF(F)
Do Read(F,X); I←I+1;
Allocate(Q);
Q̂ .Num←I ; Q .̂Note←X ;
P .̂Next←Q ;
P←Q ;
Do;
P .̂Next←Nil
Fsi;
Close(F);
END;

2)
Procedure Deletion (I/O/L: Pnote);
Var P,Q:Pnote;

Corrected Algorithmic Exercises – 1st Year MI73

Linked Lists

Beginning

IfL≠Nil
SO /*delete start
As long asL≠Nil and L̂ .Note<10
DoP←L ; L←L̂ .Next ; Release(P);Do; /*deletion elsewhere,
we must keep track of the previous one (P) P←L ; Q←L ;

IfP≠NilSOQ←P^.NextFsi; As
long asQ≠Nil
Do IfQ̂ .Note<10SO P .̂Next←Q̂ .Next ;
Q←P .̂Next
Otherwise P←Q ;
Q←Q̂ .Next
Fsi;
Do
Fsi;
END;

EXERCISE 8
Let L be a list of students. Each student is defined by their matriculation number (integer), their first and last name (string) and their
course ('ACAD', 'GTR' or 'ISIL').

1- Give the declaration of this list.

2- Write a procedureBURSTwhich allows the list L to be split into two lists L1 containing the students of the
'GTR' and L2 stream containing students from the 'ISIL' stream. In the end, the original list L will contain
students from the 'ACAD' stream only.

1-
KindPEtud=^Student ;
Student=Registration
Registration number: integer;

Name,First name:chain[25];
Sector:chain[4];
Next: PEtud;
END;
East of theKindPetud

2-
ProcedureBurst(E/S/ L,L1,L2:PEtud);
Var P1,P2,LnP,Lp:PEtud;
Beginning

L1←Nile ; L2←Nile ; Ln←Nil ; As

long asL≠Nil
Do IfL .Line='GTR' SO
IfL1=Nil
SO L1←L ; P1←L
Otherwise P1 .̂Next←L ; P1←L
Fsi
Otherwise IfL .File='ISIL' SO
IfL2=Nil
SO L2←L ; P2←L
Otherwise P2 .̂Next←L ; P2←L
Fsi
Otherwise IfLn=Nil

Corrected Algorithmic Exercises – 1st Year MI74

Linked Lists

SO Ln←L ; Lp←L
Otherwise Lp^.Next←L ; Lp←L
Fsi
Fsi;
L←L̂ .Next ;
Do;
L←Ln ;
IfLn≠NilSOLp^.Next←NilFsi; IfL1
≠NilSOP1 .̂Next←NilFsi; IfL2≠Nil
SOP2 .̂Next←NilFsi;
END;

EXERCISE 9
A pharmacist wants to process information about his stock of
medicines by computer. You are asked to represent this
information in the form of a linked linear list where each element
contains the label of a medicine, the quantity available (number of
boxes) and the unit price.

1- Provide the data structures necessary for the representation of this stock (see diagram).
2- Write the procedureSell(Med, NbBoxes) allowing to remove,Ifpossible, 'NbBoites' of the drug 'Med'
from stock. (The medicine whose quantity reaches 0 must be removed from stock).
3- Write the procedureBuy(Med, NbBoites, Prix) allowing the pharmacist to supply his stock by
'NbBoxes' of the drug 'Med' having the unit price 'Price' DA. It is considered that a drug always takes
the new price.Ifthe medicine does not exist, it must be inserted.
4- Write the functionValStockto calculate the value of drugs in stock.

1-
KindPmedic=^Medic ;
Medic=Recording
Label: string[15] ;
Qty: integer;
Price: real ;
Next: Pmedic;
END;

2-
ProcedureSell(E/S/ M:Pmedic;E/ Med:string[15]; E/NB:integer; S/Possible:booleen);
Var P:Pmedic;
Beginning

Possible←False;
IfM≠Nil
SO P←M ; Q←M ;
/*Med search
As long asQ≠Nil and Q̂ .Libele≠MedDoP←Q ; Q←Q̂ .Next ;Do; If
Q≠Nil
SO /*we found Med, we test if the sale is possible
IfQ̂ .Qty≥NB
SO Possible←True;
Q̂ .Qte←Q̂ .Qte-NB ;
/*if qte becomes zero, we delete
IfQ̂ .Qty=0
So ifP=QSOM←P .̂Next ; Release(P)/*Casesup Head

Corrected Algorithmic Exercises – 1st Year MI75

Linked Lists

OtherwiseP .̂Next←Q̂ .Next ; Release(Q)

Fsi
Fsi
Fsi
Fsi
Fsi;
END;

3-
ProcedureBuy(E/S/ M:Pmedic; E/ Med:string[15]; E/ NB:integer; E/ Price:real); Var
P,Q:Pmedic; Beginning

IfM=Nil
SO Allocate(M);
M^.Libele←Med ;
M^.Qte←NB ;
M^.Price←Price;
M^.Next←Nil
Otherwise /*Med Search
P←M ; Q←M ;
/*Med search
As long asQ≠Nil and Q̂ .Libele≠MedDoP←Q ; Q←Q̂ .Next ;Do; If
Q≠Nil
SO /*Med was found, data is updated
Q̂ .Qte←Q̂ .Qte+NB ; Q̂ .Price←Price

Otherwise /*Med does not exist, we create it at the end, after the last element (P)
Allocate(Q);
Q̂ .Libele←Med ; Q̂ .Qte←NB ; Q̂ .Price←Price;
Q̂ .Next←Nil;
P .̂Next←Q
Fsi;
Fsi;
END;

4-
FunctionValStock(M:Pmedic):real;
Beginning
ValStock←0 ;
As long asM≠Nil
DoValStock←ValStock+M^.Qty*M^.Price ; M←M̂ .Next ;Do;
END;

EXERCISE 10
Let the structure below represent a list of lists of integers.

1- Write a function that checks If two lists of integers L1 and

L2 are identical;
2- Write a parameterized action that deletes a list of integers
of the structure;
3- Write an Algorithm that removes all identical lists
duplicate (Each list of integers in the structure must be
unique).

Corrected Algorithmic Exercises – 1st Year MI76

Linked Lists

Structure declaration (PlistV)

Kind
List=^ListH ;
ListH=Record
Val: integer;
Next: List;
END;

ListV=^ListV;
ListV=Record
Next: List;
NextV:PlistV;
END;

1-
FunctionSame (L1,L2:Plist):Boolean;
Beginning
Same←True;
As long asL1≠Nil and L2≠Nil and
Idem DoIfL1^.Val≠L2^.ValSOSame←FalseFsi; L1
←L1^.Next ;
L2←L2^.Next ;
Do;
IfL1≠Nil or L2≠NilSOSame←FalseFsi;
END;

2-
ProcedureDeleteH(I/O/LV:PlistV; I/O/LH:Plist); Var
T,TC:PlistV;
P: List;
Beginning

IfLV≠Nil
SO
IfLV̂ .NextH=LH
SO /*delete head after deleting list H
As long asLH≠NilDoP←LH ; LH←LH .̂Next ; Release(P);Do; T
←LV ; LV←LV̂ .NextV ; Release(T) /*search LV that contains LH T
Otherwise ←LV ; TC← T .̂Next ; As long asTC≠Nil

Do IfTC .̂NextH=LH
SO As long asLH≠NilDoP←LH ; LH←LH .̂Next ; Release(P);Do;
T̂ .NextV←TC .̂NextV ; Release(TC) T←TC ; TC← TC .̂Next
Otherwise

Fsi;
Do
Fsi;
Fsi;
END;

3-
ProcedureSuppDoubleH(I/O/LV:PlisteV);
Var L1,L2: List;
T,TC,TR:PlistV;

Corrected Algorithmic Exercises – 1st Year MI77

Linked Lists

Beginning

T←LV ;
IfT≠Nil
SO L1←T̂ .NextH ;
TR←T ;
TC←T .̂NextV ; /*TR is the previous of TC As
long asTC≠Nil
Do L2←TC .̂NextH ;
IfSame(L1,L2)
SO /*before releasing TC in the procedure we save its Next for the rest TC
←TĈ .NextV ;
DeleteH(LV,L2)
Otherwise TR←TC ; TC←TĈ .NextV
Fsi;
Do;
T←T̂ .NextV
Fsi;
END;

EXERCISE 11
To play Am-Stram-Gram,nchildren form a circle, they choose one of them as the first, start counting
from him and decide that thekthmust leave the round, then again thekthstarting from the next one, and
so on.
Write a function that returns the sequence (as a singly linked list) of children in the order they exited
the round.

The children's circle is represented by a linked list of strings. (It may be interesting to modify this list to
make it circular!).

Deep=^Round
Round=Recording
Name: string[20] ;
Next: Deep;
END;

FunctionOutput(L: Deep; K: integer) : Deep;

Var I: integer;
P,Q, : Deep ;
Beginning

Corrected Algorithmic Exercises – 1st Year MI78

Linked Lists

Output←Nil;
IfL≠Nil
SO /*transform L into a circular list
P←L ;
As long asP .̂Next≠NilDoP←P .̂Next ;Do; P̂ .Next←L ; /
*Creation of the output list in FiFo mode Output←Nil;

IfL≠Nil
SO As long asL .Next
≠L Do For I←1 to K-2DoL←L̂ .Next ;Do; P
←L .̂Next ;/*outgoing element L̂ .Next
/*detach P
←P^.Next ; IfOutput=Nil

SO Output←P ; Q←P/*create the head, Q: last element

Otherwise Q̂ .Next←P ; Q←P/*create others
Fsi;
L← L .̂Next ;
Do;
IfOutput=Nil SOExit←L /*the list contains only 1 element
OtherwiseQ̂ .Next←L
Fsi;
L←Nil
Fsi;
Fsi;
END;

EXERCISE 12
Let L be a list of integers.

1- Write a procedureDETACHEDwhich returns the address of the maximum of the list L and detaches it from the listwithout the
DELETE .
2- Using the procedureDETACHED, write a procedureSORTwhich sorts the list L in descending order
(without creating a new list).

1-
ProcedureDetach(I/S/ L:Plist; S/ Pmax:Plist);
Var Max: integer;
Prx,P,Q:List;
Beginning

Pmax←L ;
IfL≠Nil
SO P←L ; Max←P .̂Val ; Pmax←L ; Q
←P .̂Next;
As long asQ≠Nil
Do IfQ̂ .Val>MaxSOMax← Q̂ .Val; Pmax←Q ;Prx←PFsi; P←Q ; Q
←Q .̂Next ;
Do;
IfPmax=L
SO L←L̂ .Next
Otherwise Prx̂ .Next←Pmax^.Next

Corrected Algorithmic Exercises – 1st Year MI79

Linked Lists

Fsi;
Fsi;
END;

2-
ProcedureSort(I/O/L:Plist);
Var T,P,Q: List;
Beginning

/*Sorting in descending order using DETACHE involves creating a FIFO list T←Nil ;

IfL≠Nil
SO /*Create the head
Detach(L,P);
T←P ;
/*create the other elements
As long asL≠Nil
Do Detach(L,Q);
P .̂Next←Q ;
P←Q ;
Do;
P .̂Next←Nil ;
L←T
Fsi;
END;

EXERCISE 13
In this exercise, we propose to develop a module allowing to manipulate sparse polynomials. A sparse
polynomial is a polynomial containing very few non-zero monomials.
Example: P(x) = 5.6 x1280+ 0.8 x – 9 contains 1281 terms of which only 3 are non-zero. Each
monomial is described by a record of typeTmonomecomprising the following 3 fields:
- Deg:integer representing the degree of the monomial;
- Coef:real representing the coefficient of the monomial;
- Next:pointer to the next monomial.
The list representing the polynomial will be sorted in descending order of degree. An empty list (Nil) corresponds to the zero
polynomial;
1- Write a procedureAddwhich adds to a polynomial (Pol) the value
of a monomial defined by its degree (Deg) and its coefficient (Coef). 2-
Write the proceduresSumAndProductwho respectively realize the
sum and product of two polynomials Pol1 and Pol2.
3- Write aValue Functionwhich calculates the value of the polynomial for a
value val of the variable x.
4- Write a procedureDerivativewhich determines the derivative DPol of a polynomial Pol.
5- Write a procedurePrimitivewhich determines the primitive PPol of a polynomial Pol, knowing that
PPol(0)=1.

Kind
Tmonome=̂ Monome ;
Monome=Recording
Coef:real;
Deg: integer;

Corrected Algorithmic Exercises – 1st Year MI80

Linked Lists

Next: Tmonome;
END;
1-
ProcedureAdd(I/O/Pol:Tmonome; E/M:Tmonome); Var
P,Q: Tmonome; Beginning

IfM^.Coef≠0
SO
IfPol=Nil
SOPol←M ; M^.Next←Nil
Otherwise/*search for add position or update Coef in =
IfM^.Deg>Pol.Deg
SOM^.Next←Pol ; Pol←M/*add to beginning
Otherwise IfPol̂ .Deg=M^.Deg
SO /*update Coef, then free M
Pol̂ .Coef←Pol̂ .Coef+M .̂Coef ;
Free(M)/*inCaseequality, we no longer need M /*If the
Coef becomes zero, we remove the monomial
IfPol̂ .Coef=0SOP←Pol ; Pol←Pol̂ .Next ; Release(P)Fsi
OtherwiseP←Pol ; Q←P .̂Next ;
As long asQ≠Nil and
Q .̂Deg>M^.Deg DoP←Q ; Q
←Q .̂Next ;Do; IfQ=Nil
SOP .̂Next←M ; M .̂Next←Nil
Otherwise IfQ .̂Deg=M^.Deg
SOQ .̂Coef←Q .̂Coef+M .̂Coef ;
Free(M)/*inCaseequality, we no longer need M /*If the
Coef becomes zero, we remove the monomial
IfQ .̂Coef=0
SOP .̂Next←Q .̂Next ; Free(Q)Fsi
OtherwiseP .̂Next←M ; M .̂Next←Q
Fsi
Fsi
Fsi
Fsi
Fsi;
END;

2-
ProcedureSum(E/ Pol1,Pol2:Tmonome; S/ Pol3:Tmonome); VarM:
Tmonome; Beginning

/*Add all monomials from Pol1 to Pol3== Duplication of Pol1 In Pol3 Pol3
←Nil ;
As long asPol1≠Nil
Do Allocate(M); M^.Deg←Pol1 .̂Deg; M .̂Coef←Pol1 .̂Coef;
Add(Pol3,M);
Pol1←Pol1 .̂Next ;
Do;
/*Add all monomials from Pol2 to Pol3 As
long asPol2≠Nil

Corrected Algorithmic Exercises – 1st Year MI81

Linked Lists

Do Allocate(M); M^.Deg←Pol2 .̂Deg; M .̂Coef←Pol2 .̂Coef;

Add(Pol3,M);
Pol2←Pol2 .̂Next ;
Do;
END;

ProcedureProduct(E/ Pol1,Pol2:Tmonome; S/ Pol3:Tmonome); Var

M,P: Tmonome; Beginning

Pol3←Nil ;
IfPol≠Nil and Pol2
≠Nil SO
/*Multiply each monomial of Pol2 by Pol1 and add to Pol3 As
long asPol2≠Nil
Do P←Pol1 ;
As long asP≠Nil
Do Allocate(M);
M^.Deg← Pol2 .̂Deg +P .̂Deg ; M .̂Coef← Pol2^.Coef *P .̂Coef ;
Add(Pol3,M);
P←P .̂Next ;
Do;
Pol2←Pol2 .̂Next ;
Do;
END;

3-
FunctionValue(E/ Pol :Tmonome ; E/ X :real ):real ;
Var I: whole;
Px: real;
Beginning

Value←0;
As long asPol≠Nil
Do Px←1 ;
For I←1 to Pol̂ .DegDoPx←Px*X ;Do;/*power of X calculation Value
←Value+Pol̂ .Coef*Px; Pol←Pol̂ .Next;

Do;
END;

4-
ProcedureDerive(E/ Pol:Tmonome; S/ DPol:Tmonome); Var
M,P: Tmonome; Beginning

Dpol←Nil ;
IfPol≠Nil
SO /*create the first monomial of DPol
IfPol̂ .Deg≠0
SO Allocate(Dpol);
DPol̂ .Coef←Pol̂ .Coef*Pol̂ .Deg ;
DPol̂ .Deg←Pol̂ .Deg-1 ;
P←Dpol

Corrected Algorithmic Exercises – 1st Year MI82

Linked Lists

Fsi;
Pol←Pol̂ .Next ;
/*create the other monomials of DPol
As long asPol≠Nil
Do IfPol̂ .Deg≠0
SO Allocate(M));
M^.Coef←Pol̂ .Coef*Pol̂ .Deg ;
M^.Deg←Pol̂ .Deg-1 ;
P .̂Next←M ;
P←M ;
Fsi;
Pol←Pol̂ .Next ;
Do;
IfDpol≠NilSOP .̂Next←NilFsi
Fsi;
END;

- We can also calculate the Derivative usingAdd,but the first solution is moreoptimal.

ProcedureDerive(E/ Pol:Tmonome; S/ DPol:Tmonome); Var

M,P: Tmonome; Beginning

Dpol←Nil ;
As long asPol≠Nil
Do IfPol̂ .Deg≠0
SO Allocate(M));
M^.Coef←Pol̂ .Coef*Pol̂ .Deg ;
M^.Deg←Pol̂ .Deg-1 ;
Add(DPol,M);
Fsi;
Pol←Pol̂ .Next ;
Do;
END;

5-
ProcedurePrimitive(E/ Pol:Tmonome; S/ PPol:Tmonome); Var
M,P: Tmonome; Beginning

Ppol←Nil ;
IfPol≠Nil
SO /*create the first monomial of PPol
Allocate(Ppol);
PPol̂ .Coef←Pol̂ .Coef/(Pol̂ .Deg+1);
PPol̂ .Deg←Pol̂ .Deg+1 ;
P←Ppol ;
Pol←Pol̂ .Next ;
/*create the other monomials of PPol
As long asPol≠Nil
Do Allocate(M));
M^.Coef← Pol̂ .Coef/(Pol̂ .Deg+1);
M^.Deg←Pol̂ .Deg+1 ;

Corrected Algorithmic Exercises – 1st Year MI83

Linked Lists

P .̂Next←M ;
P←M ;
Pol←Pol̂ .Next ;
Do;
Fsi;
/*create the constant
Allocate(M); M̂ .Deg←0; M̂ .̂Coef←1; M̂ .Next←Nil;/*PPol(0)=1 If
Ppol≠NilSOP .̂Next←MOtherwisePPol←MFsi;
END;

- We can also calculate the primitive usingAdd,but the first solution is moreoptimal.

ProcedurePrimitive(E/ Pol:Tmonome; S/ PPol:Tmonome); Var

M,P: Tmonome; Beginning

Ppol←Nil ;
As long asPol≠Nil
Do Allocate(M));
M̂ .Coef← Pol̂ .Coef/(Pol̂ .Deg+1);
M̂ .Deg←Pol̂ .Deg+1 ;
Add(Ppol,M);
Pol←Pol̂ .Next ;
Do;
/*create the constant
Allocate(M); M^.Deg←0; M.̂Coef←1; M^.Next←Nil;/*PPol(0)=1 If
Ppol≠NilSOP .̂Next←MOtherwisePPol←MFsi;
END;

EXERCISE 14
Definition : A matrix is called sparse if it mainly contains
zero coefficients (elements).

Example: sparse matrix 1 20 0 0 0 0 0 0 0 01

03 90 0 0 0 0 0 0 0 0

0 0 0 0 0 01040 0 0

A sparse matrix can be represented by taking into account only the non-zero elements using a
linked list. Using the list representation of a sparse matrix:
1- Give the declaration of the necessary data structure.
2- Write the procedure to fill such a structure for a given sparse matrix A(M,N). 3- Write the
parameterized action to calculate the sum of two matrices thus represented.
4- Write a procedure to display a matrix represented in this way.

1-
KindPMat= Matrix ;
Matrix=recording
I,J,Val: integer;

Corrected Algorithmic Exercises – 1st Year MI84

Linked Lists

Next:list;
END;

2-
ProcedureFillA(E/S/A:Pmat); Var
P,Q:list;
I,J,V: integer;
Beginning

A←Nil ;
Read(I,J,V);
IfV<>0
SO /*create head
Allocate(A);
 .I ←I ;  .J ←J ;  .Val ←V ; P←A;

/*create the rest of the elements, we consider that the values are introduced line by line
Read(I,J,V);
As long as V<>0
Do Allocate(Q);
Q̂ .I ←I ; Q̂ .J ←J ; Q .Val ←V ;
P .̂Next←Q;
P ←Q ;
Read(I,J,V);
Do;
P .̂Next←Nil
Fsi;
END;

3-
ProcedureSum(E/ A,B:Pmat; S/ C:Pmat);
Var P,Q,R,E:Pmat;
Beginning

/*Creating the matrix C comes down to merging the 2 lists A and B based on the indices C
←Nil ;
As long asA≠Nil and B
≠Nil Do IfHAS .I<B .̂I
SO Allocate(E);
E .̂I←Â .I ;E .̂J←A .̂J ; E .̂Val←A .̂Val ; A
←A .̂Next
Otherwise IfHAS .I>B .̂I
SO Allocate(E);
E .̂I←B .̂I ;E .̂J←B .̂J ; E .̂Val←B .̂Val ; B
←B .̂Next
Otherwise/*A .̂I=B .̂I, we move on to J
IfHAS .J<B .̂J
SO Allocate(E);
E .̂I←Â .I ;E .̂J←A .̂J ; E .̂Val←A .̂Val ; A
←A .̂Next

Corrected Algorithmic Exercises – 1st Year MI85

Linked Lists

Otherwise IfHAS .J>B .̂J

SO Allocate(E);
E .̂I←B .̂I ;E .̂J←B .̂J ; E .̂Val←B .̂Val ; B
←B .̂Next
Otherwise/*A .̂I=B .̂I and A .̂J=B .̂J, we check if the sum ≠ 0
If(HAS .Val+B .̂Val)
SO Allocate(E);
E .̂I←B .̂I ;E .̂J←B .̂J ; E .̂Val←Â .Val+B .̂Val ;
Fsi
Fsi
Fsi
Fsi;
IfC=Nil
SO /*first element
C←E ; P←C
Otherwise/*other element
P .̂Next←E ; P←E
Fsi;
Do;
/*continue with A or with B As
long asA≠Nil
Do Allocate(E);
E .̂I←Â .I ;E .̂J←A .̂J ;
E .̂Val←Â .Val ; A
←A .̂Next;
IfC=Nil
SO /*first element
C←E ; P←C
Otherwise/*other element
P .̂Next←E ; P←E
Fsi;
Do;
As long asB≠Nil
Do Allocate(E);
E .̂I←B .̂I ;E .̂J←B .̂J ;
E .̂Val←B .̂Val ; B
←B .̂Next;
IfC=Nil
SO /*first element
C←E ; P←C
Otherwise/*other element
P .̂Next←E ; P←E
Fsi;
Do;
IfC≠NilSOP .̂Next←NilFsi;
END;

4-
ProcedureDisplayA(E/A:Pmat);
Beginning
As long asA≠Nil

Corrected Algorithmic Exercises – 1st Year MI86

Linked Lists

Do Write('A[',P^.I,',', P .̂J,']=', P .̂Val) ; P

←P .̂Next ;
Do;
END;

EXERCISE 15
Let L be a list of characters constituting words (a word is a sequence of characters not containing a space)
separated by a single space character.
Write a procedure that reverses the words in list L without creating a new list.

Kind
Cliste=^Lcar ;
Lcar=Recording
because: character;
Next: List;
END ;

ProcedureInverseM(E/S/L:Cliste); Var
D,F,P,Q,B:Cliste; Beginning

D←L ;
IfL≠Nil
SO /*processing first word F
←L .̂Next ;
As long asF≠Nil and F̂ .Car≠'
' Do P←F̂ .Next;
F̂ .Next←L ;
L←F ;
F←P ;
Do;
D .̂Next←F ;
/* processing of other words
Q←F ;
As long asQ≠Nil
Do B←Q ;/*if Q≠Nil it is on a blank B
Q←Q .̂Next ; D←Q ;/*D is the first character of the word F
←Q .̂Next ;
As long asF≠Nil and F̂ .Car≠'
' Do P←F̂ .Next;
F̂ .Next←Q ;
Q←F ;
F←P ;
Do;
B .̂Next←Q ;/*Q is on the last character of the word
Q←F ;/*F is on a white or Nil
D .̂Next←Q ;
Do;
Fsi;
END;

Corrected Algorithmic Exercises – 1st Year MI87