Algorithm Design
Algorithm Design
i i
Algorithm Design
A bestseller in its French edition, this book is original in its construction and
its success in the French market demonstrates its appeal. It is based on three
principles: (1) An organization of the chapters by families of algorithms:
exhaustive search, divide and conquer, etc. On the contrary, there is no chapter
devoted only to a systematic exposure of, say, algorithms on strings. Some of
these will be found in different chapters. (2) For each family of algorithms, an
introduction is given to the mathematical principles and the issues of a rigorous
design, with one or two pedagogical examples. (3) For the most part, the book
details 150 problems, spanning seven families of algorithms. For each problem, a
precise and progressive statement is given. More importantly, a complete solution
is detailed, with respect to the design principles that have been presented; often,
some classical errors are pointed out. Roughly speaking, two-thirds of the book
is devoted to the detailed rational construction of the solutions.
i i
i i
Taylor & Francis
Taylor & Francis Group
http://taylorandfrancis.com
i i
i i
Algorithm Design
A Methodological Approach
150 Problems and Detailed Solutions
i i
i i
i i
i i
Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot
assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have
attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders
if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please
write and let us know so we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized
in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying,
microfilming, and recording, or in any information storage or retrieval system, without written permission from the
publishers.
For permission to photocopy or use material electronically from this work, access www.copyright.com or contact the
Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. For works that are
not available on CCC please contact [email protected]
Trademark notice: Product or corporate names may be trademarks or registered trademarks and are used only for
identification and explanation without intent to infringe.
DOI: 10.1201/b23251
i i
i i
i i
i i
Contents
Preface ix
v
i i
i i
i i
i i
vi Contents
1.10 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2 Complexity of an algorithm 71
2.1 Reminders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.1.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.1.2 Algorithmics, complexity of an algorithm . . . . . . . . . . . . . . . . 71
2.1.3 Minimum and maximum complexity of an algorithm . . . . . . . . . 73
2.1.4 Orders of growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.1.5 Some examples of complexity . . . . . . . . . . . . . . . . . . . . . . . 76
2.1.6 About elementary operations . . . . . . . . . . . . . . . . . . . . . . . 77
2.1.7 Practical computing time . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.1.8 Pseudo-polynomial problems . . . . . . . . . . . . . . . . . . . . . . . 78
2.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.3 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
i i
i i
i i
i i
Contents vii
i i
i i
i i
i i
viii Contents
Notations 791
Bibliography 797
Index 799
i i
i i
i i
i i
Preface
ix
i i
i i
i i
i i
x Preface
i i
i i
i i
i i
Preface xi
the students examples of methodical design. No problem is the exact rewriting of another
one, and there is full freedom to transpose each of them in a different grounding.
Contents
As already pointed out, this book is organised to successively present the main methodolo-
gies of algorithm design. However, the first chapter “Mathematics and computer science:
some useful notions” recalls mathematical bases, mostly proof principles, with an insis-
tance on induction (recurrence) and combinatorial counting; it also gives a reminder in
data structures (sets, bags, graphs, files, etc.) and provides 21 short problems and solu-
tions. With the same goal, the chapter “Complexity of an algorithm” is a refresher on the
basic ideas of the field and proposes seven problems, the last one being non-classical.
In the chapter “Specification, invariants, and iteration”, we expose the principles of the
rational design of a while loop and give 15 problems, some rather easy and others quite dif-
ficult. The (lengthy) solutions of the latter are examples of what we have previously called
“practicing both deduction and induction”. The following chapter, “Reduce and conquer,
recursion”, shows how to design recursive algorithms with the help of eight classical prob-
lems. We particularly insist on showing how the proof by induction theory can be applied
to certify the exactness of a recursive procedure.
Chapter 5 describes the “Generate and test” methodology, also called “backtracking”.
We show how to obtain a recursive enumeration of the solutions to a combinatorial prob-
lem; we give the different patterns of a program according to its combinatorial nature. We
give general principles to prune the tree of the solutions and illustrate them with 18 prob-
lems. The following chapter tackles the same kind of problems, but with the “Branch and
bound” iterative technique. Here, four classical problems are given and resolved step by
step.
Chapter 7 is devoted to “Greedy algorithms”, suited to the same kind of combinatorial
problems, but with no backtracking. The proof that they produce a good solution is ob-
viously important to elaborate: we give the usual manners to check it, with 14 problems,
some of which require an elaborate solution.
In Chapter 8, the fruitful “Divide and conquer” methodology is carefully analyzed
and an original typology of the related algorithms is given. Their detailed construction is
explained throughout 29 problems—some of them rather sophisticated.
Finally, Chapter 9 describes the “Dynamic programming” approach, often very efficient
to elaborate an optimal (polynomial) solution to a combinatorial (exponential) problem.
The richness and variety of its applications is displayed through 32 problems. Again here,
some are classics and some are unexpected, some are easy and some are difficult.
To sum up, we describe seven methodologies of algorithm design, illustrated by 148
problems. Each problem is precisely described, often in a progressive organization, and
the complete solution up to the pseudo-code is given in a methodical and rational manner.
The problem and the solution are generally divided into several questions. A marginal
note recalls the number of the problem and the number of the question in the problem. For
example, this margin note would indicate the beginning of question 3 of problem 42. In the 42 - Q 3
i i
i i
i i
i i
xii Preface
solution, the answer to question 3 would be indicated in the same way with an A instead
of a Q.
Every problem is given a double evaluation: one for its intrinsic interest, the other for
◦ ◦
◦
its difficulty. There are four levels of increasing interest denoted by ◦ ◦
◦ ◦ ◦ ◦
◦ and four
• •
•
levels of difficulty denoted by • •
• • • •
• .
Attributing an intrinsic interest to a problem is a rather arbitrary task. We have used a
mix of several criteria, the main being its pedagogical quality in illustrating the method-
ology of the chapter. The difficulty level takes into account the manner of describing the
problem; an intrisically difficult problem can be gently proposed when its description is
written as a gradual series of easier questions.
i i
i i
i i
i i
1
Mathematics and computer science: some useful
notions
P. Erdős
DOI: 10.1201/b23251-1 1
i i
i i
i i
i i
equivalence relation “if and only if” and can also be written “≡”. If a and b are elements
of B, then:
The existence of undefined expressions (for instance due to accessing a function out
of its domain or dividing by 0) requires the use of “short-circuit” operators stopping the
evaluation as soon as the result is known. The two short-circuit operators “and then” and
“or else” are defined as follows:
• If a and b are defined:
a and then b ⇔ a and b.
a or else b ⇔ a or b.
• If a is defined whereas b is not:
false and then b ⇔ false.
true and then b is undefined
false or else b is undefined.
true or else b ⇔ true.
• If a is undefined, then whatever b:
a and then b is undefined
a or else b is undefined.
In the context of predicate calculus, quantifiers ∀ and ∃ are defined as follows:
• ”∀x · (D ⇒ T (x))” is true iff, for any x in domain D then T (x) is true. Therefore, this
formula is true if D is empty.
• ”∃x · (D and T (x))” is true iff there is an x in domain D such that T (x) is true. Therefore,
this formula is false if D is empty.
The notation ∄ is a shorthand for not ∃.
The double equivalence:
is the foundation for reasoning by contraposition, where the validity of the implication
not Q ⇒ not P is proven to show that P implies Q.
i i
i i
i i
i i
• excluded middle, claiming that a property which is not false is necessarily true, then its
conjunction with its negation is false,
• the definition of implication: (P ⇒ Q) =
b (not P or Q).
(not P ⇒ false)
⇔ definition of the implication
(not(not P) or false)
⇔ involutivity of the negation
(P or false)
⇔ property of the disjunction
P.
It is important to note that when no contradiction can be exhibited, nothing can be con-
cluded as to P (neither truth nor falsity).
First example
Let us consider the following proposition P: “there is no smallest rational number strictly
greater than 0”. In order to prove P by contradiction, the negation of P is assumed, namely:
“there is a smallest rational number strictly positive r”. From the negation of P, a contra-
diction is searched.
Let s = r/2. By construction, s is a rational number strictly greater than 0 and strictly
smaller than r. This claim is in opposition to P, which states that r is the smallest rational
number.
Thus, it can be concluded that proposition P is for sure true and that there is no smallest
strictly positive rational number.
Second example
One would like to demonstrate that there is no rational number whose square is 2, in other
words one wants to prove the following proposition P “the square root of 2 is an irrational
number”.
Proof. One first assume that there is an element x = p/q of Q+ (the set of positive rational
numbers) such that x2 = 2, with p and q are relatively prime numbers (i.e. p/q is an
irreducible fraction). One has:
i i
i i
i i
i i
⇔ reformulation
2 is a divider of q2
⇔ any even square number is the square of an even number
2 is a divider of q.
One can then deduce that 2 is a divider of both p and q, which entails that p and q
are not relatively prime numbers which is in opposition to the fact p/q is an irreducible
fraction.
In a similar way, it is possible to demonstrate that there is no negative rational num-
ber whose square is 2, otherwise its opposite would be a positive rational number whose
square would be 2. As a consequence, the square root of 2 is an irrational number 1 .
then:
Conclusion ∀n · (n ⩾ n0 ⇒ P(n))
The fact that P(n) is assumed to be true constitutes the induction hypothesis, in order to
(try to) prove P(n + 1). The initialization is also called the base.
Proof. The correction of the proof by induction can be made by reasoning by contradiction.
Let X = {k ∈ N | k ⩾ n0 and P(k) = false}, be the set of integers greater than k0 such that
property P(k) is false. If X is non-empty, it encompasses a smallest element (since in any
set of integers there is an element smaller than all the others), denoted as m. From the
1 This proof was made by Euclide, about 250 B.C.
i i
i i
i i
i i
Example
Let us prove by induction the formula:
X
n
n(n + 1)
i= .
2
i=1
1(1 + 1)
=1
2
which is the same result.
Induction Let us assume that the formula is true for n, with n ⩾ 1, and let us try to prove
that it is still true for (n + 1). In other words, let us try to prove that the induction
formula
Xn
n(n + 1)
i=
2
i=1
entails
X
n+1
(n + 1)(n + 2)
i= .
2
i=1
X
n+1
i
i=1
= ! arithmetics ((n + 1) > 1)
X
n
i + (n + 1)
i=1
= induction hypothesis
n(n + 1)
+ (n + 1)
2
= arithmetics
(n + 1)(n + 2)
.
2
Conclusion The formula is true for n0 = 1. In addition, if it is true for n (where n ⩾ 1),
then it is true for (n + 1). Finally, this demonstration by induction has proven that the
formula is true for any strictly positive integer.
i i
i i
i i
i i
Remark
This demonstration may also be used to prove a result concerning negative integers: if a
formula is true for n = 0, and if the fact that it is true for −n, where n ∈ N, entails that it is
true for (−n − 1), then it is true for any negative integer.
This variant concerns a proposition on integers that are powers of 2. It is also possible
to prove a property on even numbers, or more generally on any infinite subset of N that
may be built by induction (see section 1.3, page 15).
The correctness of this demonstration pattern directly stems from that of the regular
(simple) induction.
Example
Let us prove the following property using strong induction:
Any integer strictly greater than 1 is the product of several prime numbers.
It is assumed that 1 (also called unity) is a prime number.
Induction Let us assume that any integer m less than n and greater than or equal to n0 = 2
is the product of several prime numbers. For n, two exclusive cases are singled out:
• n is prime and then the product of unity and itself, therefore the product of two
prime numbers.
i i
i i
i i
i i
• n has a divisor d, other than 1 and itself. According to the induction hypothesis,
one has n = d · p, where d and p are two integers less than or equal to n and
strictly greater than 1. Each of them is the product of several prime numbers, and
n is also the product of several prime numbers.
Conclusion Any integer strictly greater than 1 is the product of several prime numbers.
Remarks
1. Partition induction must be based on an initialization P(i, s) for which s − i + 1 = 1. In
particular, it cannot rely on an initialization where s − i + 1 = 0. As a matter of fact, in
such a case there is no value for m such that i ⩽ m < s. Similarly, the induction cannot
be based on an initialization P(i, s) such that s − i + 1 > 1. Let us take the example of
P(i, i + 1) as the initialization and let us try to prove that P(i, i + 2) holds. The only two
possible values for m are m = i and m = i+1. If m = i, the first induction hypothesis is
P(i, i) and if m = i + 1, the second induction hypothesis is P(i + 2, i + 2). None of these
predicates is an instance of the initialization and then the related pattern is invalid.
2. The regular simple induction is a special case of partition induction obtained by taking
m = i.
i i
i i
i i
i i
Example
One will once more demonstrate that:
X
n
n · (n + 1)
k=
2
k=1
P
but, this time, using the technique of partition induction. Let us denote S(i, s) = sk=i k
and call P(i, s) the predicate S(i, s) = (s2 − i2 + s + i)/2. If we succeed in proving that
P(i, s) holds, we
P will have more specifically P(1, n) and it can be concluded that S(1, n) =
(n2 + n)/2 = n k=1 k.
Pi
Initialization For any i, one has: S(i, i) = (i2 − i2 + i + i)/2 = i = k=i k.
Induction hypothesis Let us choose m = ⌊(i + s)/2⌋. One has:
m2 − i2 + m + i
• S (i, m) = ,
2
s2 − (m + 1)2 + m + 1 + i
• S (m + 1, s) = .
2
Induction itself Let us demonstrate that, on the basis of the two above hypotheses,
S(i, s) = (s2 − i2 + s + i)/2 for i < s:
S(i, s)
= definition
X
s
k
k=i
= arithmetics (i < s), with m = ⌊(i + s)/2⌋
X
m X
s
k+ k
k=i k=m+1
= definition
S (i, m) + S (m + 1, s)
= induction hypothesis
m2 − i2 + m + i s2 − (m + 1)2 + s + m + 1
+
2 2
= arithmetics
s 2 − i2 + s + i
2
X
s
s 2 − i2 + s + i
Conclusion k= .
2
k=i
Remarks
1. One trick used in the example above consists in replacing a constant (1 as the lower
bound of the quantification) by a variable (i). Such a technique will be encountered
for the construction of iterations in the context of the “strengthening by introducing
variables” (confer section 3.3.3, page 98) where more than necessary is proven in order
to facilitate (in general) the demonstration.
i i
i i
i i
i i
2. When used for the design of algorithms called “Divide and conquer”, the major dif-
ficulty with partition induction lies in the discovery of induction hypotheses and the
way they may be combined to make the final solution, what will be called “gathering
step”.
Property 1:
Let E be a totally ordered set by means of the relation ⪯ and P be a property depending on the
element x of E. If the following property holds:
Proving this property is achieved as a simple transposition of that given in section 1.1.3
for simple induction.
The correctness of this pattern stems from the fact the set N2 of pairs of integers is
equipped with a total order (induced by the total order over N), defined as follows:
Let us consider q the point whose coordinates are denoted by (i, j). The pattern proposed
above aims at assessing that if P holds at any point: (i) of the rectangle 0 .. i − 1, 0 .. j − 1 (the
cases when i = 0 or j = 0 are covered by the initialization), (ii) from (i, 0) to (i, j − 1) of row
i and (iii) (0, j) to (i − 1, j) of column j, then P holds at point (i, j) as well. In other words, if
P holds at any point “lower” (according to ⪯) than point (i, j), P(i, j) holds as well, which
corresponds to the instance of property 1 for the pairs of (N2 , ⪯).
i i
i i
i i
i i
This demonstration pattern is used in problem 21, page 45. It may be transposed to N1 if
needed with an initialization referring to N1 and the induction with N1 −{1}, the conclusion
being:
F(1) = 1
F(2) = 1
F(n) = F(n − 1) + F(n − 2) n>2
P(1) = 1
P(2) = 1
P(3) = 1
P(n) = P(n − 2) + P(n − 3) n>3
f is a linear function. On the other hand, the one appearing in the relation defining factori-
als (number of permutations in a set of n elements) is nonlinear:
Fact(1) = 1
Fact(n) = n · Fact(n − 1) n > 1.
Thanks to the theory of generative functions (see for example [14]), mathematics provide
powerful tools to find closed forms (i.e. nonrecurrent) for some series defined by means of
recurrence relations, especially when f is linear, but also in other cases. Thus, Fibonacci
i i
i i
i i
i i
Recurrence relations 11
Catalan numbers, which are the subject of problems 5, page 34, and 13, page 40, are
defined by the recurrence relation:
Cat(1) = 1
X
n−1
Cat(n) = Cat(i) · Cat(n − i) n>1
i=1
as well as by:
Cat(1) = 1
4n − 6
Cat(n) = · Cat(n − 1) n > 1.
n
A(0, n) = n + 1 n⩾0
A(m, 0) = A(m − 1, 1) m>0
A(m, n) = A(m − 1, A(m, n − 1)) m > 0 and n > 0.
Another example of two index recurrence is that of Stirling numbers, which correspond
to the number of partitions with p blocks of a set of n elements. Here, the recurrence is
much more simple than the previous one and Stirling numbers are studied in problem 16,
page 41.
calculation.
i i
i i
i i
i i
As closed forms are rarely known, the computational procedure aims at building an
iterative program where a one (or more) dimensional array is used to store the successive
values of the considered series. This approach is discussed and justified in chapter 4.
According to the principle adopted, the value of a cell is calculated from those already
present in the array. Then the order for filling the array is of prime importance and the evo-
lution of the calculation strongly depends on dependence relationships between elements.
For one dimension recurrences, it is generally simple (increasing or decreasing index val-
ues), but multiple index recurrences require more attention. The examples given hereafter
illustrate the proposed approach.
nbBT (0) = 1
X
n−1
nbBT (n) = nbBT (i) · nbBT (n − i − 1) n ⩾ 1.
i=0
i i
i i
i i
i i
Recurrence relations 13
After having checked (by enumeration) that nbBT (1) = 1 and nbBT (2) = 2, the next
value is:
2
X
nbBT (3) = nbBT (i) · nbBT (n − i − 1)
i=0
= nbBT (0) · nbBT (2) + nbBT (1) · nbBT (1) + nbBT (2) · nbBT (0)
= 2 + 1 + 2 = 5.
Figure 1.1, page 13, shows all the binary trees for n ∈ 0 .. 3.
• • •
• •
• • • • •
• • • • • •
• • • •
Fig. 1.1 – Vizualization of all binary trees of size 0, 1, 2 and 3, in respective numbers: 1, 1, 2 and 5.
1. constants
2. n ∈ N1 and n = . . .
3. variables
4. NBBT ∈ 0 .. n → N1
5. begin
6. NBBT [0] ← 1;
7. for i ranging 1 .. n do
8. NBBT [i] ← 0;
9. for j ranging 0 .. i − 1 do
10. NBBT [i] ← NBBT [i] + NBBT [j] · NBBT [i − j − 1]
11. end for
12. end for;
13. write(the number of binary trees having , n, nodes is , NBBT [n])
14. end
An alternate solution for this calculation is presented in problem 13, page 40.
i i
i i
i i
i i
1. constants
2. n ∈ N1 and n = . . .
3. variables
4. Facto ∈ N1
5. begin
6. Facto ← 1;
7. for i ranging 2 .. n do
8. Facto ← Facto · i
9. end for;
10. write(for n = , n, the value of n! is , Facto)
11. end
nbDel(0, j) = 1 0⩽j⩽m
nbDel(i, 0) =
1 1⩽i⩽n
nbDel(i, j − 1) + 1⩽i⩽n
nbDel(i, j) = nbDel(i − 1, j) + et .
nbDel(i − 1, j − 1) 1⩽j⩽m
In order to compute nbDEL(n, m) where m and n are two integers, the array
NBD[0 .. n, 0 .. m] is associated with nbDEL. The computation of NBD[i, j] (connected with
nbDEL(i, j), the general term of the recurrence), it is necessary to know: (i) the value of the
cell with the same row index and the column index immediately lower, (ii) the value of the
cell with the same column index and the row index immediately lower and (iii) the value
of the cell with row and column immediately lower. One may then fill NBD according to
rows (but columns or diagonals as well). After initializing row 0 with 1 (first term of the
recurrence), rows are filled by increasing values of index i (until n is reached): cell (i, 0)
is set to 1 (second term of the recurrence), then cells (i, 1) to (i, m) are filled using the last
term of the recurrence.
i i
i i
i i
i i
2. Determination of the dependence relationships that connect the left element and those
present in the right part of the general term of the recurrence. An evolution of the
calculation can then be deduced, which ensures that the computation of any element
of the array calls only on previously computed elements (possibly using initialization
terms of the recurrence).
3. Optionally, improvements of the computation, e.g. restriction of the calculation only to
necessary elements.
4. Production of the code.
As it can be seen in the example of factorial (cf. also problem 12, page 39), the tabular
structure may be replaced by a few appropriate scalar variables. Awareness is required
about the representation of numbers, especially in the presence of a recurrence whose val-
ues grow very quickly. It is advisable to work with a floating point representation rather
than with integers. For example, Ackerman numbers are such that A(3, n) = 2n+3 − 3
2
..
et A(4, n) = 22 − 3 (n + 3 occurrences of 2), and this number becomes rapidly huge
2
22
(A(4, 2) = 2 − 3 = 216 − 3 = 265 536 − 3). Last, the dependence relationship connecting left
and right hand sides may be nontrivial. Here again, we refer to Ackerman numbers and
the computation of A(6, 1) = A(5, 65533).
Proof by induction
When algorithms based on this type of reasoning are built, we frequently use the generic
term inductive reasoning, whose heart is induction. When reasoning on integers, it will be
mentioned if it the underlying induction is a simple or a strong one. They constitute the
two most often used variants in chapters 4 and 8.
Recursive program
An algorithm (as well as its coded form) is called recursive if it calls itself directly or by
means of other algorithms. The function Fact in page 16 illustrates the notion of recursive
algorithm, as well as numerous programs in chapters 4 and 8.
The “canonical” implementation of a recurrence is a recursive algorithm. However, it
will be seen in Chapter 4 that, for efficiency purposes, an iterative version will be preferred
where a tabular structure is filled (see preceding examples). This must not be confused
with the fact that a recursive program can be transformed (automatically but with the
explicit handling of a stack, see section 1.8) into an iterative one, which will have the same
behavior (especially the same performances) as the initial recursive program.
Nonetheless, there is a type of recursive program that can interestingly be transformed
into an iterative one: in the case of a terminal recursion. We will investigate this concept
with functions, but this would apply to procedures as well. A function F is terminal recur-
sive if it complies with the following pattern:
1. function F(. . .) result . . . pre
2. ...
i i
i i
i i
i i
3. begin
4. if C then
5. result V
6. else
7. result F(. . .)
8. end if
9. end
It is then possible to obtain an iterative program (whose execution is more efficient),
which is achievable by an smart compiler.
Example
The function hereafter:
1.4 Sets
1.4.1 Basic notations
We begin with a particular formula called pair which will be frequently used in the follow-
ing. A pair is composed by two expressions separated by a comma or by the symbol 7→.
i i
i i
i i
i i
Sets 17
For example, the formula x, y + 3 is a pair. This pair may also be denoted by x 7→ y + 3, or
even (x, y + 3). In this notation, the first element is called the origin and the second one is
called the end.
C=b (x, y + 3) associates the name C to the object (x, y + 3).
The relational operators = and ̸=, with their common meaning, are assumed available
to compare two mathematical objects.
i i
i i
i i
i i
dom(R) =
b {a | a ∈ E and ∃b · (b ∈ F and (a, b) ∈ R)}.
id(E) =
b {(a, b) | (a, b) ∈ E × E and a = b}.
i i
i i
i i
i i
Sets 19
T: Total
PI T PS P: Partial
I: Injective
S: Surjective
TI TS B: Bijective
TB
Fig. 1.2 – Inclusion diagram of the various types of function. A → B means that type A functions
are included in type B functions. From [1].
Let S be a relation between F and G, and R be a relation between E and F. The relation
R ◦ S is called the composition of R and S. It is defined by:
1.4.5.2 Functions
A function f from E to F is a relation where there is no pairs (a, b) and (a, c) such that b ̸= c.
One writes f ∈ E → F. In the remainder, several types of functions will be singled out. Let
f ∈ E → F.
1.4.5.3 Arrays
An array t is a total function from an interval i .. s to a set F. One denotes t ∈ i .. s → F.
When i belongs to the definition domain of the array, t[i] stands for the element having the
index i of t. The set notation may be used, but when the context allows the determination
of the bounds, the notation [t1 , . . . , tn ] may be used as a constant of type array. A sub-array
(sometimes called array slice) defined on the domain i .. s is denoted by t[i .. s]. Hence, if the
interval 3 .. 5 is included in the definition domain of t, t[3 .. 5] ← [6, −1, 2] is a valid assign-
ment. It is equivalent to t[3 .. 5] ← {3 7→ 6, 5 7→ 2, 4 7→ −1}. Besides, after the assignment,
codom(t[3 .. 5]) = {−1, 2, 6}, whereas dom(t[3 .. 5]) = {3, 4, 5}.
i i
i i
i i
i i
1.4.6 Bags
A bag (or multiset) of elements of the set E is a mathematical structure inside which the
number of occurrences of a given element is meaningful. A bag S over E may be considered
as a function s from E to N, such that, for v ∈ E, s(v) is the number of occurrences of v in S.
In order to ease writing, we adopt an ad hoc notation instead of the set-oriented one. The
notations used further and their set-oriented equivalent forms are listed hereafter.
Bags Sets Bags Sets
<
− ∈ ̸< ̸⊂
⧸
∅ ⊑ ⊆
−̇ − ̸⊑ ̸⊆
⊓ ∩ |. . .| card
⊔ ∪ bmin min
< ⊂ bmax max
bag(E) represents the set of finite bags of the finite set E and J. . .K is equivalent to the
notation {. . .} for sets defined in extension. Last, mult(v, B) is the function returning the
multiplicity (the number of occurrences) of v in the bag B.
i i
i i
i i
i i
Sets 21
functions for which set operators are available (dom, codom, etc.). The size (length) of
the string c is denoted by |c|. The concatenation (denoted by ·) allows to extend a string
by adding another string, as well as a character (which is converted into a string). If
c = c[1] . . . c[n] denotes a string, c = c[n] . . . c[1] is the mirror of c. From an algorith-
mic point of view, a string c used as an input parameter implicitly conveys its definition
domain (dom(c)). If c is a string defined over 1 .. n, the slice c[i .. s] is a string defined
over 1 .. s − i + 1 provided that i .. s ⊆ 1 .. n. The empty string ε (neutral element for the
concatenation) is defined over 1 .. 0. The declaration of a symbolic constant, a variable or
a parameter c of type string is written c ∈ string with an implicitly vocabulary made up
of letters, numbers and special symbols. Calling on a specific vocabulary Σ is achieved by
c ∈ string(Σ). The following example illustrates the use of strings, especially constants not
surrounded by quotation marks which require a special font.
1. constants
2. a =abcd /% symbolic constant of type string %/
3. variables
4. b ∈ string({a,b,c,d,1,2,3,4}) /% variable of type string over the vocabulary
Σ = {a,b,c,d,1,2,3,4} %/
5. begin
6. write(Odd(a)) ; /% the function Odd(x) (see the code) delivers a string made
of the elements of x having an odd index %/
7. read(b) ; write(Odd(b)) ;
8. b ← acbd · 1234 · a[3 .. 4] · a[1] ; /% example of a concatenation %/
9. write(Odd(b))
10. end
1. function Odd(x) result string pre
2. x ∈ string and y ∈ string
3. begin
4. y ← ε ; /% y becomes an empty string %/
5. for i ranging
dom(x) do
i
6. if 2 · ̸= i then
2
7. y ← y · x[i] /% extension of y by the next element of x having an odd
index %/
8. end if
9. end for;
10. result y
11. end
i i
i i
i i
i i
1.5 Graphs
Intuitively, a graph is a set of points, some of them being pairwise connected. It is a fairly
simple notion which allows for modeling numerous problems offering a great practical
interest, such as the search of the best route to reach a vacation home with a GPS device.
Graph theory is also the source of many mathematical and/or computer science com-
plex challenges such as the four color problem whose complete automated proof has been
carried out by the proof assistant Coq.
More simply, for us, the notion of graph originates numerous interesting problems
throughout this book.
Graph theory may be seen as an emanation of set theory (through the notion of binary
relation). However, the two theories have developed separately, thus often use divergent
vocabularies. In the following, directed graphs are first studied, then undirected ones. This
overview ends with the case of weighted (valued) graphs. Only finite graphs are taken into
consideration.
Example
The pair G defined by:
{a,b,c,d,e,f},
G=
{(a,b), (a,c), (a,f), (b,a), (b,c), (b,d), (c,e), (d,d), (d,f), (e,a), (e,f), (f,c)}
is a directed graph.
Figure 1.3 provides four possible representations for this graph. Schema (b), that has
the form of a square matrix, is often used as a computer representation.
An arrow that connects a vertex s with itself is called a loop over the vertex s; it writes
(s, s) with s ∈ N.
Let s be a vertex of a graph G. The out-degree (respectively in-degree) of s in G, de-
noted by d+G (s) (respectively dG (s)), is the number of arrows whose origin (respectively
−
Example
In the example of graph G in figure 1.3, page 23, we have d+ G (d) = 2, dG (d) = 2, SuccG (a) =
−
{b, c, f} and PredG (c) = {a, b, f}. It can be noticed that the arrow (d, d) is a loop (over d).
i i
i i
i i
i i
Graphs 23
b
c
0 1 1 0 0 1
1 0 1 1 0 0
a d 0 0 0 0 1 0
0 0 0 1 0 1
e 1 0 0 0 0 1
f 0 0 1 0 0 0
(a) (b)
a× ×a
a • b • c • f /
b× ×b
b • a • c • d/
c× ×c c • e /
d× ×d d • d • f /
e • a • f /
e× ×e • c /
f
f× ×f
(c) (d)
Fig. 1.3 – Four representations of a directed graph. Schema (a) is the (usual) sagittal representation,
(b) is the representation by an adjacency matrix, (c) is a bipartite representation and (d) is a repre-
sentation by lists of successors.
The graph G1 = ({a, b, d, f}, {(a, b), (b, a), (a, f), (b, d), (d, d), (d, f)}) is the graph induced
from G by the set of vertices {a, b, d, f}.
Examples of paths
In the graph of figure 1.3, page 23:
• ⟨a, b, a, c, e, a, b, d, d⟩ is a path. It is made up of the following list of arrows:
⟨(a, b), (b, a), (a, c), (c, e), (e, a), (a, b), (b, d), (d, d)⟩ and its length is 8. It is neither sim-
ple, nor elementary.
i i
i i
i i
i i
• ⟨a, b, c, e, a, b⟩ is not a simple path: the arrow (a, b) is browsed twice. ⟨a, b, d, f, c, e⟩ is
a Hamiltonian path.
Schema (a) in figure 1.4, page 24, shows an Eulerian path, namely ⟨d, b, c, a, b, e, d, c, e⟩.
Let G = ({s1 , . . . , sn }, V) be a graph and C = ⟨si1 , . . . , siq ⟩ be a path in G. C is a circuit in
G if and only if siq = si1 .
The terms elementary, simple, Hamiltonian and Eulerian can be easily transposed from
path to circuit.
Examples of circuits
In the graph of figure 1.3, page 23:
• ⟨a, b, a, b, d, d, f, c, e, a⟩ is a circuit since on the one hand it is a path and on the other
hand vertex a is both its origin and its extremity.
• ⟨c, e, f, c⟩ is an elementary circuit.
• ⟨a, b, a, c, e, a⟩ is a simple circuit, but it is not elementary.
• ⟨a, b, d, f, c, e, a⟩ is a Hamiltonian circuit.
In the graph (b) of figure 1.4, page 24, the path ⟨d, b, c, a, b, e, d, c, e, f, d⟩ is an Eulerian
circuit.
a a
b c b c
d e d e
(a) (b)
Fig. 1.4 – Two directed graphs. Graph (a) contains the Eulerian path ⟨d, b, c, a, b, e, d, c, e⟩, but no
Eulerian circuit. Graph (b) contains at least one Eulerian circuit (⟨d, b, c, a, b, e, d, c, e, f, d⟩).
i i
i i
i i
i i
Graphs 25
b b
a c a c
f d f d
e e
(a) (b)
In the schema given hereafter, graph (a) is represented in the plan, whereas (b) (the
grid “cylinder”) proposes a three-dimensional representation. They are isomorphic graphs
through the following bijection p:
p = {(H, c), (G, b), (J, a), (I, d), (C, g), (D, f), (F, e), (A, h)}.
c g
I H • •
A C
•h •f
d• b•
F D
•
J G • e
a
(a) (b)
Example
The pair G defined by:
{a,b,c,d,e,f},
G=
{a, b}, {a, e}, {a, f}, {b, c}, {b, d}, {d}, {c, e}, {a, f}, {e, f}, {d, f}
is an undirected graph. Figure 1.5 provides three possible representations for this graph.
The terms string and cycle for undirected graphs are the counterparts of those of path
and circuit in directed graphs. The qualifiers elementary, simple, Hamiltonian and Eulerian
apply to undirected graphs as well. The same applies to the definitions of a subgraph, a
graph induced by a set of vertices and a transitive closure.
i i
i i
i i
i i
a× ×a
b
c
b× ×b
0 1 1 0 1 1
1 0 1 1 0 0 c× ×c
a d fgk 1 1 0 0 1 1
d× ×d
0 1 0 1 0 1
e 1 0 1 0 0 1 e× ×e
f 1 0 1 1 1 0
f× ×f
Fig. 1.5 – Three representations of an undirected graph. Schema (a) is the usual representation; (b)
is the representation by an adjacency matrix (this matrix is always symmetric); (c) is a bipartite
representation.
9.0
b 3.4
0
1.6
7
3. 3.7 ∞ 3.4 9.0 ∞ ∞
a 5.0 −2.7 ∞ ∞ ∞ ∞ 5.0 ∞
.0
7.0 d
12
∞ ∞ ∞ −2.7 ∞ 8.3
−
4.
2
e 7.0 ∞ ∞ ∞ ∞ −1.0
f −1.0 ∞ ∞ −12.0 ∞ ∞ ∞
8.3
(a) (b)
Fig. 1.6 – Two representations of a weighted directed graph. Schema (a) is the usual sagittal rep-
resentation, (b) is the matrix representation where absent arrows are provided with a conventional
symbol (here ∞).
An undirected weighted graph is a graph in which every edge is provided with an at-
tribute.
More formally, an undirected weighted graph G is a triple (N, V, P) such that (N, V) is an
undirected graph and P is total function from V to a set E of values.
i i
i i
i i
i i
Trees 27
1.6 Trees
Beyond their intrinsic interest (compiling, automated proofs, natural language processing,
etc.), trees are at the root of efficient representations for a wide range of data structures
(sets, queues, priority queues, flexible arrays, etc. – see [22, 9]. Despite the use of numerous
types of trees throughout this book (see for instance recursion trees, Chapter 5, page 197),
here we restrict ourselves to binary and ternary trees. There are several ways to define this
notion. Using graph theory is one of them. A binary or ternary tree is defined as a specific
graph (an undirected connected loopless graph where a particular vertex – the root – is
i i
i i
i i
i i
1. constants
2. ab = {/} ∪ {(l, n, r) | l ∈ ab and n ∈ N and r ∈ ab}
3. variables
4. t ∈ ab
5. begin
6. t ← /;
7. t ← (((/, 0, /), 1, /), 3, (((/, 4, /), 5, (/, 6, /)), 7, (/, 9, /)));
8. write(t.l)
9. end
ab is the set of all finite binary trees of integers. It is defined (line 2 in the code) as the union
of two sets: {/} (the empty tree) and the set of triples (l, n, r), where l and r are binary trees
(respectively the left subtree and the right subtree) and n an integer. Line 4, t is a variable
defined as one of the elements the set ab. The instruction in line 6 assigns the empty tree
to t. That of next line assigns the tree of schema (a) in figure 1.7 to t. Line 8 displays (on a
regular terminal) the left subtree of t (denoted by t.l).
v = 5?
3 < = >
1 7 v = 3? P v = 9?
< = > < = >
0 5 9
A P A v = 7? P A
4 6 < = >
(a) A P A
(b)
Fig. 1.7 – Schema (a): a binary tree and Schema (b) : a (decision) ternary tree (A: absent P: present).
In a binary tree, a leaf is a childless node (without any successor); a simple point is a
node with a single child. The height of a binary tree is the distance (i.e. the number of
edges) between the root and the furthest leaf. The weight of a binary tree is the number of
its nodes/vertices. Among all the possible simple “paths” in a nonempty binary tree, there
is (at least) one with maximum length. This length is called the diameter. A diameter does
not necessarily include the root (see problem 94, page 431).
3 Even if, for convenience, they can be at the same place in the schemas, it is important to distinguish between
the name of a vertex or a node, which is an identifier, and the label, which is any type of value. The inductive
definition of trees allows for omitting the name of the node.
i i
i i
i i
i i
Trees 29
In the forthcoming schemas, “paths” connecting grey vertices are materialized by bold
arrows. In schema (a) (respectively (b)), the considered “path” is made of 5 (respectively 7)
arrows, so its length is 5 (respectively 7). The height of these two trees is 4, their diameter
is 7. The bold “path” in schema (b) is a diameter.
(a) (b)
Most of the above definitions can easily be transposed to ternary trees. Among par-
ticular binary trees, let us cite skinny trees, complete trees, full trees and perfect trees. A
skinny tree is a tree where no vertex has two children. A complete tree is a tree does not
contain any simple point. Trees (a) and (b) in figure 1.8, page 29, are complete trees. This
is not the case for the three others in this figure. A full tree is a tree where all leaves are
located at the same height. It is the case for tree (b) in figure 1.8, page 29. It is the only tree
of this type in this figure. A perfect tree is such that: (i) all leaves are located on the last
two levels, i.e. the lowest levels, (ii) when the (perfect) tree is not a full one, i.e. when the
leaves are spread over two levels, the leaves of the lowest level are left-gathered (iii) there
is at most one simple point and it is located on the penultimate level. Schema (c) in fig-
ure 1.8 provides an example of a perfect tree. Tree (b) is also a specific perfect tree (because
of the absence of a simple point). On the contrary, trees (d) and (e) in figure 1.8, page 29,
are not perfect trees, the first one because it possesses two simple points, the second one
because the leaves of the last level are left-gathered. Tree (a) is not a perfect tree. It is easy
– and often useful – to give an inductive definition of the notions studied in this section
(see problem 94, page 431). We draw the attention of the reader on the fact that definitions
concerning trees are far from consensual.
(a)
(b)
i i
i i
i i
i i
A particular type of binary tree is worthy of a special attention, namely binary search
trees (called bst for short). An bst is either an empty tree, or a binary tree whose nodes
contain numeric values, and such that, if v is its root, its left (respectively right) subtree is
a bst containing, if nonempty, values lower (respectively greater) than v. Tree (a) in figure
1.7, page 28, is a bst.
At many places, we make use of particular trees called “decision trees”. A decision tree
allows for structuring a classification (see figure 8.1, page 421), for representing the various
executions of an algorithm (see figure 90, page 427), sometimes with aim of computing its
complexity (see figure 96, page 433). Usually, a decision tree appears as a binary tree where
each node is a predicate and each branch a possible answer (true or false). The predicate
can be replaced by a multiple choice question where the number of branches of each node
is that of the answers to the considered question. Tree (b) in figure 1.7, page 28, is a ternary
tree for deciding whether or not a given value v belongs to the set {3, 5, 7, 9}. In this tree,
each node is intended for comparing v with the value present in the considered node.
Leaves answer the question associated with the decision tree (P: the numeric value present
in the leaf belongs to {3, 5, 7, 9}, A : the numeric value present in the leaf does not appear in
{3, 5, 7, 9} – it is absent.)
i i
i i
i i
i i
Priority queues 31
• HeadPQ(q): function which delivers the priority element (the head) of the queue q. The
precondition of this function is that the queue involves at least one element.
• RemovePQ(q): procedure that removes the priority element (the head of the queue)
from the queue q. This procedure also has as a precondition that q contains at least one
element.
• AddPQ(q, e): procedure which inserts the element e in the queue q (this element is
assumed to convey its own priority).
• IsEmptyPQ(q): Boolean function which returns true if and only if the priority q is
empty.
Sometimes, it is necessary to enrich this set of operations with additional ones, such as
that consisting in modifying the priority of a given element of the queue (see for instance
problem 78, page 345). The size of the queue q is denoted by |q|.
1.7.2 Implementations
Several more or less sophisticated implementations of priority queues are reported in the
literature. Let us remind two of them for queues with n elements:
• Sorted lists for which the insertion operation is in O(n), the (re)initialization operation
is in Θ(n) or Θ(1) depending on the fact that space is recovered or not. Other operations
are in Θ(1). This type of solution is convenient only if n is small.
• Heaps. From a structural point of view, a heap is a perfect binary tree (leaves are located
on – at most – two consecutive levels and those of the last level are left-gathered). As
to the content, a heap is such that the value of any node is less than (or equal to) that
of all its descendants.
An important characteristic is that a heap can beneficially be represented by an array T
such that, for a given i, T [2i] and T [2i + 1], if they do exist, are the children of T [i].
The following schema (a) shows a heap defined on R+ according to its arborescent
form. Schema (b) is the array representation of schema (a).
2.3
4.0 5.6 1 2 3 4 5 5 7 8 9 10
T 2.3 4.0 5.6 6.1 7.9 7.3 9.8 9.5 8.0 8.3
6.1 7.9 7.3 9.8
(a) (b)
In terms of visited vertices (or evaluated conditions), the cost of the operation Delete
is in Θ(log2 (n)) and that of Insert is in O(log2 (n)). Other operations require a constant
time.
i i
i i
i i
i i
As for priority queues, it is sometimes useful to enrich this set of operations or to mod-
ify some of them.
A LIFO queue (hereafter called a stack) is a data structure designed to manage items
according to the following strategy: the element to be removed is the last one that was
introduced (hence the name LIFO: Last In First Out). Operations used to deal with stacks
are:
• initStack(S) procedure that empties the stack S,
• topStack(S) function that delivers the top of the stack S without modifying this latter
(precondition: the stack is not empty),
• Stack(S, v) procedure that puts the integer value v on top of the stack S,
• unStack(S) procedure that removes the top of the stack S (precondition: the stack is not
empty),
i i
i i
i i
i i
Problems 33
1.9 Problems
Problem 1. Is a neutral element unique? ◦ •
Let S be a set provided with an internal operator ⊕. Let u ∈ S be a left neutral element
for ⊕, i.e.:
∀x · (x ∈ S ⇒ u ⊕ x = x).
Let v be a right neutral element for ⊕.
Question 1. Prove in a direct way that if ⊕ is a commutative operator, one has u = v. 1-Q1
Question 2. Prove this property by contradiction without calling on the commutativity 1-Q2
property of ⊕.
The solution is on page 46.
The interest of this problem is to demonstrate the same property by means of both a proof by
contradiction and a proof by induction.
Let E be a finite set with a partial order relation denoted by ⪯ and F be a strict nonempty
subset of E. A strict antecedent of x is an element y distinct from x such that y ⪯ x. An
element m of F is said to be minimum if m has no strict antecedent in F.
Question 1. Prove by contradiction that F has at least one minimum element. 2-Q1
Question 2. Demonstrate by induction that F has at least one minimum element. 2-Q2
Question 3. One considers the set E made of pairs of integers and the partial order 2-Q3
relation ⪯ defined by:
b a ⩽ c and b ⩽ d.
(a, b) ⪯ (c, d) =
Let F(⊂ E) = {(a, b) | a ∈ 1..3 and b ∈ 1..2 and a ̸= b}. Enumerate the minimum elements
of F.
The solution is on page 46.
In this problem, two results about the comparison of values of factorials and exponentials
are established. The first one constitutes a result useful for the order of two related classes of
complexity (see Chapter 2).
i i
i i
i i
i i
∀n · (n ∈ N1 ⇒ n! ⩾ 2n−1 ).
In this problem, we first validate a new schema for the proof by simple induction. Then, it is
applied to a property about the construction of an amount of money. We also ask for making
the demonstration with the proof by regular simple induction. It is the possible to decide
whether one method is more “convenient” than the other one, noticing that the result holds
for this problem only.
4-Q1 Question 1. Prove that the following alternate pattern for simple induction proof
holds:
4-Q2 Question 2. Use this pattern to prove that any amount of money n over five cents can
be obtained with two and seven cent coins.
4-Q3 Question 3. Prove the same result by simple induction as given in section 1.1.3.1, page
4.
4-Q4 Question 4. Which is the maximum number of seven cent coins used in each of these
patterns?
4-Q5 Question 5. In your opinion, which of these two proofs is easier to perform?
The solution is on page 47.
In this problem, it is proven (by simple induction) that the closed form of the recurrence rela-
tion proposed for Catalan numbers is valid. An upper bound of the value of the nth Catalan
number is also proposed.
i i
i i
i i
i i
Problems 35
Catalan numbers have been previously addressed and defined by the following recur-
rence relation (see page 11):
Cat(1) = 1
4n − 6
Cat(n) = · Cat(n − 1) n > 1.
n
Question 1. Prove by simple induction that, for any positive integer n, the closed form 5-Q1
of this recurrence relation is (see page 11):
(2n − 2)!
Cat(n) = .
(n − 1)! n!
Question 2. Prove by simple induction that, for any positive integer n, one can write: 5-Q2
4n−1
Cat(n) ⩽ .
n
The solution is on page 48.
This problem is intended for drawing the attention on the compliance with the hypotheses
so as to perform a valid proof by induction. Two examples are successively proposed, where
the proposition P to prove is obviously false. It is interesting to point out the fallacy in the
reasoning suggested to make the proof.
First case
We envisage to prove the following property P1 :
The reasoning is performed on the maximum of the two numbers a and b, denoted by
max(a, b).
i i
i i
i i
i i
Second case
We consider the following property P2 :
n arbitrary points of a plane are aligned.
The induction relates to the number of points n.
Initialization For n = 2, proposition P2 holds, since two points are aligned.
Induction Suppose that property P2 holds for p points (induction hypothesis). Let us
prove that then the (p + 1) points A1 , A2 , A3 , . . . , Ap+1 are aligned. According to the
induction hypothesis, the first p points A1 , A2 , A3 , . . . , Ap are aligned on a straight
line (d1 ) and the last p points A2 , A3 , . . . , Ap+1 are aligned on a straight line (d2 ).
These two straight lines (d1 ) et (d2 ) have the points A2 and A3 in common and they
are one and the same. One has (d1 ) = (d2 ) = (A2 A3 ) and the points A1 , A2 , A3 , . . . ,
Ap , Ap+1 are aligned.
Conclusion Proposition P2 holds for any number of points strictly greater than 1.
Following the previous one, this problem aims at pointing out a flaw in a reasoning by in-
duction. However, here, the formula to demonstrate is right and a direct appropriate proof is
expected.
It is proposed to demonstrate by simple induction that, for any strictly positive integer
n, one has: s r q p
n = 1 + (n − 1) 1 + n 1 + (n + 1) 1 + (n + 2) . . .
To start, it is assumed that the above expression makes sense, i.e. that it converges when
n increases indefinitely (which is true, as we will see later).
The proof by strong induction is performed as follows:
Initialization For n = 1, the right part of the formula becomes:
q p
1 + 0 1 + 1(. . .) = 1
i i
i i
i i
i i
Problems 37
We have demonstrated that the induction hypothesis entails the formula to be proven.
Question 1. Where is the flaw in the above reasoning? 7-Q1
In section 1.1.6, page 9, a two indexes recurrence proof pattern was proposed. The objective of
this problem is to validate another one.
i i
i i
i i
i i
Problem 9. Divisibility by 7 ◦ •
This problem is devoted to the proof by induction of a property of the elements of a series of
integers given under its closed form.
9-Q1 Question 1. Prove by simple induction that whenever A(n, p) is (respectively is not) a
multiple of 7, A(n + 1, p) is (respectively is not) a multiple of 7.
9-Q2 Question 2. What can be said about the divisibility (by 7) of the series of numbers
A(n, 0), A(n, 1), A(n, 2) and A(n, 3)?
The solution is on page 51.
Here, a series of numbers is under consideration. Two properties are proven, one by simple
induction and the second one “directly”. It turns out that the proof by induction does not
appear to be the easiest one.
A(1) = 1
n2 − 3n + 1
A(n) = A(n − 1) + n ⩾ 2.
(n − 1)2 · n2
10 - Q 1 Question 1. Prove by simple induction that the closed form of numbers A(n) is (n2 −
2
n + 1)/n for any integer n ⩾ 1. What can be deduced as to the nature of these numbers?
10 - Q 2 Question 2. Prove that for any integer n > 2, A(n) lies in the open interval A(2) .. A(1).
The solution is on page 51.
In this problem, one tries to build an infinite sequence of binary numbers which equals that
obtained by taking only one in three term, as well as that obtained by keeping the two in three
remaining terms. Of course, the two trivial sequences made solely of 0’s or 1’s are discarded.
Let S = ⟨s1 , s2 , . . . , sn , . . .⟩ be the binary sequence other than the trivial one composed
solely of 0’s (respectively 1’s). One denotes by S/3 the sequence built by taking one in three
element of S as follows: S/3 = ⟨s3 , s6 , . . . , s3n , . . .⟩. One denotes by S − S/3 the sequence
i i
i i
i i
i i
Problems 39
Question 1. Propose a reasoning by induction which allows the construction of the two 11 - Q 1
sequence S1 and S2 (other than ⟨0, 0, 0, . . .⟩ and ⟨1, 1, 1, . . .⟩) such that S = S/3 = S − S/3.
They are called the “lizard sequence” (see [11]).
Question 2. Give their first 20 elements. 11 - Q 2
The solution is on page 52.
This problem highlights the fact that even if a closed form of a recurrence formula is known,
it can hardly be used in an algorithm.
Let us remind that Fibonacci sequence of integer numbers is defined (see page 10) by
the following recurrence:
F(1) = 1
F(2) = 1
F(n) = F(n − 1) + F(n − 2) n > 2.
" √ !n √ !n #
1 1+ 5 1− 5
F(n) = √ − n ⩾ 1.
5 2 2
Question 1. Explain why the above formula is not used to compute F(n) for a given 12 - Q 1
n.
Question 2. Propose an iterative algorithm returning the nth Fibonacci number. 12 - Q 2
Remark
Several other ways for the computation of Fibonacci numbers are discussed in problem 89,
page 425.
The solution is on page 53.
i i
i i
i i
i i
This problem is a complement to the example given page 12. Its objective is to design a variant
of the algorithm computing the number of binary trees possessing n elements on the basis of
a closed form, therefore expected to be more efficient.
It has been established that the number of binary trees with n nodes is given by the
following recurrence:
nbBT (0) = 1
X
n−1
nbBT (n) = nbBT (i) · nbBT (n − i − 1) n ⩾ 1.
i=0
This problem has a twofold interest. On the one hand, a practical way for the calculation of
the elements of a two index recurrence is studied. On the other hand, a closed form is proposed
and proven by means of a new pattern for two index proof by induction.
a(0, j) = j + 1 j⩾0
a(i, 0) = 2 · a(i − 1, 0) + a(i − 1, 1) i>0
a(i, j) = a(i − 1, j − 1) + 2 · a(i − 1, j) + a(i − 1, j + 1) i > 0 and j > 0.
14 - Q 1 Question 1. Give the value a(3, 2). Propose a tabular structure and describe the evolu-
tion of the calculation of a(i, j) (i, j ⩾ 0).
14 - Q 2 Question 2. Write an iterative program which computes the value a(n, m) for a given
pair (n, m).
14 - Q 3 Question 3. Propose a closed form for a(i, j) and prove its validity by induction. What
is the interest of this expression from an algorithmic point of view?
The solution is on page 54.
i i
i i
i i
i i
Problems 41
One considers possible moves of the knight (in the spirit of the chessgame) under constraint
between the two extreme points of a board and their enumeration by means of a recurrence
formula.
One is interested in the paths of the knight (according to chessgame) over a board with
n > 4 rows and m > 3 columns. One wants to know the number of distinct ways to go
from the square (1, 1) (departure) to the square (n, m) (arrival). By convention, (i, j) stands
for the square of the board located on row i and column j. In contrast to chessgame where
the knight has eight possible moves (except if it would go outside the board), it is imposed
that the knight moves only in order to increase the column index (the second one), as
shown in figure 1.9.
7
ZnZ0Z0Z0Z
6
0Z0M0Z0Z0
5
Z0M0Z0M0Z
4
0Z0Z0Z0M0
3
Z0Z0ZnZ0Z
2
0Z0Z0Z0M0
1
Z0Z0Z0M0Z
1 2 3 4 5 6 7 8 9
Fig. 1.9 – The knight located in (7, 2) (respectively (3, 6)), plotted in black, can move to the two
(respectively four) positions, plotted in white.
Question 1. Let nbRout(i, j) be the count of distinct paths starting in (1, 1) and ending 15 - Q 1
in (i, j. Give the complete recurrence for calculating nbRout(i, j).
Question 2. Write the iterative algorithm derived from this formula for any given pair 15 - Q 2
of integers (n, m). Give the value of nbRout(5, 7).
The solution is on page 56.
The main goal of this problem is to establish the recurrence formula defining Stirling numbers.
We denote by S(p, n) the number of partitions with p blocks of a set having n elements.
The values S(p, n) are called Stirling numbers. For example, {{a, c}, {b, d}} and {{b}, {a, c, d}}
are two out of the seven partitions with two blocks of the four element set {a, b, c, d} .
i i
i i
i i
i i
16 - Q 1 Question 1. Give all the partitions with one, two, three and four blocks of the latter
four element set (a block cannot be empty).
16 - Q 2 Question 2. What is the recurrence defining S(p, n)?
16 - Q 3 Question 3. Propose a progression of the calculation of S(p, n), then develop the cor-
responding iterative algorithm.
16 - Q 4 Question 4. Give the values of S(p, n) for 1 ⩽ p ⩽ 5 and 1 ⩽ n ⩽ 7.
The solution is on page 58.
The target of this problem is twofold: establishing a recurrence relation and optimizing its
algorithmic computation by obviating some of the cells of the underlying array.
17 - Q 1 Question 1. Give two ways for climbing up the 12 steps (not more, not less) of a stair-
case using exactly three jumps of a1 = 2 or a2 = 3 or a3 = 5 steps.
17 - Q 2 Question 2. Give the recurrence relation for the calculation of nbCL(s, m).
17 - Q 3 Question 3. Propose a progression for this calculation, then the iterative associated
program.
17 - Q 4 Question 4. Give the values nbCL(s, m) for m ⩽ 12, s ⩽ 6, n = 2, a1 = 2, a2 = 5.
17 - Q 5 Question 5. In the previous example, it can be noticed that some portions of the array
related to nbCL are filled in with 0’s. Explain why and suggest an improvement of the
algorithm proposed in question 3.
The solution is on page 59.
This problem introduces the Patagon game, where a single player aims at accumulating the
highest gain. One searches to count the “reasonable” ways of playing, which both comply
with the rule of the game and are likely to lead to the maximum gain. problem 146, page 687
is devoted to the determination of a way of playing according to which the highest gain is
reached.
i i
i i
i i
i i
Problems 43
When playing the Patagon game, the player is in front of n objects, arranged in line. Each
object possesses a given visible value. The player can take as many objects as he wants so
as to accumulate a total value as large as possible. Obviously, there is a constraint (and
only one): the player cannot take two of the objects of the initial configuration located side
by side.
Question 1. What is the best choice with the following line of objects (where an object 18 - Q 1
is represented by its value) ?
23 41 40 21 42 24
Question 2. The choice of the player is assumed to be represented by its n-sized char- 18 - Q 2
acteristic vector (1 in position i if the ith object is taken, 0 otherwise). In the previous
example, [0, 1, 0, 1, 0, 1] represents a game yielding 0 + 41 + 0 + 21 + 0 + 24 = 86 Patagon
currency units. Prove that, for n > 1, there are strictly less than 2n distinct ways of playing.
Question 3. Some ways of playing are, for sure, worse than others. For example, 18 - Q 3
[0, 1, 0, 1, 0, 0] (yielding 62) is worse than [0, 1, 0, 1, 0, 1] (paying 86). A way of playing is said
to be reasonable, if it does not leave objects that could have been taken (while obeying the
rule of the game). Hence, playing [0, 1, 0, 1, 0, 1] is reasonable, whereas playing [0, 1, 0, 0, 0, 1]
or [0, 1, 0, 1, 0, 0] is not. How can the reasonable ways of playing be characterized?
Question 4. The objective of the remainder of the problem is to count the number of 18 - Q 4
reasonable ways of playing, in other words, the number of n sized binary vectors related to
all reasonable ways of playing. For a n sized game, nbRWP0 (n) (respectively nbRWP1 (n))
denotes the number of reasonable ways of playing where the nth location of the vector is 0
(respectively 1). The total number of reasonable ways of playing, nbRWP(n), is obviously
the sum nbRWP0 (n) + nbRWP1 (n).
Prove that:
nbRWP0 (1) = 0, nbRWP1 (1) = nbRWP0 (2) = nbRWP1 (2) = nbRWP0 (3) =
nbRWP1 (3) = 1
and that for n > 3:
nbRWP0 (n) = nbRWP1 (n − 1)
nbRWP1 (n) = nbRWP1 (n − 2) + nbRWP1 (n − 3).
Question 6. Give the values of nbRWP0 (n), nbRWP1 (n) and nbRWP(n) for n varying 18 - Q 6
from 1 to 15. Independently of nbRWP0 , which relation ties nbRWP and nbRWP1 ? Would
it have been possible to establish it before?
Question 7. Give the algorithm calculating nbRWP(n) for a given value n. 18 - Q 7
i i
i i
i i
i i
In this problem, one is interested in the number nbWW of ways to win in a game where
tokens located in two stacks are added or removed. A property of nbWW is pointed out and
proven by induction.
Let us consider a game where two stacks P and Q containing respectively p and q
tokens (p, q > 1) are available. The goal is to reach one of the configurations (p = 0, q = 1)
or (p = 1, q = 0), called winning state later. The evolution of the stacks obeys the following
procedure: two tokens are removed from P (respectively Q), one is thrown away and the
other is added to Q (respectively P).
Example. (p = 4, q = 6) −→ (p = 2, q = 7) or (p = 5, q = 4).
We want to know the number nfg(p, q) of distinct ways allowing to reach one of the two
winning states starting from a configuration where stack P contains p tokens and stack Q
has q tokens.
19 - Q 1 Question 1. Give the recurrence expression of nbWW(p, q).
19 - Q 2 Question 2. Propose a tabular structure associated with the calculation of nbWWg as
well as the progression of its filling.
19 - Q 3 Question 3. Deduce an iterative algorithm for the computation of the number of dis-
tinct ways allowing to reach one of the two winning states of the game.
19 - Q 4 Question 4. Use this algorithm to compute nbWW(4, 2).
19 - Q 5 Question 5. Prove that any element nbWW(i, j), such that |i − j| is a multiple of 3, is
equal to 0 (excepted nbWW(0, 0), which makes no sense).
The solution is on page 63.
This problem raises the (apparently) simple problem of enumerating the distinct ways for
forming one euro with yellow coins. It is shown that the intuitive approach based on a single
index recurrence is not appropriate and that it is necessary to call on a double index one. The
approach developed here has a follow up in problem 148, page 689.
One wants to know the number of distinct ways for forming the amount of one euro
with yellow coins, in other words, using the six following coins of the European currency
system: 1, 2, 5, 10, 20 and 50 cents.
20 - Q 1 Question 1. Let us first reason in order to form any amount ranging from one to nine
cents. Obviously, there is a single solution to form the amount of one cent. For two cents,
one can take a single coin (two cents), or a one cent coin and one cent remains to be formed.
To form the amount s of three or four cents, one takes a one cent coin and the amount (s−1)
remains to be formed, or one takes a two cent coin and the amount (s − 2) remains to be
formed. To form five cents, one takes a single coin (five cents), or a one cent coin and the
amount of four cents remains to be formed, or a two cent coin and the amount of three
cents remains to be formed. Last, to form the amount s from six to nine cents, one takes
a five cent coin and the amount (s − 5) remains to be formed, or a one cent coin and the
amount (s − 1) remains to be formed, or a two cent coin and the amount (s − 2) remains
i i
i i
i i
i i
Problems 45
to be formed. One deduces the following recurrence defining nbWF1E(1), the number of
ways for forming one euro:
nbWF1E(1) = 1
nbWF1E(2) = 1 + nbWF1E(1)
nbWF1E(i) = nbWF1E(i − 1) + nbWF1E(i − 2) 3⩽i⩽4
nbWF1E(5) = 1 + nbWF1E(4) + nbWF1E(3)
nbWF1E(i) = nbWF1E(i − 5) + nbWF1E(i − 2) + nbWF1E(i − 1) 6 ⩽ i ⩽ 9.
Question 4. Write the iterative program performing the computation of the number of 20 - Q 4
ways for forming one euro with yellow coins.
Question 5. What is the number of ways for forming one euro with yellow coins? 20 - Q 5
Question 6. Prove that the number of ways for forming the amount m with all yellow 20 - Q 6
coins grows with m.
The solution is on page 65.
We define the shuffle operation of two words and want to determine the number of possible
shuffles of two given words. We also want to decide whether a word can be the result of the
shuffle of two others.
Let us take three words: u of length m, v of length n and w of length (m + n). The word
w is said to be a shuffle of the two words u and v if it obtained in shuffling the letters of
u and v while preserving their order of the letters in u and v. For example, with u = nose
and v = lips, the word w = nolispse is a shuffle of u and v, but not the word nlsoipes.
Question 1. Give a recurrence relation for the calculation of nbShuf(m, n) the number 21 - Q 1
of distinct shuffles that can be obtained from u and v, or more generally from any pair of
words of respective lengths m and n. What is the value of nbShuf(5, 4)?
Question 2. Prove by induction that nbShuf(m, n) = (m + n)!/(m! · n!). How could 21 - Q 2
we have found this result directly?
Question 3. Write an algorithme which decides if a word w is a shuffle of the words u 21 - Q 3
and v. Apply it to u = abc, v = db and w = dabbc.
The solution is on page 68.
i i
i i
i i
i i
1.10 Solutions
Answers to problem 1. Is a neutral element unique ? The problem is on page 33.
1-A1 Answer 1. Since the operator ⊕ is commutative, one has:
∀x · (x ∈ S ⇒ u ⊕ x = x ⊕ u).
are stored in k boxes, at least one box contains two (or more) objects.
i i
i i
i i
i i
Solutions 47
The element (1, 2) has no strict antecedent and is therefore a minimum of F. The same holds
for (2, 1). F possesses two minimum elements.
Conclusion The inequality holds for n = 1 as well as for (n + 1) if it does for n. It can be
deduced that n! ⩾ 2n−1 for any strictly positive integer n.
Answer 2. It is easy to observe that the inequality n! ⩾ n2n does not hold until n = 8 3-A2
since 8! = 40320 and 216 = 65536. On the contrary, it holds for n = 9 since 9! = 362880 and
218 = 262144.
We now prove that for n ⩾ 9, if n! > 22n then (n + 1)! > 22n+2 . One has:
(n + 1)!
= definition of a factorial
(n + 1) · n!
> induction hypothesis
(n + 1) · 22n
> n⩾9
4 · 22n
= property of the exponential
22n+2 .
It can be deduced that the proposed property (n! > 22n ) for any integer n strictly greater
than 8.
Answer 1. The proof of validity of this pattern is made in a way similar to the one used 4-A1
in section 1.1.3.1, page 4.
i i
i i
i i
i i
4-A2 Answer 2. First, this pattern is used to demonstrate the property claiming that any
amount of money n (strictly) greater than five cents may be obtained with coins of two
and seven cents.
Initialization We take n0 = 6 since it is impossible to form the amount of five cents with
the two considered coins. It is possible to obtain the amount of six (respectively seven)
cents with three two cent coins (respectively one seven cent coin).
Induction Suppose that the property holds for any amount n ⩾ 6 (induction hypothesis).
To form the amount (n + 2), it is sufficient to add one two cent coin to the combina-
tion of coins serving for the amount n (which does exist according to the induction
hypothesis).
Conclusion The property holds for any amount n ⩾ 6.
4-A3 Answer 3. We now proceed to the demonstration using the “regular” proof by simple
induction (see section 1.1.3.1, page 4).
Initialization The amount of six cents is obtained with three two cent coins.
Induction Assume that the property holds for a given value of n (n ⩾ 6). Two exclusive
cases occur:
• The amount n has been obtained with at least one seven cent coin. This coin is
discarded, four two cent coins are added and the amount n + 1 is thus formed.
• The amount n has been obtained only with two cent coins. Three of these coins are
removed and one seven cent coin is added, which makes the amount n + 1.
Conclusion The amount of six cents can be formed with two cent coins and (no) seven cent
coins and if it is possible to form the amount n, we know how to form the amount
(n + 1) with these coins. Hence, it is possible to form any amount strictly over five
cents with two and seven cent coins.
4-A4 Answer 4. According to the first pattern, only one seven cent coin can appear (pre-
cisely that used to form the amount of seven cents), since then only two cent coins are
added. It is the same with the second pattern, since as soon as a seven cent coin appears, it
is removed.
4-A5 Answer 5. The first (respectively second) pattern requires to prove the validity of the
property for n0 and n0 + 1 (respectively n0 ). On the contrary, in this example, the proof of
the induction step is shorter with the first schema where no distinction between situations
has to be made.
i i
i i
i i
i i
Solutions 49
4n − 2 (2n − 2)!
·
n + 1 (n − 1)! · n!
= arithmetics
(4n − 2) · (2n − 2)!
(n − 1)! · (n + 1)!
= numerator and denominator multiplied by n
(4n2 − 2n) · (2n − 2)!
n! · (n + 1)!
= arithmetics
(2n)!
n! · (n + 1)!
this latter expression being nothing but the closed form for (n + 1).
Conclusion The closed form holds for n = 1, and if it holds for n ⩾ 1, it does for (n + 1).
It can be concluded that the closed form is suitable for any positive value n.
Remark
Equality occurs only for n = 1. Beyond, 4n−1 /n is a strict upper bound for Cat(n). Hence,
one has: Cat(2) = 1 < 41 /2 (= 2), Cat(3) = 2 < 42 /3 (≈ 5.33), Cat(5) = 14 < 44 /5 (= 51.2).
i i
i i
i i
i i
As a matter of fact, this line may produce negative numbers (when a or b equals 0): we are
no longer in the scope of property P1 applying to integers. Take the numbers a = 0 and
b = 1. One has: a − 1 = −1 and b − 1 = 0. Their maximum is 0 whereas these two numbers
are both equal to 0 (and therefore equal).
6-A2 Answer 2. The fallacy lies in the following sentence:
The two straight lines (d1 ) and (d2 ) have the two points A2 and A3 in common.
So that this claim is true, the number of points must be strictly over 2 (p ⩾ 3), in order to
be able to use points A2 and A3 . The induction hypothesis must start with p > 2. However,
for p = 2, the straight line (d1 ) is (A1 A2 ) and the straight line (d2 ) is (A2 A3 ), and they have
only one point (A2 ) in common and generally they are not collinear.
7-A1 Answer 1. The flaw appears when writing (implicitly for any n ⩾ 2):
2
((n − 1) − 1)/(n − 2) = n.
As a matter of fact, a division by (n − 2) is performed, but this denominator is equal to 0
when n = 2, and the division is illegal.
7-A2 Answer 2. For any n ⩾ 1, the following identity holds:
p
n = 1 + (n − 1)(n + 1).
p
In the right member, let us replace (n + 1) by 1 + n(n + 2), it yields:
q p
n = 1 + (n − 1) 1 + n(n + 2).
p
Now, let us replace (n + 2) by 1 + (n + 1)(n + 3), we get:
r q p
n = 1 + (n − 1) 1 + n 1 + (n + 1)(n + 3).
The substitution mechanism can be repeated for (n + 3), then (n + 4) and so on, and this
results in the proposed formula, namely:
s r q p
n = 1 + (n − 1) 1 + n 1 + (n + 1) 1 + (n + 2) . . . .
We use the total order relation over N1 2 given in section 1.1.6, page 9, namely:
i i
i i
i i
i i
Solutions 51
Answer 1. Let A(n, p) = q, where q is a nonnegative integer, then we have 32n = 9-A1
2n−p + q. By definition:
A(n + 1, p) = 32(n+1) − 2(n+1)−p = 9 · 32n − 2 · 2n−p .
Replacing 32n by (2n−p + q) in the right part of the preceding expression, we get:
A(n + 1, p) = 9 · (2n−p + q) − 2 · 2n−p = 7 · 2n−p + 9 · q.
This latter expression is likely to produce a multiple of 7 only if q (indeed A(n, p)) is itself
a multiple of’7. Thus, we have:
A(n, p) = q = 7k and A(n + 1, p) = 7 · (2n−p + 9k).
Consequently, if A(n, p) is a multiple of 7, A(n + 1, p) is also one and if A(n, p) cannot be
divided by 7, A(n + 1, p) cannot either.
Answer 2. From the previous answer, A(n, p) is made of integers multiple of 7 if and 9-A2
only if the first term of the series (A(n0 , p) = A(p, p)) is a multiple of 7. The first term of
each of the four proposed series is now considered:
• the first terms of the series A(n, 0) is A(1, 0) = 32 − 21 = 7 and A(2, 0) = 77 and the series
is made of integers multiple of 7 for any positive integer n,
• the series A(n, 1) starts with A(1, 1) = 32 −20 = 8, and this series is not made of numbers
multiple of 7 for any positive integer n,
• the first term of the series A(n, 2) is A(2, 2) = 34 − 20 = 80, and this series is not made of
multiples of 7 for any integer n strictly greater than 1,
• the series A(n, 3) starts with A(3, 3) = 36 − 20 = 728 = 7 · 104. It can be deduced that any
element of the series A(n, 3) can be divided by 7 for any integer n strictly greater than 2.
Answer 1. For n = 1, the suggested closed form yields A(1) = 1, which matches the 10 - A 1
value given by the recurrence formula. We will demonstrate that for any n > 1:
(n + 1)2 − (n + 1) + 1 n2 + n + 1
A(n + 1) = = .
(n + 1)2 (n + 1)2
One has:
(n + 1)2 − 3(n + 1) + 1 n2 − n − 1
A(n + 1) = A(n) + = A(n) +
n2 · (n + 1)2 n2 · (n + 1)2
and replacing A(n) by its value given by the recurrence relation:
n2 − n + 1 n2 − n − 1 n4 + n3 + n2 n2 + n + 1
A(n + 1) = + = =
n2 n2 · (n + 1)2 n2 · (n + 1)2 (n + 1)2
which is the expected expression.
The numerator and the denominator of the expression defining numbers A(n) are integers,
hence these numbers are rational ones.
i i
i i
i i
i i
On the other hand, they are positive since for any positive integer n:
2
n2 − n + 1 n−1
A(n) = > ⩾ 0.
n2 n
Answers to problem 11. The lizard sequence The problem is on page 38.
11 - A 1 Answer 1. We denote by a and b the first two terms of a sequence S obeying the con-
straints of the statement. We will prove that, if we assume that the (3k − 1) first terms of
the sequence S = ⟨a, b, s3 , . . . , s3k−1 , . . .⟩ for k ⩾ 1 are known, the next three terms can be
identified. Then, it will be possible to deduce that it is possible to build a lizard sequence
S as long as desired. We use a proof by strong induction.
Induction For k ⩾ 1, the first (3k − 1) terms of S are assumed to be known (induction
hypothesis). Then:
S = ⟨a, b, s3 , . . . , s3k−1 , x, y, z, . . .⟩
and we want to determine the value of the terms x, y and z of respective rank 3k, 3k+1
and 3k + 2. More precisely, the three sequences are written:
S = ⟨a, b, s3 , . . . , sk , . . . , s2k+1 , s2k+2 . . . , s3k−1 , x, y, z, . . .⟩
S/3 = ⟨s3 , . . . , x, . . .⟩
S − S/3 = ⟨a, b, . . . , y, z, . . .⟩.
It turns out that: (i) x is the kth term of S/3 and it should be equal to the kth term of
S, so x = sk and sk is known since k ∈ 1 .. 3k − 1, (ii) y is the (2k + 1)th term of S − S/3
and it should be equal to the (2k + 1)th term of S, so y = s2k+1 . Now, (2k + 1) is in
the range 1 .. 3k − 1 only if k ⩾ 2. However, for k =1, the term s2k+1 is none other
than x which we know from the above, (iii) z is the (2k + 2)th term of S − S/3 and it
should be equal to the (2k + 2)th term of S, so z = s2k+2 . Now, (2k + 2) is in the range
1 .. 3k − 1 only if k ⩾ 3. However, for k = 1, the term s2k+2 is none other than y which
is known from the above, and if k = 2, the term s2k+2 is identified with x also known.
Conclusion It is possible to build a sequence S of any length given the first two terms a
and b.
i i
i i
i i
i i
Solutions 53
In addition to the two trivial sequence made solely of 0’s or 1’s, there are two lizard se-
quences, depending on the value (0 or 1) taken by a and b:
S1 = ⟨0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0⟩
S2 = ⟨1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1⟩
where S2 (respectively S1 ) is obtained from S1 (respectively S2 ) by the inversion of 0’s and
1’s.
Answers to problem 12. Fibonacci sequence; about the closed form The
problem is on page 39.
Answer 1. Programming directly the proposed formula delivers a real number, not an 12 - A 1
integer value as expected. In the experiment
√ that we have conducted with the language
Ada provided by the Ideone platform, 5 = 2.236068 and the simple precision number
representation, a difference between the exact value and the integer part of the real result
appears from n = 68.
Answer 2. The computation of the nth Fibonacci number is performed in an iterative 12 - A 2
fashion based on the recurrence. It can be noticed that, as for the computation of a factorial,
keeping values F(1) to F(n−1) is useless for the computation of F(n). Only three variables
are necessary x, y and z, which play the role of F(n − 2), F(n − 1) and F(n). The program
is the following:
1. constants
2. n ∈ N1 − {1, 2} and n = . . .
3. variables
4. x ∈ N1 and y ∈ N1 and z ∈ N1
5. begin
6. x ← 1; y ← 1 ;
7. for i ranging 3 .. n do
8. z ← x + y; x ← y; y ← z
9. end for;
10. write(Fibonacci number of rank , n, is , z)
11. end
Answers to problem 13. How many binary trees have n nodes? The problem
is on page 40.
Answer 1. Let j = i + 1, for n ⩾ 1, nbBT (n) can be rewritten: 13 - A 1
X
n
nbBT (n) = nbBT (j − 1) · nbBT (n − j).
j=1
Xn
Cat(n + 1) = Cat(i) · Cat(n − i + 1).
i=1
i i
i i
i i
i i
13 - A 2 Answer 2. We have seen the closed form of Catalan numbers on page 11, namely:
(2n − 2)! 1
Cat(n) = = · Cn−1
2n−2 n ⩾ 1.
(n − 1)! n! n
The value nbBT (n) can be written thanks to the previous expression of the (n + 1)th Cata-
lan number:
nbBT (0) = 1
nbBT (1) = 1
1 (n + 2) · · · 2n
nbBT (n) = Cat(n + 1) = · Cn
2n = n > 1.
n+1 2···n
The corresponding program is:
1. constants
2. n ∈ N and n = . . .
3. variables
4. NBBT ∈ N1 and Denom ∈ N1
5. begin
6. NBBT ← 1;
7. for i ranging n + 2 .. 2n do
8. NBBT ← NBBT · i
9. end for;
10. Denom ← 1;
11. for i ranging 2 .. n do
12. denom ← Denom · i
13. end for;
14. NBBT ← NBBT/Denom;
15. write(the number of binary trees having , n, nodes is , NBBT )
16. end
Answers to problem 14. Identifying a closed form The problem is on page 40.
14 - A 1 Answer 1. To compute a(3, 2), we need the values a(2, 1), a(2, 2) and a(2, 3), which,
in turn, require the knowledge of a(1, 0), . . . , a(1, 4). The calculation of these latter values
is based on a(0, 0), . . . , a(0, 5), values obtained directly from the recurrence formula (first
line).
The values are computed as follows: (i) elements whose first index is 0 and second index
j ranges 0 .. 5, thanks to the first line of the recurrence formula, (ii) element a(1, 0) with
the second line of the recurrence, and elements whose first index equals 1 and second
index ranges 1 .. 4 using the third term of the recurrence, (iii) elements a(2, 1), a(2, 2) and
a(2, 3) with the third line, and last (iv) element a(3, 2) using once again the third line.
From a concrete point of view, the computations will result in the (partial) filling of the
array A[0 .. i, 0 .. i + j] whose values are reported in figure 1.10, page 55.
The calculation of a(i, j) corresponds to the filling of cell A[i, j]. We start with cells
A[0, max({j − i, 0})] to A[0, j + i] (first line of the recurrence), then (when i > 0) cells
A[k, max({j − i + k, 0})] to A[k, j + i − k] of any line whose index k is varying from 1
i i
i i
i i
i i
Solutions 55
j 0 1 2 3 4 5
i=0 1 2 3 4 5 6
1 4 8 12 16 20
2 32 48 64
3 192
to i, using the second (respectively third) line of the recurrence for the first cell when
max({j − i + k, 0}) = 0 (respectively max({j − i + k, 0}) > 0) and the third line for all
other cells.
Answer 2. The following algorithm computes the value of cell A[n, m] related to 14 - A 2
a(n, m) according to the previously described progression.
1. constants
2. n ∈ N and n = . . . and m ∈ N and m = . . .
3. variables
4. A ∈ 0..n × 0..n + m → N1
5. begin
6. for j ∈ 0 .. m + n do
7. A[0, j] ← j + 1
8. end for;
9. for i ranging 1 .. n do
10. for j ranging max({m − n + i, 0}) .. n + m − i do
11. if j = 0 then
12. A[i, 0] ← 2 · A[i − 1, 0] + A[i − 1, 1]
13. else
14. A[i, j] ← A[i − 1, j − 1] + 2 · A[i − 1, j] + A[i − 1, j + 1]
15. end if
16. end for
17. end for;
18. write(the value of the sequence in , n, m, is , A[n, m])
19. end
Remark
We invite the reader to design another version where a two row array A is used.
Answer 3. It turns out that the formula a(i, j) = (j + 1) · 4i for i, j ⩾ 0 holds over the 14 - A 3
whole array of figure 1.10, page 55.
So as to prove it by induction, it is necessary to use a valid proof pattern. A glance at the
recurrence formula defining a(i, j) leads to think that neither the pattern given in page
9, nor that proposed in problem 8 page 37 is suitable, since their initialization requires to
demonstrate the validity of the formula for the first column of the tabular structure. From
the partial order relation ⪯ over N2 defined in section 1.1.6, page 9:
b a < c or (a = c and b ⩽ d)
(a, b) ⪯ (c, d) =
it is easy to show that the following pattern (of proof) is an instance of the property (1)
page 9, for the pair (N2 , ⪯):
i i
i i
i i
i i
It can be noticed that the proof to be done requires only an order over lines, but that the
reference property (property 1), page 9) requires a total order. This pattern is now used to
prove that
1. constants
2. n ∈ N and n = . . . and m ∈ N and m = . . .
3. begin
4. write(the value of the sequence in , n, m, is , (m + 1) · 4n )
5. end
both simpler and more efficient than the algorithm of the previous question.
15 - A 1 Answer 1. In general, there are four possibilities for reaching the square (i, j) in a single
move: the knight was in (i − 2, j − 1) or in (i − 1, j − 2) or in (i + 1, j − 2) or in (i + 2, j − 1).
It can be deduced that for 3 ⩽ i ⩽ n − 2 and 3 ⩽ j ⩽ m:
i i
i i
i i
i i
Solutions 57
nbRout(1, 1) = nbRout(3, 2) = 1
nbRout(i, 1) = 0 2⩽i⩽n
nbRout(i, 2) = 0 1 ⩽ i ⩽ n and i ̸= 3
nbRout(1, j) = nbRout(3, j − 1) + nbRout(2, j − 2) 3⩽j⩽m
nbRout(2, j) = nbRout(3, j − 2) + nbRout(1, j − 2) + nbRout(4, j − 1) 3⩽j⩽m
nbRout(n, j) = nbRout(n
− 2, j − 1) + nbRout(n
− 1, j − 2) 3⩽j⩽m
nbRout(n − 3, j − 1)+
nbRout(n − 1, j) = nbRout(n − 2, j − 2)+ 3⩽j⩽m
nbRout(n, j − 2)
nbRout(i − 2, j − 1)+
nbRout(i − 1, j − 2)+ 3⩽i⩽n−2
nparc(i, j) =
nbRout(i + 1, j − 2)+
and .
3⩽j⩽m
nbRout(i + 2, j − 1)
Answer 2. The values of nbRout are stored in a n row, m column array, NR[1..n, 1..m]. 15 - A 2
Columns 1 and 2 are first initialized thanks to the first three terms of the recurrence. Due
to the fact that the calculation of any other square call only on values located “on its left
side”, columns 3 to m are then dealt with: the four extreme elements (row index 1, 2, (n−1)
and n) are calculated by means of terms 3 to 6 of the recurrence, others using the last term
of the recurrence (general case). This yields the following algorithm:
1. constants
2. n ∈ N1 − {1 .. 4} and n = . . . and m ∈ N1 − {1 .. 3} and m = . . .
3. variables
4. NR ∈ 1 .. n × 1 .. m → N1
5. begin
6. NR[1, 1] ← 1;
7. for i ranging 2 .. n do
8. NR[i, 1] ← 0
9. end for;
10. for i ranging 1 .. n do
11. NR[i, 2] ← 0
12. end for;
13. NR[3, 2] ← 1;
14. for j ranging 3 .. m do
15. NR[n, j] ← RP[n − 1, j − 2] + NR[n − 2, j − 1];
16. NR[n − 1, j] ← NR[n, j − 2] + NR[n − 2, j − 2] + NR[n − 3, j − 1];
17. NR[1, j] ← NR[2, j − 2] + NR[3, j − 1];
18. NR[2, j] ← NR[1, j − 2] + NR[3, j − 2] + NR[4, j − 1];
19. for i ranging 3 .. n − 2 do
20. NR[i, j] ← NR[i−2, j−1]+NR[i−1, j−2]+NR[i+1, j−2]+NR[i+2, j−1]
21. end for
22. end for;
23. write(the number of ways for moving from (1, 1) to (, n, , , m, ) is ,
NR[n, m])
24. end
Running this algorithm for n = 5 and m = 7 leads to the following array:
i i
i i
i i
i i
j 1 2 3 4 5 6 7
i=5 0 0 1 0 2 3 10
4 0 0 0 2 2 5 7
3 0 1 0 2 1 8 10
2 0 0 1 1 3 4 9
1 1 0 1 0 3 2 11
16 - A 1 Answer 1. We have:
• one partition with one block: {{a, b, c, d}},
• seven partitions with two blocks: {{a, b}, {c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}},
{{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}},
• six partitions with three blocks: {{a}, {b}, {c, d}}, {{a, b}, {c}, {d}}, {{a, c}, {b}, {d}},
{{a}, {c}, {b, d}}, {{a, d}, {b}, {c}}, {{a}, {d}, {b, c}},
• one partition with four blocks: {{a}, {b}, {c}, {d}}.
S(1, n) = 1 n⩾1
S(p, p) = 1 p>1
S(p, n) = 0 p>n
S(p, n) = p · S(p, n − 1) + S(p − 1, n − 1) n ⩾ 1 and p < n.
16 - A 3 Answer 3. The array S[1 .. p, 1 .. n] is used to compute the values associated with this
recurrence. Observing the recurrence, we can notice that, in the general case (fourth term),
the value of element S[i, j] depends on those of the two elements located in the preceding
column (j − 1), which makes it possible to proceed by increasing values of the column
index. Each column j is filled as follows: (i) cell S[1, j] is initialized to 1 (first term of the
recurrence), (ii) the general term is used for the calculation of any cell S[i, j] where i < j
and i ⩽ p, (iii) when the cell S[j, j] belongs to the array, it is set to 1, and finally (iv) any cell
S[i, j] where i > j is set to 0.
The corresponding algorithm is:
1. constants
2. n ∈ N1 and n = . . . and p ∈ N1 and p ⩽ n and p = . . .
i i
i i
i i
i i
Solutions 59
3. variables
4. S ∈ 1 .. p × 1 .. n → N
5. begin
6. S[1, 1] ← 1;
7. for i ranging 2 .. p do
8. S[i, 1] ← 0
9. end for;
10. for j ranging 2 .. n do
11. S[1, j] ← 1;
12. for i ranging 2 .. p do
13. if i < j then
14. S[i, j] ← i · S[i, j − 1] + S[i − 1, j − 1]
15. elsif i = j then
16. S[i, j] ← 1
17. else
18. S[i, j] ← 0
19. end if
20. end for
21. end for;
22. write(the number of partitions with , p, blocks of a set having , n,
elements
23. is , S[p, n])
24. end
Answer 4. For p = 5 and n = 7, the values obtained are reported in the array below: 16 - A 4
n 1 2 3 4 5 6 7
p=1 1 1 1 1 1 1 1
2 0 1 3 7 15 31 63
3 0 0 1 6 25 90 301
4 0 0 0 1 10 65 350
5 0 0 0 0 1 15 140
Answer 1. Two possible sequences of jumps are ⟨5, 2, 5⟩ and ⟨2, 5, 5⟩, which shows that 17 - A 1
the order of the jumps matters (when they are different).
Answer 2. The recurrence relation is built according to the following observations: 17 - A 2
Special cases There is a single way to climb 0 steps with 0 jumps and therefore
nbCL(0, 0) = 1. Moreover, there is no way for jumping (at least one jump) without
climbing (at least one step) and nbCL(s, 0) = 0 for s ⩾ 1. Last, one has nbCL(0, m) = 0
for m > 0, since it is impossible to climb at least one step without jumping.
General case Let us suppose that we are on step m of the staircase after s jumps, with s
and m strictly positive. As s > 0, just before we made a jump (which led us to the step
m) from one of the steps from which step m can be reached with a single jump. The
count of ways to reach the step m with s jumps is thus equal to the sum of the ways
we had to reach these steps.
i i
i i
i i
i i
nbCL(0, 0) = 1
nbCL(0, m) = 0 m>0
nbCL(s, 0) = 0 X s>0
nbCL(s, m) = nbCL(s − 1, m − ai ) s > 0 and m > 0.
i∈1..n and
(m−ai )⩾0
17 - A 3 Answer 3. To compute this recurrence, the array NBCL[0 .. s, 0 .. m] is used where the
cell NBCL[i, j] is associated with the element nbCL(i, j) of the recurrence. It can be ob-
served that the calculation of the cell NBCL(s, m) calls only on values whose first index is
immediately lower (s − 1). Hence, the calculation can progress by increasing values of row
indexes inasmuch as the first row (index 0) is initialized, which is performed by means of
the first two terms of the recurrence. Last, any row can be filled in from left to right after
setting the first element to 0, according to the third term of the recurrence.
The n values of the possible jumps (ai ) are stored in the array A[1 .. n], in increasing order
(without loss of generality). The corresponding algorithm is the following:
1. constants
2. n ∈ N1 and n = . . . and s ∈ N1 and s = . . . and m ∈ N1 and m = . . . and
3. A ∈ 1 .. n → N1 and A = [. . .]
4. variables
5. NBCL ∈ 0 .. s × 0 .. m → N
6. begin
7. NBCL[0, 0] ← 1;
8. for j ranging 1 .. m do
9. NBCL[0, j] ← 0
10. end for;
11. for i ranging 1 .. s do
12. NBCL[i, 0] ← 0;
13. for j ranging 1 .. m do
14. NBCL[i, j] ← 0;
15. for k ranging 1 .. n do
16. if j − A[k] ⩾ 0 then
17. NBCL[i, j] ← NBCL[i, j] + NBCL[i − 1, j − A[k]]
18. end if
19. end for
20. end for
21. end for;
22. write(the number of ways for climbing , m, steps with , s, jumps
23. is , NBCL[s, m])
24. end
A possible variant would consist in the suppression of lines 16 à 18 and the use of the array
NF whose column indexes range from −A[n] to m, NBCL[0..s, −A[n]..−1] being initialized
with 0’s.
17 - A 4 Answer 4. With the algorithm explicited above, for s = 6, m = 12, n = 2, a1 = 2 and
a2 = 5, the following array NF is produced:
i i
i i
i i
i i
Solutions 61
j 0 1 2 3 4 5 6 7 8 9 10 11 12
i=0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0 0 0 0 0 0
2 0 0 0 0 1 0 0 2 0 0 1 0 0
3 0 0 0 0 0 0 1 0 0 3 0 0 3
4 0 0 0 0 0 0 0 0 1 0 0 4 0
5 0 0 0 0 0 0 0 0 0 0 1 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 1
Answer 5. Using the array A whose values are increasing as previously stated, the 17 - A 5
number of steps reached with s jumps cannot be neither under s · A[1], nor above s · A[n],
which explains the 0’s appearing in the cells connected with these cases (for example,
columns with index j = 11 and j = 12 for i = 2 and the last ten columns for i = 5).
Consequently, we can envisage a variant of the initial algorithm where, after the initializa-
tion of any row with 0’s, the filling of row i is restricted to cells whose column index lies in
the interval i · A[1] .. max({m, i · A[n]}). Lines 11 to 21 of the previous algorithm are replaced
by:
1. for i ranging 1 .. s do
2. NBCL[i, 0] ← 0;
3. for j ranging 1 .. m do
4. NBCL[i, j] ← 0
5. end for;
6. for j ranging i · A[1] .. min({m, i · A[n]}) do
7. for k ranging 1 .. n do
8. if j − A[k] ⩾ 0 then
9. NBCL[i, j] ← NBCL[i, j] + NBCL[i − 1, j − A[k]]
10. end if
11. end for
12. end for
13. end for;
Answers to problem 18. The Patagon game The problem is on page 42.
Answer 1. Of course, several choices are possible, but the one looking like the best one 18 - A 1
(intuitively for the moment or after the evaluation of all legal choices) is the sequence ⟨23,
40, 42⟩, yielding the total amount 105.
Answer 2. 2n is the number of distinct subsets of a set having n elements, or the num- 18 - A 2
ber of distinct n sized binary vectors. This would be the number of unconstrained ways of
playing. But, for n > 1, there is at least one vector with two successive 1’s; therefore the
legal ways of playing are strictly less than 2n .
Answer 3. Any binary vector cannot contain two successive 1’s and a reasonable vec- 18 - A 3
tor cannot have three consecutive 0’s either (in such a case, that of the middle could be
replaced by 1). In addition, it can neither start, nor end with 00.
Answer 4. The first six expressions are established by enumeration. For a 1 sized 18 - A 4
game, the only reasonable possibility is to take its single object, and nbRWP0 (1) = 0
and nbRWP1 (1) = 1. For a 2 sized game, 01 and 10 only are reasonable choices, and
nbRWP0 (2) = nbRWP1 (2) = 1. Last, with a 3 sized game, the reasonable configurations
i i
i i
i i
i i
are: 010 et 101, therefore nbRWP0 (3) = nbRWP1 (3) = 1. The general term of the recurrence
is developed in studying the four exclusive exhaustive cases of n-sized reasonable vectors
with n > 3: V1 = [. . . , 0, 0, 1, 0], V2 = [. . . , 1, 0, 1, 0], V3 = [. . . , 1, 0, 0, 1], V4 = [. . . , 0, 1, 0, 1].
It can be remarked that when removing the final 0 in V1 and V2 , we obtain a reasonable
vector with 1 in position n − 1, thus nbRWP0 (n) = nbRWP1 (n − 1). It is not the case
when removing the final 1 in vectors V3 and V4 , since then, if V4′ = [. . . , 0, 1, 0] is clearly a
reasonable vector, V3′ = [. . . , 1, 0, 0] is not. It is necessary to study carefully what happens
when the last two elements of V3 are suppressed. We then get V3′′ = [. . . , 1, 0], which is a
reasonable vector and it can be deduced that:
nbRWP1 (n) = nbRWP0 (n−1)+nbRWP0 (n−2) = nbRWP1 (n−2)+nbRWP1 (n−
3)
using the definition of nbRWP0 established before.
18 - A 5 Answer 5. The values nbRWP(1), nbRWP(2) and nbRWP(3) are obtained by the cor-
responding values of nbRWP0 and nbRWP1 , i.e.:
nbRWP(1) = nbRWP0 (1) + nbRWP1 (1) = 0 + 1 = 1,
nbRWP(2) = nbRWP0 (2) + nbRWP1 (2) = 1 + 1 = 2,
nbRWP(3) = nbRWP0 (3) + nbRWP1 (3) = 1 + 1 = 2.
For n > 3, using the definition one gets:
nbRWP(n) = nbRWP0 (n) + nbRWP1 (n)
= nbRWPr1 (n − 3) + nbRWP1 (n − 4) + nbRWP1 (n − 2) + nbRWP1 (n − 3)
= nbRWP0 (n − 2) + nbRWP0 (n − 3) + nbRWP1 (n − 2) + nbRWP1 (n − 3)
= nbRWP(n − 2) + nbRWP(n − 3).
18 - A 6 Answer 6. The values of nbRWP0 (n), nbRWP1 (n) and nbRWP(n) for n varying from
1 to 15 are gathered in the array below:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
nfr0 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28
nfr1 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
nfr 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65
It can be observed that for n > 2: nbRWP1 (n) = nbRWP(n − 2). This is not surpris-
ing since: (i) the form of their recurrence is the same, nbRWP1 (3) = nbRWP(1) = 1 and
nbRWP1 (4) = nbRWP(2) = 2, (ii) in question 4:
nbRWP1 (n) = nbRWP0 (n − 1) + nbRWP0 (n − 2) = nbRWP1 (n − 2) + nbRWP0 (n − 2)
= nbRWP(n − 2).
Remark
As seen in page 10, the sequence whose general term is P(n) = P(n − 2) + P(n − 3) for
any n > 2 where P(0) = P(1) = P(2) = 1, defines the Padovan sequence. Its numbers are
exponentially increasing in the order of (1.324 · · · )n−1 . More precisely, the nth number is
the integer closest to (1.324 · · · )n−1 /1.045 · · · . For instance, P(20) = 200.
The number 1.324 · · · is sometimes called silver ratio , by analogy with the golden ratio
related to Fibonacci sequence.
18 - A 7 Answer 7. The calculation of nbRWP(i) requires only nbRWP(i−2) and nbRWP(i−3).
To compute nbRWP(n), the array T [1 .. 4] is used to keep the last four values of nbRWP,
thus the program:
i i
i i
i i
i i
Solutions 63
1. constants
2. n ∈ N1 and n = . . .
3. variables
4. T ∈ 1 .. 4 → N1
5. begin
6. T [1] ← 1; T [2] ← 2; T [3] ← 2;
7. for i ranging 4 .. n do
8. T [4] ← T [1] + T [2];
9. for j ranging 1 .. 3 do
10. T [j] ← T [j + 1]
11. end for
12. end for;
13. write(the number of reasonable ways for playing with a game
14. of size , n, is , T [4])
15. end
Answers to problem 19. The game of two stacks The problem is on page 44.
Answer 1. There is one and only one way to reach a winning state if one is already 19 - A 1
in this state: doing nothing. In the configuration p = 1, q = 1, it is no longer possible to
play, a winning state is unattainable and it is lost. When p ⩾ 2 and q ⩾ 2, two possible
ways of playing are open and the number of ways to reach a winning state is given by the
sum of the ways to win from the two configurations attained when playing (p − 2, q + 1 or
p + 1, q − 2). When p or q is less than 2, there is a single way of playing and the number of
ways to win from the configuration (p, q) equals that of the new configuration (p − 2, q + 1
when q < 2, p + 1, q − 2 when p < 2). The following recurrence can be derived, which
accounts for the symmetry of the problem:
nbWW(0, 1) = nfg(1, 0) = 1
nbWW(1, 1) = 0
nbWW(0, q) = nbWW(1, q − 2) q>1
nbWW(1, q) = nbWW(2, q − 2) q>1
nbWW(p, 0) = nbWW(p − 2, 1) p>1
nbWW(p, 1) = nbWW(p − 2, 2) p>1
nbWW(p, q) = nbWW(p − 2, q + 1) + nbWW(p + 1, q − 2) p > 1 and q > 1.
Answer 2. Due to the fact that the number p (respectively q) of tokens of stack P (re- 19 - A 2
spectively Q) may increase, the tabular structure cannot be reduced to an array with (p+1)
rows and (q + 1) columns (or the reverse). Strictly speaking, an array with (p + ⌊q/2⌋ + 1)
rows and (q + ⌊p/2⌋ + 1) columns would suffice, but for simplicity of the filling, a squared
tabular structure T [0 .. p + q, 0 .. p + q] is used where T [i, j] corresponds to nfWW(i, j). As
to the general case, this array can be filled in by increasing diagonals of equation (p + q),
since nbWW(p, q) is located on the diagonal of equation (p + q) and the two elements
required for its calculus are located on the diagonal of equation (p + q − 1). Diagonals
of equation 1, 2 et 3 (0 is meaningless) are first initialized using the appropriate terms of
the recurrence. Then, elements of a diagonal are filled in thanks to the general term of the
recurrence, except the extreme four terms for which the terms associated with p or q less
than 2 are used.
Answer 3. The algorithm below implements the above principles: 19 - A 3
i i
i i
i i
i i
1. constants
2. p ∈ N1 − {1} and p = . . . and q ∈ N1 − {1} and q = . . .
3. variables
4. T ∈ 0 .. p + q × 0 .. p + q → N
5. begin
6. T [0, 1] ← 1; T [1, 0] ← 1;
7. T [2, 0] ← 1; T [0, 2] ← 1; T [1, 1] ← 0;
8. T [3, 0] ← 0; T [1, 2] ← 1; T [2, 1] ← 1; T [0, 3] ← 0;
9. for k ranging 4 .. p + q do
10. T [0, k] ← T [1, k − 2];
11. T [1, k − 1] ← T [2, k − 3];
12. T [k, 0] ← T [k − 2, 1];
13. T [k − 1, 1] ← T [k − 3, 2];
14. for j ranging 2 .. k − 2 do
15. T [j, k − j] ← T [j − 2, k − j + 1] + T [j + 1, k − j − 2]
16. end for
17. end for;
18. write(the number of ways for winning with two stacks having, p,
and , q, tokens
19. is , T [p, q])
20. end
i i
i i
i i
i i
Solutions 65
Answers to problem 20. The yellow coins The problem is on page 44.
The origin of the problem lies in the fact that some combinations of coins are counted more
than once. Thus, when we convert “To form the amount s of three cents, one takes a one
cent coin and the amount (s − 1) remains to be formed, or one takes a two cent coin and the
amount (s − 2) remains to be formed”, into nbWF1E(3) = nbWF1E(2) + nbWF1E(1), there
is no guarantee that distinct ways are counted. In this example, the combination made of
a one cent coin and a two cent coin is obtained (and counted) twice. In other words, the
recurrence suggested does not take into account exclusive situations leading to distinct
ways for forming the desired amount and in this respect this is not a valid recurrence.
Answer 2. Now, we envisage a double index recurrence and we denote by 20 - A 2
nbWF1E2(m, p) the number of distinct ways for forming the amount m with the coins
numbered from p to 6. We proceed as follows. To form the amount m with coins num-
bered from p to 6 (p < 6), we can: (i) take only coins ranked strictly over p (i.e. no coin of
value value v(p)), or (ii) take a single coin of value v(p) (if possible, i.e. if m ⩾ v(p)) and
the amount (m − v(p)) remains to be formed with the coins whose rank ranges from (p + 1)
to 6 according to the same mechanism, or (iii) if possible (i.e. if m ⩾ 2 · v(p)) take two coins
whose rank is p and the amount (m − 2 · v(p)) remains to be formed with coins whose rank
ranges from (p + 1) to 6 according to the same mechanism, (iv) and so on. In doing so, we
are ensured that the ways for forming the amount m are different by construction since, in
i i
i i
i i
i i
the first case the combination of coins involves no coin whose rank is p, in the second case
a single such coin is inserted, in the third case two such coins appear, etc. Therefore, when
m ⩾ v(p), one can write:
⌊ v(p)
m
⌋
X
nbWF1E2(m, p) = nbWF1E2(m − i · v(p), p + 1)
i=0
or even:
nbWF1E2(m, p)
= distinction of the first term
⌊ v(p)
m
⌋
X
nbWF1E2(m, p + 1) + nbWF1E2(m − i · v(p), p + 1)
i=1
= variable change, (i − 1) becomes j
⌊ m−v(p)
v(p) ⌋
X
nbWF1E2(m, p + 1) + nbWF1E2(m − v(p) − j · v(p), p + 1)
j=0
= definition of nbWF1E2
nbWF1E2(m, p + 1) + nbWF1E2(m − v(p), p).
When m is strictly less than v(p), the only way for forming the amount m is to ignore
coins of rank p and use those ranked from (p + 1) to 6. So, we end up with the recurrence
hereafter
nbWF1E2(0, p) = 1 1⩽p⩽6
nbWF1E2(m, 6) = 1 m is a multiple of v(6) and 1 ⩽ m ⩽ 100
nbWF1E2(m, 6) = 0 m is not a multiple of v(6) and 1 ⩽ m ⩽ 100
nbWF1E2(m, p) = nbWF1E2(m, p + 1) + nbWF1E2(m − v(p), p) m⩾
v(p) and 1 ⩽ p < 6 and 1 ⩽ m ⩽ 100 nbWF1E2(m, p) = nbWF1E2(m, p + 1)
m < v(p) and 1 ⩽ p < 6 and 1 ⩽ m ⩽ 100.
Remark 1
It is worth noticing that the order of the coins does not matter, the key point is to con-
sider all of them and to calculate nbWF1E2(100, 1). If it is assumed that the coins are
ordered increasingly on their values, the last term of the recurrence can be replaced by
nbWF1E2(m, p) = 0, since when m is less than v(p), it is less than v(p + 1) too.
Remark 2
One could consider nbWF1E2(m, p) the number of ways for forming the amount m with
coins 1 to p, in which case one would calculate nbWF1E2(100, 6).
20 - A 3 Answer 3. In the example aiming at forming three cents with yellow coins such that
v(1) = 20, v(2) = 5, v(3) = 10, v(4) = 1, v(5) = 50 and v(6) = 2 (but any other ordering of
the coins would be suitable as well), one has:
nbWF1E2(3, 1) = nbWF1E2(3, 2); nbWF1E2(3, 2) = nbWF1E2(3, 3); nbWF1E2(3, 3) =
nbWF1E2(3, 4);
nbWF1E2(3, 4) = nbWF1E2(3, 5) + nbWF1E2(2, 4).
i i
i i
i i
i i
Solutions 67
Yet:
nbWF1E2(2, 4) = nbWF1E2(2, 5) + nbWF1E2(1, 4) = nbWF1E2(2, 6) +
nbWF1E2(1, 5) + nbWF1E2(0, 4) = 1 + nbWF1E2(1, 6) + 1 = 1 + 0 + 1 = 2;
nbWF1E2(3, 5) = nbWF1E2(3, 6)+nbWF1E2(1, 5) = 0+nbWF1E2(1, 6) = 0+0 =
0.
Finally, nbWF1E2(3, 1) has the value 2, as expected.
Answer 4. The program performing the calculation uses the array T [0 .. 100, 1 .. 6] asso- 20 - A 4
ciated with nbWF1E2, and the result is T [100, 1]. The value of the yellow coins are stored in
the array V[1 .. 6] in any order a priori. The recurrence defined before leads to a progression
according to decreasing value of the column index. We start with column 6 for which sec-
ond and third terms are used. Then, each column is filled in according to increasing values
of row index: the cell of index 0 thanks to the first term, next elements using fourth and
fifth terms. This results in the following program:
1. constants
2. V ∈ 1 .. 6 → N1 and V = [1, 2, 5, 10, 20, 50]
3. variables
4. T ∈ 0 .. 100 × 1 .. 6 → N
5. begin
6. for i ranging 0 .. 100 do
7. T [i, 6] ← 0
8. end for;
100
9. for i ranging 0 .. ⌊ V[6] ⌋ do
10. T [V[6] · i, 6] ← 1
11. end for;
12. for p ranging inverse 1 .. 5 do
13. T [0, p] ← 1;
14. for m ranging 1 .. V[p] − 1 do
15. T [m, p] ← T [m, p + 1]
16. end for;
17. for m ranging V[p] .. 100 do
18. T [m, p] ← T [m, p + 1] + T [m − V[p], p]
19. end for
20. end for;
21. write(the number of ways for forming one euro with yellow coins
is , T [100, 1])
22. end
Answer 5. By running this program, it appears that there are 4562 distinct ways for 20 - A 5
forming one euro with yellow coins.
Answer 6. It has been seen that nbWF1E2(m, 1) does not depend on the order accord- 20 - A 6
ing to which yellow coins are taken into account, therefore on the order of values in V.
Hence, it is possible to work with the vector V = [1, 2, 5, 10, 20, 50]. In this context, for
m > 0, nbWF1E2(m, 1) is defined as the sum of nbWF1E2(m, 2) and nbWF1E2(m − 1, 1).
Since nbWF1E2(m, 2) ⩾ 0, one has:
nbWF1E2(m, 1) ⩾ nbWF1E2(m − 1, 1).
Another justification of this result can be found in realizing that the formation of the
amount m with the six yellow coins can begin with the formation of (m − 1) followed
by the addition of a one cent coin to get m.
i i
i i
i i
i i
Remark
When all the values of T are displayed, it turns out that, as a matter of fact, nbWF1E2(m, 1)
grows with m, non strictly for the first four values and strictly after. However, it can be
noted that, in general, nbWF1E2(m, p) where p ̸= 1 is not increasing.
21 - A 1 Answer 1. Let us denote by nbShuf(i, j) the number of distinct shuffles that can be
built from the prefixes u[1 .. i] and v[1 .. j] of the words u and v. In the general case w[i + j]
can be either u[i], or v[j]. In the first case, there are nbShuf(i − 1, j) possible shuffles ending
by u[i], and in the second one there are nbShuf(i, j − 1) possible shuffles ending with v[j].
When u (respectively v) is the empty word, there is a unique way for building the shuffle.
Thus, the following recurrence is obtained:
nbShuf(i, 0) = 1 0⩽i⩽m
nbShuf(0, j) = 1 0⩽j⩽n
nbShuf(i, j) = nbShuf(i − 1, j) + nbShuf(i, j − 1) 1 ⩽ i ⩽ m and 1 ⩽ j ⩽ n.
Remark
It can be observed that the array is symmetric with respect to the diagonal of equation
i − j = 0, which is in coherence with the fact that the two indexes i and j play the same role
in the recurrence.
21 - A 2 Answer 2. For the proof by induction, the pattern given page 9 is used since it is well
suited for this situation and we let P(m, n) = (nbShuf(m, n) = (m + n)!/(m! ·n!)).
Initialization For any integer i, one has:
i!
nbShuf(i, 0) = 1 =
i! · 0!
i i
i i
i i
i i
Solutions 69
(i + j − 1)! (i + j − 1)!
nbShuf(i − 1, j) = , nbShuf(i, j − 1) =
(i − 1)! · j! i! · (j − 1)!
it must be proven that:
(i + j)!
nbShuf(i, j) =
i! · j!
One has:
nbShuf(i, j)
= general term of the recurrence
nbShuf(i − 1, j) + nbShuf(i, j − 1)
= induction hypothesis
(i + j − 1)! (i + j − 1)!
+
(i − 1)! · j! i! · (j − 1)!
= arithmetics
i · (i + j − 1)! j · (i + j − 1)!
+
i! · j! i! · j!
= arithmetics
(i + j) · (i + j − 1)!
i! · j!
= definition of factorial
(i + j)!
.
i! · j!
(m + n)!
Conclusion ∀(m, n) · m ∈ N and n ∈ N ⇒ nbShuf(m, n) = .
m! · n!
The preceding result is rewritten:
(m + n)!
nbShuf(m, n) = = Cm n
m+n = Cm+n
m! · n!
in other words nbShuf(m, n) is the number of combinations of n (or m) elements out of
(m + n) or even the number of ways to choose n (or m) distinct letters out of (m + n). This
result can be established directly as follows. Let ML be an array with (m + n) cells. There
are Cn
m+n ways for taking m cells of this array to assign the letters of u in increasing order
of the index and in the order of the letters of u. For each way to place u, there is a single
way for the placement of the letters of v inside ML and therefore the number of shuffles of
u and v equals Cn m+n .
Answer 3. The requested decision algorithm is based on the recurrence isSHUF such 21 - A 3
that isSHUF(i, j) = true, if and only if w[1 .. i + j] is a shuffle of u[1 .. i] and v[1 .. j]. The
reasoning for establishing this recurrence is similar to that of the first question (w is a
shuffle of u and v only if its last letter is that of u or v). We get:
i i
i i
i i
i i
1. constants
2. u ∈ string and u = . . . and v ∈ string and v = . . .
3. and w ∈ string and w = . . . and m = |u| and n = |v|
4. variables
5. M ∈ 0 .. m × 0 .. n → B
6. begin
7. M[0, 0] ← true;
8. for j ranging 1 .. n do
9. M[0, j] ← M[0, j − 1] and w[j] = v[j]
10. end for;
11. for i ranging 1 .. m do
12. M[i, 0] ← M[i − 1, 0] and w[i] = u[i];
13. for j ranging 1 .. n do
14. M[i, j] ← (M[i − 1, j] and w[i + j] = u[i]) or (M[i, j − 1] and w[i + j] =
v[j])
15. end for
16. end for;
17. write(it is , M[m, n], to say that , w, is a shuffle of , u, and , v)
18. end
The handling of the example where u = abc, v = db, w = dabbc, leads to the array below:
j 0 1 2
ϵ d b
i=0 ϵ T T F
1 a F T T
2 b F T T
3 c F F T
Since the cell M[3, 2] contains the value true, it can be concluded that w =dabbc is a shuffle
of u =abc and v = db.
i i
i i
i i
i i
2
Complexity of an algorithm
A. Perlis
2.1 Reminders
2.1.1 Algorithm
First, let us recall that an algorithm is defined as a set of rules intended for the resolution of
a problem with input data. This set of rules defines exactly a sequence of operations which
terminate in finite time.
For example, let us consider the multiplication of two positive integers written in base
10. We have learnt at school a certain algorithm to solve this problem, on the basis of a pre-
cise sequence of elementary operations, using multiplication of digits in base 10 and addi-
tion of numbers. We know that this algorithm allows to calculate the product of any pair of
numbers in a finite time, depending on the length of the numbers. There exists other algo-
rithms to solve this problem, sometimes founded on variations on the same principle (like
the abacus technique), but also quite different, as is the so-called Russian multiplication1
(see figure 2.1), which requires only multiplications and divisions by 2 (and additions).
These algorithms are simple enough to be learnt by most of people, and pretty efficient,
in the sense that they deliver the expected result quickly and they require neither a large
space, nor the writing of too numerous digits. At the contrary, observe the following naïve
algorithm: to multiply n by m, write n lines each with m crosses, one below the other, then
count the total number of crosses. This latter method requires only the ability to count, but
it is much more costly in time and space.
DOI: 10.1201/b23251-2 71
i i
i i
i i
i i
72 Complexity of an algorithm
4 1 3 3
4 1 2 0 ̸6 ̸6
×
3 3 1 0 ̸1 ̸3 ̸2
1 2 3 5 2 6 4
+ 2 ̸5 ̸2 ̸8
1 2 3
1 1 0 5 6
1 3 5 3
1 3 5 3
Fig. 2.1 – Left: ordinary multiplication of 41 and 33. Right: Russian multiplication. On the left
column, from top to bottom, one writes the finite sequence of the integer divisions of 41 by 2. On
the right column, from top to bottom, one writes the sequence of the multiplications of 33 by 2. Line
by line, the parity of the left number is checked. If it is even (marked in grey), the right number in
the line is suppressed. Eventually, one adds all remaining numbers in the right column to obtain
41 × 31 = 33 + 264 + 1056.
Usually, the efficiency of an algorithm is measured as its time complexity (or temporal)
and its space complexity (or spatial). However, since the size of computer memories has
tremendously increased over the past years, space complexity is a less and less critical
criterion. That is why, in the remainder of this book, time complexity prevails.
On the basis of this remark, the goal of algorithmics becomes essentially the search
for an algorithm solving a given problem as quickly as possible. Hence, the key question
raised is that of the measurement of this speed. Of course, it is highly desirable to measure
the complexity of an algorithm independently of both the programming language used for
implementation and the computer onto which it will be run. Thus, complexity is analyzed
on the basis of one or several elementary operation(s) , which depend on the problem, but is
(are) representative of what the considered algorithm does. In that respect, for an algorithm
performing a search in an array, the elementary operation is the comparison, while for a
sort algorithm two elementary operations come into play: comparison and exchange of
data. Last, for the product of two matrices, the multiplication of (in general real) numbers
constitutes the elementary operation.
A second important point is that complexity is expressed according to the size of data
that are dealt with. This size is an integer characteristic of the problem. For an algorithm
searching in an array or sorting an array, it is the number of elements (or size) of the ar-
ray; for the product of two square matrices, it is the number of rows (or columns) of the
matrices. It is often impossible to give the exact complexity of an algorithm in terms of a
number of elementary operations depending on the size of the data. As a matter of fact,
most of time complexity depends on data themselves. For example, some sort algorithms
work very well when the array is already almost sorted and slowly if it is sorted backward.
For this reason, exact complexity is not the target and the considered notions are those of
minimum complexity (or best case) when data are supportive, and maximum complexity (or
worst case). It is tempting to define an average complexity, but this is hardy feasible in
general since statistical hypotheses about data distribution are required.
Another approach to time analysis is to use the notion of order of growth, which ex-
presses the behavior of complexity when data size becomes “huge” (asymptotic complex-
ity).
In the following two sections, we present the notions of minimum and maximum com-
plexity, then complexity analysis by order of growth.
i i
i i
i i
i i
Reminders 73
1. constants
2. n ∈ N1 and n = . . . and x ∈ string and x = . . .
3. variables
4. DIC ∈ 1 .. n + 1 → string and DIC = [. . .]
5. begin
6. DIC[n + 1] ← x ; i ← 1;
7. while DIC[i] ̸= x do
8. i←i+1
9. end while;
10. if i < n + 1 then
11. write(the word , x, is in position , i, in the dictionary)
12. else
13. write(the word , x, is not in the dictionary)
14. end if
15. end
What is the complexity of this algorithm? We already know that in the worst case (when x
is not in the original dictionary), (n + 1) comparisons are performed. In the best case, only
one comparison is done, if luckily enough, x is the first word in the dictionary. The average
complexity can be calculated under simple statistical hypotheses and it turns out that it is
not n/2 (see problem 27, page 81).
If it is now assumed that the dictionary is sorted, obviously there is a quicker method
for searching a word: binary search. There are many variants (see for example problem 90,
page 427); we suggest the following iterative version. The word located “in the middle”
of the dictionary is compared to x. If x is greater than (respectively lower than or equal
to) the middle element according to the lexicographical order, the operation is repeated
in the upper (respectively lower) half dictionary until a portion of dictionary containing a
single word is reached. A positive decision is drawn if this word is the searched word x,
otherwise x is not in the dictionary.
2 Actually,a more elementary operation would be the comparison of letters, or even that of bits, but we keep
with this one for obvious reasons.
i i
i i
i i
i i
74 Complexity of an algorithm
In the case of this algorithm, there are neither best, nor worst situations. As a matter of
fact, the number of comparisons (of words) depends only on the size n of the dictionary
DIC, not on its contents. The size of search area is repeatedly divided by two and we will
admit that the number of comparisons is in the order of ⌊log2 (n)⌋, the greatest integer
less than or equal to log2 (n) (we come back on this statement later). If we admit that the
average complexity of RechDict1 is linear, RechDict2 performing a logarithmic number of
comparisons is better, as expected.
For a dictionary of English language, n is close to 200 000 and the number of compar-
isons of RechDict2 (⌊log2 (n)⌋) is 16.
Let us remark that the variant of RechDict2 where the alternative distinguishes the
equality of x and T [mil] (and the program stops), may require a single comparison. How-
ever, it is convenient to notice that: (i) the favorable configuration differs from that for
RechDict1 and (ii) one more comparison is performed at each iteration step and in the
worst case the number of comparisons becomes 2 · ⌊log2 (n)⌋.
i i
i i
i i
i i
Reminders 75
• 2n (exponential complexity), • nn .
One could try to write formulas of type fA (n) ∈ O(n2 ) meaning (with some precautions
that will be explicited) that fA (n) does not grow more rapidly than n2 when n increases.
However, this first attempt would be very restrictive since, for instance, fA (n) = n2 /2 +
3n/2 + 1 or fA (n) = 2n2 − 1 would not comply with the definition. Hence, the meaning of
fA (n) ∈ O(n2 ) is revised so that the two preceding examples become acceptable. For the
first one, it will be said that fA (n) does not grow more quickly than the reference function
(here n2 ) when n increases, from a given rank n0 . Thus, it is possible to write (n2 /2 + 3n/2 +
1) ∈ O(n2 ), since from n0 = 4, it is true that (n2 /2 + 3n/2 + 1) < n2 . However, it is still
illegal to write (2n2 − 1) ∈ O(n2 ) since for any n > 1 : (2n2 − 1) > n2 . Yet, intuition tells
that the order of growth is the same for both (2n2 − 1) and n2 , and it seems consistent to
say (2n2 − 1) and n2 grow the same way. Last, we say that fA (n) ∈ O(n2 ), if there is a
constant C and an integer n0 from which the inequality fA (n) ⩽ C · n2 holds. Eventually,
the following definition is adopted. Let g be a function: N → R+ . We call maximum order of
growth O of g the set:
b {t : N → R+ | ∃(C, n0 ) · (C ∈ R+ and n0 ∈ N and ∀n·
O(g) =
((n ∈ N and n ⩾ n0 ) ⇒ t(n) ⩽ C · g(n)))}.
According to this definition, (n2 /2 + 3n/2 + 1) ∈ O(n2 ), as well as (2n2 − 1) ∈ O(n2 )
hold. Since (2n2 − 1) ∈ O(n2 ), (2n2 − 1) ∈ O(n3 ) also holds. In practice, we look for the
smallest reference function rf such that fA (n) ∈ O(rf(n)). Once the set O(g) of the functions
which grow at most as quickly as g (now with a precise meaning) has been defined, it is
legitimate to define similarly the set Ω(g) of the functions which grow at least as quickly
as g. The two notions O(g) and Ω(g) allow to provide upper and lower bounds for the
behavior of an algorithm.
We call minimum order of growth of g the set:
Last, we call exact order of growth of g the set Θ(g) defined by the intersection of O(g)
and Ω(g):
Interesting result
Let A be an algorithm made of two consecutive parts A1 and A2 , whose respective
complexities are such that fA1 (n) ∈ O(f1 (n)) and fA2 (n) ∈ O(f2 (n)); then fA (n) ∈
max({O(f1 (n), O(f2 (n))}). In other words, the maximum order of growth of an algorithm is
given by that of its part of highest maximum order of growth (see problem 23, page 79).
i i
i i
i i
i i
76 Complexity of an algorithm
Remarks
1. f ∈ O(1) means that from a given rank n0 there is a constant C such that f(n) ⩽ C.
2. The complexity function fA (n) of any algorithm A is such that fA (n) ∈ Ω(1).
3. For any integer a ⩾ 2, one has: O(loga (n)) = O(log2 (n)) and Θ(loga (n)) = Θ(log2 (n))
since loga (n) = log2 (a) · log2 (n). In general, log2 (n) is taken as a reference function.
4. Stirling formula n n
√
n! ≈ 2πn ·
e
allows to write (by taking the logarithm of each member) that log2 (n!) ∈ Θ(n ·log2 (n)).
5. An order of growth is not a limit. For instance, f(n) = n2 · (2 + sin2 (n)) ∈ Θ(n2 ) but it
does not have a limit when n tends toward infinity. Moreover, functions concerned by
orders of growth are not from R to R, but from N to R+ since the size of data manipu-
lated in a program is an integer and a complexity is positive by nature.
X
n X
i−1
n · (n + 1)
1=
2
i=1 j=0
thus in Θ(n2 ),
• the calculation of a Delannoy number of order (m, n) given by the recurrence in page
14, whose complexity in terms of additions is expressed as:
X
n X
m
2=2·m·n
i=1 j=1
X
n X
j−1
(n − 1)(n − 2)
1=
2
j=2 i=2
thus in Θ(n2 ),
• algorithm RechDict1 which is in O(n) comparisons,
i i
i i
i i
i i
Reminders 77
nbStepMax(1) = 1 j n k
nbStepMax(n) = 1 + nbStepMax n>1
2
whose solution is nbStepMax(n) = ⌊log2 (n)⌋. The maximum number of comparisons (of
words) is thus 2 · ⌊log2 (n)⌋ + 1; this algorithm is in O(log2 (n)).
This latter example highlights the central role (very often) of recurrence relations for
the evaluation of complexity. They are used intensively, in particular for the complexity of
recursive algorithms in chapters 4 and 8.
i i
i i
i i
i i
78 Complexity of an algorithm
an instruction computer run-time of 1µs. For example, in an hour, the size of the problem
that can be dealt with by an algorithm in n3 is 1 500. An “astronomic” size is greater than
the estimated number of atoms in the universe (1080 ).
For the same instruction run-time (1µs), the following array gives time necessary for an al-
gorithm, whose exact complexity appears in columns, to with data whose size is indicated
in rows. For example, a program in n2 can deal with a problem of size 1 000 in one second.
An “astronomic” time is greater than one trillion years.
efficient than A1 to produce the desired result. In contrast, when N is a reasonable (i.e. a
rather small) amount (which is often the case in concrete applications), A2 is better than
A1 .
Algorithms like A2 , whose type of complexity is in Θ(N · P(n)), where P(n) is a poly-
nomial in n, and where N depends on the data, are said pseudo-polynomial. Of course, they
can be studied and used, but we must keep in mind that their run-time depends directly
and critically on the data of the considered problem.
i i
i i
i i
i i
Problems 79
Final remark
For some problems, data size can be evaluated as a function of several parameters, not a
single one. For example, in chapter 9 we will see the “Choosing skis” problem, where each
of the n skiers must receive the best pair of skis (among m). n and m are independent
values, except the condition m ⩾ n. The order of growth of the best algorithm known
for this problem is O(n · m). Therefore, it is impossible to characterize its complexity on
the basis of a single parameter: in such a case, the size of the problem is basically multi-
dimensional and the order of growth is expressed as a multiple variable polynomial.
2.2 Problems
Problem 22. About some reference functions ◦
◦ •
This problem aims at deciding whether “close” reference functions characterize (or not) the
same order of growth.
1. 2n+1 ∈ O(2n )
2. (n + 1)! ∈ O(n!)
3. f(n) ∈ O(n) ⇒ (f(n))2 ∈ O(n2 )
4. f(n) ∈ O(n) ⇒ 2f(n) ∈ O(2n )
5. nn ∈ O(2n ).
In this problem, an interesting property is established. It is related to the sum of two functions
whose maximum or exact order of growth is known. This result is useful in practice to deter-
mine the maximum or exact order of growth of a program obtained by sequential composition
of several components.
∀n · (n ⩾ n0 ⇒ f1 (n) ⩽ f2 (n)),
i i
i i
i i
i i
80 Complexity of an algorithm
23 - Q 1 Question 1. Demonstrate that if g(n) ∈ O(f1 (n)) and h(n) ∈ O(f2 (n)) then g(n) +
h(n) ∈ O(f2 (n)).
23 - Q 2 Question 2. Prove that if g(n) ∈ Θ(f1 (n)) and h(n) ∈ Θ(f2 (n)) then g(n) + h(n) ∈
Θ(f2 (n)).
The solution is on page 84.
The main objective of this problem is to prevent from drawing hasty conclusions when dealing
with orders of growth.
Very often, the order of growth of an algorithm is expressed as a polynomial. In this problem,
it is shown that a simplified version is sufficient to express the order of growth.
f(n, k) = 1k + 2k + · · · + nk ∈ Θ(nk+1 ).
i i
i i
i i
i i
Problems 81
In problem 23, page 79, we have seen a property of the sum of two complexity functions. To
extend it to a multiple sum seems legitimate, but beware of confusing the image of a function
with the sum of functions.
X
n
i = (1 + 2 + · · · + n) ∈ O(n2 ).
i=1
X
n
n · (n + 1)
i= .
2
i=1
Yet:
X
n
i ∈ O(1 + 2 + · · · + n)
i=1
and
O(1 + 2 + · · · + n) = O(max({1, 2, . . . , n})) = O(n).
Hence:
n · (n + 1)
∈ O(n).
2
Where is the flaw?
The solution is on page 87.
The algorithm hereafter, close to that developed for the sequential search in a dictio-
nary, looks for the value x in the array T of integers where the first n elements are distinct,
the last one acting as a sentinel (its value is precisely x). The result returned is the rank of
x when x is in T [1 .. n], (n + 1) otherwise.
1. constants
2. x ∈ N1 and x = . . . and n ∈ N1 and n = . . .
3. variables
4. T ∈ 1 .. n + 1 → N1 and T = . . . and i ∈ N1
5. begin
6. i ← 1 ; T [n + 1] ← x;
7. while T [i] ̸= x do
8. i←i+1
9. end while;
i i
i i
i i
i i
82 Complexity of an algorithm
10. write(i)
11. end
27 - Q 1 Question 1. Give the minimum and maximum complexity of this algorithm, in terms
of comparisons.
27 - Q 2 Question 2. The following probabilistic hypothesis is made: (i) the integer values in
the array are drawn equi-probably between 1 and N, with N ⩾ n and (ii) x is drawn equi-
probably between 1 and N as well. What is the average complexity of the algorithm?
The solution is on page 87.
This problem shows how two strategies a priori analogous can produce algorithms of very
different complexity. Ultimately, a solution with linear complexity is expected, but also an
upper bound of the constant of proportionality, which is rather unusual.
We are in front of a river with a dense fog. We know that there is a ford in the neigh-
borhood, but we ignore if it is located on the left or on the right and at which distance
(unbounded a priori). With this fog, the entrance of the ford can be seen only when we are
just in front of it. How to proceed to cross the river?
We must successively explore left and right ways, while increasing the distance trav-
eled at each direction change. Starting on the left or on the right does not matter, but both
sides must be considered in a “balanced” fashion and the distance must be steadily in-
creased so as to avoid to walk too far in the wrong way (where there is no ford).
A first method consists in walking one step on the right, coming back to the starting
point, walking one step on the left, coming back to the starting point, walking two steps
on the right, coming back to the starting point, walking two steps on the left, coming back
to the starting point, walking three steps on the right, and so on until the ford is reached,
according to the following schema:
Let us suppose that the ford is situated 15 steps on the left. To reach it, the number of
steps walked in total is 465, more than 30 times the 15 strictly necessary steps.
More generally, let us denote by n the distance (in steps) between the starting point and
the ford, i.e. the minimum number of steps necessary to reach the ford.
28 - Q 1 Question 1. Give the number of steps walked with the proposed method when the
ford is located n steps on the left (respetively right) away from the starting point. What is
the class of complexity of this method in terms of steps traveled? One would like to find
a basically more efficient method (in the sense of class of complexity) ensuring that the
ford is reached with less than 9n steps. The shortcoming of the previous method lies in
a too “wise” increase in the number of steps. Adding a single step each time (arithmetic
progression) is finally costly and one imagines to double the number of steps (geometric
progression), which is reflected by the schema below:
i i
i i
i i
i i
Solutions 83
8 4 2 1 1 2 4 8 16
Question 2. Give the number of steps walked depending on whether the ford is lo- 28 - Q 2
cated 9 (respectively 15) steps away from the starting point on the left or on the right.
Conclude.
Question 3. Check that, with a progression according to the powers of 3 (instead of 2), 28 - Q 3
the objective (in terms of steps walked) is not met.
Question 4. Modify the method proposed in the second question, still progressing us- 28 - Q 4
ing the powers of 2, so that the constraint on the number of steps walked is met. It is asked
to give the maximum number of steps walked as well as the minimum one, depending on
n, the distance between the starting point and the ford.
The solution is on page 88.
2.3 Solutions
Answers to problem 22. About some reference functions
The problem is on page 79.
i i
i i
i i
i i
84 Complexity of an algorithm
Answers to problem 23. About orders of growth The problem is on page 79.
i i
i i
i i
i i
Solutions 85
∀n · (n ∈ N1 ⇒ (1 · n3 ⩽ f(n) ⩽ 18 · n3 ))
and thus f(n) ∈ Θ(n3 ).
As to g(n), 3n2 − 6n + 9 has a positive value for any n ∈ D (and even for any n ∈ N).
Therefore, for n ∈ D, g(n) ⩽ n3 . Moreover:
n3 n3
g ′ (n) = g(n) − =2· − 3n2 + 6n − 9
3 3
is a function taking positive values (not necessarily integers) for any n ∈ D, hence g(n) ⩾
n3 /3. Eventually, we have established that for n ⩾ 3:
1
· n3 ⩽ g(n) ⩽ 1 · n3
3
thereby g(n) ∈ Θ(n3 ).
Answer 2. Here again, we will try to under and over estimate f by a polynomial. Let- 25 - A 2
ting g(n) = ap /2 · np + ap−1 · np−1 + · · · + a1 · n + a0 , we can write:
ap
f(n) = · np + g(n).
2
Let us examine g(n). If c denotes the largest of the values |ai | for i ∈ 0 .. p − 1, one has:
g(n)
= definition
ap p p−1
· n + ap−1 · n + · · · + a1 · n + a0
2
⩾ arithmetics
ap p
· n − c · (np−1
+ · · · + n + 1)
2
⩾ value of the geometric series for n ̸= 1
ap c
p
·n − · (n − 1)
p
2 n−1
> arithmetics
ap p c p
·n − ·n
2 n−1
= arithmetics
ap c
p
n · − .
2 n−1
i i
i i
i i
i i
86 Complexity of an algorithm
This latter expression is positive for n ⩾ n0 = 2 + (2c/ap ) and we can conclude that:
ap
∀n · n ∈ D and n ⩾ n0 ⇒ f(n) ⩾ · np .
2
Let us now try to find a polynomial overestimating f. Let b be the largest of the values |ai |,
for i ∈ 0 .. p. One has:
f(n, k) = 1k + 2k + · · · + nk ⩽ n · nk = nk+1 .
Furthermore:
f(n, k) = 1k + 2k + · · · + (n − 1)k + nk
1k 1k 2k 2k (n − 1)k (n − 1)k nk nk
= + + + + ··· + + + +
2 2 2 2 2 2 2 2
1k + 1k + 2k + 2k + · · · + (n − 1)k + (n − 1)k + nk + nk
=
2
1 + n + 2 + (n − 1) + · · · + (n − 1)k + 2k + nk + 1k
k k k k
= .
2
Using formula 2.1, page 80, it comes:
k k ! n n + 1 k
1 n+1 n+1
f(n, k) ⩾ + ··· + =
2 2 2 2 2
nk+1
⩾ .
2k+1
i i
i i
i i
i i
Solutions 87
Finally:
1
∀n · n ∈ N1 ⇒ ·nk+1
⩽ f(n, k) ⩽ 1 · nk+1
2k+1
which confirms that for k ∈ N and n ∈ N1 , one has:
f(n, k) ∈ Θ(nk+1 ).
Answers to problem 26. Order of growth: paradox? The problem is on page 81.
Answer 1. One has: 26 - A 1
X
n
n(n + 1) n2 n
= 1 + 2 + ··· + n = = +
2 2 2
i=1
Pn
therefore i=1 = 1 + 2 + · · · + n ∈ O(n2 ).
Remark
We could have used the result established in the third question of the preceding problem
by taking k = 1 for f(n, k).
Answer 2. The reasoning carried out operates on the image of the function and not 26 - A 2
on the function itself. As a matter of fact, the decomposition of the considered function in
terms of a sum of functions yields:
X
n ∞
X
f(n) = i= fi (n)
i=1 i=1
objects come matters. For example, there are 60 distinct arrays when N = 5 and n = 3.
i i
i i
i i
i i
88 Complexity of an algorithm
(N − n)(N − 1)!/(N − n)! arrays remain where x cannot be found for which (n + 1) com-
parisons take place. Thus, the average number of comparisons is:
! !
1 Xn
(N − 1)! (N − n)(N − 1)! n
i + (n + 1) = (n + 1) 1 − .
N!
(N−n)!
(N − n)! (N − n)! 2N
i=1
In particular, for N = n, there are ((n+1)/2) comparisons in average. When N/n increases,
the number of comparisons tends to (n + 1).
Answers to problem 28. The ford in the fog The problem is on page 82.
28 - A 1 Answer 1. Generally speaking, when the ford is located n steps on the left away from
the starting point, the number of steps required by the suggested method is:
X
n−1
4· i + 3n = 4(n(n − 1))/2 + 3n = 2n2 + n.
i=1
i i
i i
i i
i i
Solutions 89
Answer 4. The idea is to adopt the following schema, where the symmetry (left/right) 28 - A 4
is broken:
8 2 1 4 16
In contrast to the previous two methods, the actual position of the ford on the left side is
not a disadvantage. As a matter of fact, when the ford is 5 steps on the left, we have to
walk (1 + 1) + (2 + 2) + (4 + 4) + 5 = 19 steps, whereas when it is 5 steps on the right
(1 + 1) + (2 + 2) + (4 + 4) + (8 + 8) + 5 = 35 steps are necessary. In both cases, the number
of steps is less than 10 · 5 = 50, which bodes well.
Let us evaluate the number N of steps to walk when the ford is located on the left of the
starting point. When the ford is one (respectively two) steps on the left, it is reached with
three (respectively four) steps and the constraint is met since 3 < 10 · 1 and 4 < 10 · 1. When
it is located at a distance n greater than two steps, one has:
yet:
22p−1
< 1. (2.2)
n
Relying on the schema describing the move strategy, the number of steps N is:
In effect, we walk back and forth alternatively on the left and on the right until the ford is
not reached. It comes:
N
= formula 2.3
2(20 + 21 + · · · + 22p ) + n
= sum of a geometric series
2(22p+1 − 1) + n
= arithmetics
8 · 22p−1 + n − 2
= arithmetics with n > 0
22p−1
n · (8 · + 1) − 2
n
< formula 2.2
9n − 2.
i i
i i
i i
i i
90 Complexity of an algorithm
The same result is obtained when the ford is located n steps to the right of the starting
point (we study the values of n between two even powers of 2 after treating the case n = 1
separately, for which we have N = 1).
Complementary study
We will now show that, if we stick to geometric progressions, choosing the reason 2 is
optimal. To this end, we choose a continuous rather than discrete frame and we evaluate
distances, no longer in number of steps, but in divisible units, such as the meter. It is there-
fore considered that the ford is at a distance of n from the starting point, where n is this
time a positive real number. If we explore on the side of the ford and turn back after having
walked a length strictly less than n, the ford is by definition not yet reached.
Let us denote by E (real over 1.0) the reason for the geometric progression. So, the strategy
consists in making 1.0 meter on the right, E meters on the left, E2 meters on the right, etc.
We will assume that the ford is on the right at a distance of 2.0 meters or more, but it does
not matter as we have seen before. Let us look at the worst and the best cases, from the
point of view of the N/n ratio, where N is the distance (this time in meters) walked before
finding the ford.
For example, let E = 3.0 and n = 9.01. First we go one meter to the right, then we go
back to the starting point (another meter), then we go to the left at the distance E = 3.0,
we go back to the starting point (so far we have covered seven meters). We will now go
nine meters to the right and just miss the ford by one centimeter. We turn back on the
nine meters (provisional total: 25.0), we go back and forth to the left and we come back
to the starting point for a total of (25.0 + 2 · 27.0) = 79.0 meters. Only 9.01 meters to go
and we will reach the ford. We then covered a total distance of N = 88.01 meters, with a
ratio N/n = 9.768 · · · . Now imagine that the ford was not at n = 9.01 meters, but at ten
meters. We would have walked N = 89.0 meters, for a ratio N/n of 8.9, which would have
been better than the previous one. The further the ford would have been to the right, at a
distance less than or equal to 81.0 meters, the more this ratio would have decreased. The
ford is here on the right, at a distance n such that E2 < n ⩽ E4 . Generally speaking, if it is
on the right, there is an integer p such that E2p < n ⩽ E2p+2 and the worst case (the one
that maximizes the ratio N/n) is when n = E2p + ϵ with ϵ as small as desired. The best
case is when n = E2p+2 . The proof of validity of both statements is left to the reader.
i i
i i
i i
i i
Solutions 91
E2p (2E2 + E − 1) + E − 1 2
N = 2(1 + E + E2 + · · · + E2p+1 ) + E2p + ϵ = − + ϵ.
E−1 E−1
N can be rewritten as:
2E2 + E − 1 2p E2 + 1 2E2 + E − 1 E2 + 1
N= (E + ϵ) − 2ϵ = n − 2ϵ .
E−1 E−1 E−1 E−1
So we can see that N is linearly related to n.
What is the best value of E to minimize this distance in the worst case? Deriving the term
(2E2 + E − 1)/(E − 1), we see that it is minimum for E = 2.0 and in this case: N = 9n − 10ϵ.
We assume that the ford is on the right at a distance n ⩾ 2.0. In the best case (n = E2p ), the
number of steps is:
E+1 2
N = 2(1 + E + E2 + · · · + E2p−1 ) + E2p = n− .
E−1 E−1
We can see that N is also in linear relation with n and for E = 2 we have: N = 3n − 2.
Note that replacing E by E/(E−1) in the coefficient (2E2 +E−1)/(E−1) leaves this coefficient
unchanged. This results in identical limit values (L) of N/n, confirmed by the experiments
carried out by the authors, an excerpt of which is given in the table below:
E 1.2 1.25 1.4 1.5 1.8 2 2.25 3 3.5 5 6
L 15.4 13.5 10.8 10 9.1 9 9.1 10 10.8 13.5 15.4
i i
i i
Taylor & Francis
Taylor & Francis Group
http://taylorandfrancis.com
i i
i i
3
Specification, invariants, and iteration
M. Kundera
This chapter illustrates the principle of reasoned development of loops. It could seem at
first sight that writing a loop is a straightforward task, but every programmer knows how
tricky it can be. The logical approach that we propose here applies to a variety of problems
and reveals the interest of its systematic and thorough nature. Several problems in Chapter
8 call also on loops and will supplement those proposed here. The main objective is to
equip the reader with strong bases about the construction of loops by invariant, however
without entering in too many sophisticated details.
DOI: 10.1201/b23251-3 93
i i
i i
i i
i i
1. First of all, the conjunction of the invariant and the stopping condition leads to the
desired goal, which can be formalized by:
(a) preserve the invariant. More precisely, the progression is a fragment of program de-
fined by the precondition “invariant and not stopping condition” and the postcon-
dition “invariant”. Here, the assertion is that the invariant holds before and after
the progression is carried out. Of course, one must not conclude that the invariant
holds during the whole execution of the progression.
(b) strictly decrease the termination expression. More precisely, in looping situation
(i.e. when the predicate “invariant and not stopping condition” holds), the (inte-
ger) value of the termination expression after one progression step is positive or
zero and strictly less than its previous value. Thus, the stopping condition will be
met after a finite period of time, which ensures that the program finishes.
3. The initialization must establish the invariant. It is a piece of program whose precondi-
tion is that of the problem to be solved and whose postcondition is the invariant.
It is worth noticing that the first two components (invariant and stopping condition)
relate to situations while the next two (progression and initialization) are actions. Items 1, 2
and 3 clearly show that the invariant plays a central role since it appears in items 1, 2-a, 2-b
and 3. It constitutes the cornerstone of the construction of loops, in other terms the glue
which links the other components together. Hence, the development of a loop begins with
the identification of the invariant.
Figure 3.1 summarizes the aspects discussed earlier.
The encoding of the corresponding generic loop is as follows:
1. initialization;
2. while not stopping condition do
3. progression
4. end while
In this “minimal” notation, precondition, postcondition, invariant and termination ex-
pression do not appear. The last two elements are widely addressed in the design phase
and, in general, only the fist two are featured in the code as comments (introduced by the
keywords PRE and POST ).
i i
i i
i i
i i
precondition postcondition
of the loop of the loop
and
initialization
establishes
stopping
invariant
condition
and
not
progression
preserves
Precondition: (A ∈ N) and (B ∈ N1 ).
Postcondition: q is the quotient and r is the remainder of the division of A by B.
In order to make the postcondition “usable” (this point will be developed later), it is
reformulated on the basis of the definition of the Euclidian division by:
(A = B · q + r) and (0 ⩽ r)
and as stopping condition: r < B. The actions related to the progression and the initializa-
tion remain to be expressed, as well as the termination expression. As to the progression,
it suffices to increment q of 1 and to decrement r of the value of B to restore the invariant
(which is possible since the stopping condition is not met, hence r ⩾ B). The invariant is
established from the precondition by the assignments: 0 to q and A to r. Concerning the
termination expression, it can be observed that the expression (A − q · B) is equal to A
after the initialization takes place and diminishes of B whilst being positive after each step
i i
i i
i i
i i
of the progression (it is possibly zero after the last iteration step). On the basis of the five
components pointed out on the one hand, and the generic code on the other hand, the fol-
lowing program is deduced:
1. constants
2. A ∈ N and A = . . . and B ∈ N1 and B = . . .
3. variables
4. q ∈ 0 .. A and r ∈ 0 .. B − 1
5. begin
6. /% PRE: (A ∈ N) and (B ∈ N1 ) %/
7. q ← 0; r ← A;
8. while not(r < B) do
9. q ← q + 1; r ← r − B
10. end while;
11. /% POST: (A = q · B + r) and (r ⩾ 0) and (r < B) %/
12. write(the quotient of the division of , A, by , B, is , q, and the remain-
der is , r)
13. end
It can be noticed that when A = 0, the “while” loop is not entered (it is the only case
indeed). Moreover, when A is a multiple of B, the remainder r is 0.
i i
i i
i i
i i
Useful techniques 97
We want to elaborate a solution involving a single loop and where the array T is not nec-
essarily entirely read. A brief analysis shows that two cases may occur:
• the array T involves a single copy of its minimum which turns out to be T [K], which
requires the complete scan of T ,
• T [K] is not the minimum value of T (a value strictly less than T [K] is encountered and
the scan of T can stop), or T [K] is indeed the minimum of T and another value (T [i], i ̸=
K) equal to T [K] is encountered, and once again the scan of T can stop).
In order to facilitate the design of a solution, in a first time, the variable infk is ignored
and the following new postcondition is taken into consideration:
Postcondition: i is the lowest index of the interval 1 .. N different from K such that T [i] ⩽
T [K] if it does exist, (N + 1) otherwise
which stands for an intermediary situation (in the sense of sequential composition); the
following approach is thus envisaged:
Precondition: i is the index of 1 .. N different from K such that T [i] ⩽ T [K] (if such an i
exists), (N + 1) otherwise.
Postcondition: infk = (T [K] is less than all other elements inT ).
The code related to C OMP PART consists in assigning the value of the relational expres-
sion (i = N + 1) to infk. As to that of L OOP, it relies on the following five components:
It is easy to check that: (i) the conjunction of the invariant and the stopping condition en-
tails the postcondition, (ii) the progression preserves the invariant, (iii) the termination
expression decreases at each step whilst being nonnegative, and (iv) the initialization es-
tablishes the invariant, in other words that the relationships 1, 2-1, 2-2 and 3 are met. Even-
tually, the following program is built:
1. constants
2. N ∈ N1 and N = . . . and T ∈ 1 .. N → N and T = [. . .] and K ∈ 1 .. N and K =
...
3. variables
i i
i i
i i
i i
4. i ∈ 1 .. N + 1 and infk ∈ B
5. begin
6. /% first part: L OOP %/
7. /% PRE: (T is a constant array of N integers) and (N ⩾ 1) and (K
constant) and (K ∈ 1 .. N) %/
8. i ← 1;
9. while not((i = N + 1) or else ((i ̸= K) and (T [i] ⩽ T [K]))) do
10. i←i+1
11. end while;
12. /% POST: i is the index of 1 .. N different from K such that T [i] ⩽ T [K] (if such
an i exists), (N + 1) otherwise %/
13. /% second part: C OMP PART %/
14. infk ← (i = N + 1);
15. if infk then
16. write(the element whose index is, K, in the array, T , is its unique
minimum)
17. else
18. write(the element whose index is, K, in the array, T , is not its unique
19. minimum)
20. end if
21. end
i i
i i
i i
i i
i i
i i
i i
i i
It is then possible to breakup the postcondition and to apply the suggestions made above
to divide it into two parts, the first one being the invariant and the second one the stopping
condition:
1. Invariant The first two conjuncts are easy to establish and thus taken for the invariant:
1 i N
T
̸= 0
The conjunct (T [i] = 0) has been discarded. It is indeed a predicate which is difficult to
establish since it demands the localization of a zero!
2. Stopping condition The discarded conjunct is chosen, i.e. T [i] = 0. It can be noticed that
this predicate involves no quantifier which makes it possible to integrate its negation
into the loop condition.
3. Progression It is specified by:
A possible idea for the progression is to move i one position to the right by the assign-
ment: i ← i + 1. The invariant is fulfilled by the new situation since there is no zero in
T [1 .. i − 1] and that there is necessarily one after T [i − 1] (according to the precondition)
hence i ⩽ N and i ∈ 1 .. N.
4. Initialization It is specified by:
Moving from the precondition to the invariant, means that the following situation is
reached:
1/i N
T
i i
i i
i i
i i
1. constants
2. N ∈ N1 and T ∈ 1 .. N → N and T = [. . .]
3. variables
4. i ∈ 1 .. N
5. begin
6. /% PRE: (T is a constant array of N integers) and (there is at least one zero
in the array T ) %/
7. i ← 1;
8. while not(T [i] = 0) do
9. i←i+1
10. end while;
11. /% POST: (i ∈ 1 .. N) and (T [1 .. i − 1] contains no zero) and (T [i] = 0) %/
12. write(the index of the leftmost zero in , T , is , i)
13. end
In the best case, this algorithm is in Θ(1) and at worst it is in Θ(N) in terms of comparisons.
In section 3.7, several problems are proposed in which the initial postcondition is not
expressed in a conjunctive form. In such a situation that occurs very frequently in prac-
tice, the postcondition must first be turned into a “constructive” form, i.e. expressed as a
conjunction which is to be broken up.
i i
i i
i i
i i
1 i k N
T White ? Red
• The initial situation where the content of T is unknown (neither white, nor red element
localized), with i = 1 and k = N. As a matter of fact, the above formula which thus
writes:
is evaluated to true and it expresses that nothing is known about each of the elements
of T ,
• The final situation where all elements are localized (white elements on the left, red ones
on the right), with k = i − 1,
• A situation where there is at least one red element and no white one, with i = 1 and
0 ⩽ k < N,
• A situation where there is at least one white element and no red one, with 1 < i ⩽ N+1
and k = N,
• The case where T is empty (N = 0).
2. Stopping condition The loop terminates when k = i − 1. It has been pointed out (see
item 3.4.2) that then the conjunction of the invariant and the stopping condition entails
the postcondition.
3. Progression The action to undertake in the progression depends on the color of T [i]. If
T [i] is white, i is incremented by 1 (which extends the zone containing white elements)
and if T [i] is red, it is exchanged with T [k] and k is decremented by 1 (which enlarges
the zone involving red elements).
4. Initialization Operations related to the initialization have been evoked in item 3.4.2,
and they come down to two assignments: i ← 1 and k ← N.
5. Termination The expression (k−i+1) is suitable since it is equal to N after initialization,
it decreases by 1 at each iteration step and its value is zero when the stopping condition
is met.
i i
i i
i i
i i
1 i k N
T White Red ?
Fig. 3.3 – Another situation related to the hypothesis of the work carried out partly.
(P and B) ⇒ R.
It has been suggested to reformulate the postcondition by introducing one (or sev-
eral) variable(s) in order to make a conjunction appear. In doing so, we have strengthened
the initial postcondition by an auxiliary postcondition which entails it. However, it may
happen that, for necessity reasons or by opportunity, the strengthening of the postcondi-
tion appears only during the development phase. In such cases, the strengthening of the
postcondition is often expressed indirectly by the strengthening of the invariant. Thus, an
additional conjunct P′ is associated with the “natural” invariant so as to either ensure the
progression, or express a stopping condition. More formally, we have:
(P and P′ and B) ⇒ (P and B)
⇒ one has either (P and B) = R, or at worst (P and B) ⇒ R
(P and P′ and B) ⇒ R.
i i
i i
i i
i i
1 m N
T
X
m−1
s= T [j]
j=1
More formally, making the domain of the variables explicit, the postcondition is rewritten:
X
m−1
(m ∈ 1 .. N) and (T [m] = maxj∈1..N (T [j])) and (s ∈ Z) and s = T [j].
j=1
First attempt
The postcondition is strengthened so as to obtain a conjunction on the basis of the follow-
ing situation:
1 m i N
T
X
m−1
s= T [j]
j=1
i i
i i
i i
i i
First, let us examine the variation domain of variables i, m and s. So that m takes a
value, the array T [1 .. i − 1] must be nonempty, which entails that i is not equal to 1. Hence,
i is varying in the interval 2 .. N + 1, whereas m ∈ 1 .. i − 1 and s ∈ Z. Adding this
information, we get:
(i ∈ 2 .. N + 1)
and (m ∈ 1 .. i − 1) and (T [m] = maxj∈1..i−1 (T [j])) and
X
m−1
(s ∈ Z) and s = T [j].
j=1
Second attempt
The invariant (and indirectly the postcondition) is strengthened by the addition of the
X
i−1
conjunct v = T [j].
j=1
1. Invariant It becomes:
i i
i i
i i
i i
graphically:
X
i−1
(T [m] = max (T [j])) and v = T [j]
j∈1..i−1
j=1
1 m i N
T
X
m−1
s= T [j]
j=1
If i is the position of the new maximum in T [1 .. i], s takes the value of v. The variables
m and v are then updated, T [i] is added to v and i is incremented by 1.
4. Initialization The initialization is specified by:
Precondition: (T is a constant injective array of N integers) and (N ⩾ 1).
I NITIALIZATION
Postcondition: (i ∈ 2 .. N + 1) and (m ∈ 1 .. i − 1) and (T [m] = maxj∈1..i−1 (T [j])) and
P Pi−1
(s ∈ Z) and (s = m−1
j=1 T [j]) and (v ∈ Z) and (v = j=1 T [j]).
The value 2 is assigned to i, which enforces other variables to comply with the follow-
ing constraints:
(s = T [1]) and (v = T [1]) and (m = 1).
4. Termination The variable i is incremented at each step of the progression. The expres-
sion (N + 1 − i) is suited to ensure the termination.
1. constants
2. N ∈ N1 and N = . . . and T ∈ 1 .. N → Z and T = [. . .]
3. variables
4. i ∈ 1 .. N + 1 and m ∈ 1 .. N and v ∈ Z and s ∈ Z
5. begin
6. /% PRE: T is a constant injective array of N integers) and (N ⩾ 1)) %/
7. i ← 2; s ← T [1]; v ← T [1]; m ← 1;
8. while not(i = N + 1) do
i i
i i
i i
i i
3.5.1 An example
We want to know whether the sum of the elements of the constant array T [1 .. N] is greater
than a given value S, or not.
We want to build the program specified by:
The presence of a quantification suggests that its evaluation as such will raise a difficulty
and we proceed to a second strengthening with the introduction of the variable ps calcu-
lating the partial sum of the first (i − 1) elements of T , hence:
Pi−1
Postcondition: (i ∈ 1 .. N + 1) and (ps = j=1 T [j]) and (sgs = (ps > S)) and (i = N + 1).
1. Invariant The first three conjuncts are easy to establish and they serve for the invariant:
X
i−1
(i ∈ 1 .. N + 1) and ps = T [j] and (sgs = (ps > S)).
j=1
i i
i i
i i
i i
We can observe that the algorithm could stop as soon as sgs turns to true, which could di-
minish the number of iterations, thus complexity at worst. This remark leads to the modi-
fication of both the stopping condition and the progression in the preceding development.
The stopping condition is modified accordingly and a new loop is built.
1. constants
2. N ∈ N and N = . . . and T ∈ 1 .. N → N and T = [. . .] and S ∈ N1 and S = . . .
3. variables
4. i ∈ 1 .. N + 1 and sgs ∈ B and ps ∈ N
5. begin
6. /% PRE: (T is an array of N natural numbers) and (N ⩾ 0) and (S constant) and (S ∈
N1 ) %/
7. i ← 1; sgs ← false; ps ← 0;
i i
i i
i i
i i
i i
i i
i i
i i
3.7 Problems
Problem 29. White and red beans ◦
◦ •
This famous problem by D. Gries [15] highlights the fact that it is possible to reason about a
given algorithm (or program) by identifying its invariant.
A can contains a number W of white beans and R of red beans (W + R ⩾ 1). We are
provided with a reserve of red beans which suffices to perform the following operation
while it is possible:
Two beans are randomly taken from the can
if they have the same color then
they are thrown away and one red bean is put back into the can
else
the red bean is thrown away and the white bean is put back into the can
end if
i i
i i
i i
i i
Problems 111
5. Termination: (N + 1 − i)
This problem is a simple application of the postcondition splitting principle in order to find
out an invariant, once it is appropriately reformulated to be under constructive form.
This problem is dedicated to the “basic” problem of search of a value in a bidimensional array.
A “natural” solution makes use of two loops, but it is shown that it is easy and elegant to
proceed with a single one. The proposed approach can be easily extended to a higher number
of dimensions. We will use the hypothesis of the work carried out partly.
i i
i i
i i
i i
32 - Q 1 Question 1. Propose the elements of a single loop answering this specification, on the
basis of the hypothesis of the work carried out partly.
32 - Q 2 Question 2. Write the corresponding program and give its complexity in terms of com-
parisons.
Remark
We invite the reader to build the equivalent program made of two loops so as to compare
it with the previous one, especially regarding the ease of design.
The solution is on page 129.
A sort program is now presented. Although it is not among “efficient” sorts, it is interesting
from a pedagogic point of view. Moreover, in contrast to the previous problem, it relies on two
nested loops according to an approach both simple and progressive.
The second conjunct of the postcondition expresses that the content of T does not
change but possibly the order of its elements. The exclusive use of the procedure Ex-
change(i, j) previously introduced (see section 3.4.2, page 101) guarantees the compliance
with this property. In this way, this conjunct can be definitely dropped.
The postcondition is not under constructive form and it must be strengthened:
Assuming that the work is carried out partly, we are in the situation represented here-
after:
1 i N
T
sorted
i i
i i
i i
i i
Problems 113
We can already glimpse that the progression will aim at doing so that T [1 .. i] is sorted.
We have two possible choices: i) to insert T [i] in T [1 .. i] at the right place, and ii) to keep
T [1 .. i − 1] unchanged assuming that all the values in T [i .. N] are greater than (or equal to)
those of T [1 .. i − 1]. The first option corresponds to the sort by insertion and we choose the
second one, called sort by selection, because it requires to select the smallest value in T [i .. N].
Question 1. Give the postcondition associated with this option, then specify the com- 33 - Q 1
ponents of the resulting loop, skipping the specification of the part related to the identifi-
cation of the position m of the minimum in T [i .. N].
Question 2. We have now to handle the loop corresponding to the identification of the 33 - Q 2
position m of the minimum in T [i .. N]. This fragment of program is specified by:
The array T [i .. N] is nonempty since in the context of execution of this loop, we have:
i ∈ 1 .. N + 1 and i ̸= N + 1. So, we are sure to find a minimum value in T [i .. N].
The postcondition can be schematized by:
1 i m N
T
Question 4. Write the program achieving the sort by selection of the array T [1 .. N]. 33 - Q 4
The use of the pattern proposed for bounded linear search (see section 3.5, page 107) is illus-
trated through a simple example.
i i
i i
i i
i i
34 - Q 1 Question 1. Prove that, when T represents a palindrome, the following property holds:
34 - Q 2 Question 2. Indicate why and how this problem can be solved with an adaption of the
pattern featured in section 3.5.2, page 109.
34 - Q 3 Question 3. Write the program which decides whether T stands or not for a palin-
drome.
34 - Q 4 Question 4. Give its complexity in terms of evaluated conditions.
The solution is on page 133.
This problem illustrates the use of the hypothesis of the work carried out partly. The Dutch
flag is a classical problem, so named by its author, E.W. Dijkstra, because the original version
is aimed at replenishing the colors of the flag of his country. The version dealt with here is
slightly different since natural numbers are managed instead of colors. This algorithm is at
the heart of quicksort which makes one of its major interests.
Roughly speaking, the postcondition appears as shown below (the middle zone is not
empty since it contains at least one copy of V):
1 p q N
<V =V >V q>p
i i
i i
i i
i i
Problems 115
This version of the postcondition cannot be used as such for a breakup. We will trans-
form it (strengthen): we replace the variables of existential quantification p and q by the
programming variables b and w (see section 3.3.3, page 98), hence:
At this stage, there is no evidence for a breakup and we envisage the introduction of
the variable r in association with one of the identifiers b, w and N do that a new conjunct
appears.
Question 1. Give the expression of the postcondition resulting from the association of 35 - Q 1
r with w, then the invariant for which a graphical representation is asked.
Question 2. Pursue the construction of the loop while identifying the cases where no 35 - Q 2
exchange is needed and so that at most one exchange occurs for each step of the progres-
sion.
Question 3. Write the program stemming from this construction and specify its com- 35 - Q 3
plexity in terms of exchanges.
The solution is on page 134.
This problem shows another example of use of the hypothesis of the work carried out partly.
Here, the stopping condition is worthy of a special attention.
Question 2. What can be observed when i = j ? Can we take this predicate as the 36 - Q 2
stopping condition?
Question 3. Provide the three other components of the loop. 36 - Q 3
Question 4. Deduce the complexity of the associated program, in terms of both com- 36 - Q 4
parisons and exchanges.
The solution is on page 136.
i i
i i
i i
i i
First of all, let us notice that the precondition entails that N ⩾ M. The quantifier #
denotes the count quantifier. Hence:
Postcondition: (i ∈ 1 .. N) and (#j · ((j ∈ 1 .. i − 1) and (T [j] = 0)) = M − 1) and (T [i] = 0).
Although this postcondition is under a constructive form, we may think that the presence
of a quantification will be embarrassing for the identification of an efficient invariant.
37 - Q 1 Question 1. Propose a strengthened version of the postcondition in which the quanti-
fied expression calls on the variable p.
37 - Q 2 Question 2. Build the loop on the basis of this new postcondition.
37 - Q 3 Question 3. Deduce the program associated with the loop and give its complexity in
terms of comparisons.
The solution is on page 137.
This problem illustrates the breakup of the postcondition after a sequence of strengthenings.
Let us consider an array containing as many even as odd numbers. We would like to
place each of the even (respectively odd) numbers in a position with an even (respectively
odd) index. Let us notice that when all the even numbers are correctly placed, it is the same
for the odd numbers (and conversely), hence the following specification:
As in the previous problem, evolutions of T are made via the procedure Exchange, which
gets us free from the first conjunct of the postcondition. The postcondition is not in a con-
junctive form, but it can be easily strengthened while preserving its symmetry:
i i
i i
i i
i i
Problems 117
Postcondition (second version which entails the first one): ((e ∈ 2 .. 2 · N + 2) and (e
is even) and (positions with even indexes in the interval 2 .. e − 2 contain even
values) and (e = 2 · N + 2)) or ((o ∈ 1 .. 2 · N + 1) and (o is odd) and (positions with
odd indexes in the interval 1 .. o − 2 contain odd values) and (o = 2 · N + 1)).
However, it is not yet a conjunctive form and we must proceed to a strengthening of this
version. To this aim, let:
(e ∈ 2 .. 2N + 2) and (e is even) and
P= b (positions with even indexes of the interval 2 .. e − 2
contain even values)
(o ∈ 1 .. 2N + 1) and (o is odd) and
Q= b (positions with odd indexes of the interval 1 .. o − 2
contain odd values)
Question 5. Justify the fact that it is also possible to build a loop from the following 38 - Q 5
postcondition:
(e ∈ 2 .. 2N) and (e is even) and (positions with even indexes of the interval 2 ..
e−2 contain even values) and (o ∈ 1..2N+1) and (o is odd) and (positions with
odd indexes of the interval 1 .. o − 2 contain odd values) and (e = 2N) and (o =
2N + 1).
This problem illustrates a case of a double strengthening, namely of the postcondition on the
one hand (which is traditional), of the invariant (imposed by the progression) on the other
hand. In addition, we highlight the fact that the approach proposed for the construction does
not conflict with modifications aiming at the efficiency of the resulting program.
i i
i i
i i
i i
The postcondition is not under conjunctive form; to achieve this, we introduce the variable
i in the following way:
Postcondition (version stemming from the strengthening of the previous one): (lg is the
length of the longest succession of zeros contained in the subarray T [1 .. i − 1]) and (i ∈
1 .. N + 1) and (i = N + 1).
First attempt
The preceding formulation suggests an invariant and a stopping condition:
1. Invariant The first two conjuncts are easy to establish and they are retained for the in-
variant:
(lg is the length of the longest succession of zeros contained in the subarray
T [1 .. i − 1]) and (i ∈ 1 .. N + 1).
1 i N
T 0 ········· 0
lg
Second attempt
We make the construction founded on the previous suggestion.
39 - Q 1 Question 1. Specify the new invariant.
39 - Q 2 Question 2. Taking (i = N + 1) as the stopping condition, continue the construction of
the loop (progression, initialization and termination expression).
i i
i i
i i
i i
Problems 119
Question 4. Propose and justify another stopping condition likely to improve the effi- 39 - Q 4
ciency of the loop.
The solution is on page 142.
This problem about the search for a majority element in a bag is also addressed in chapter
“Divide and conquer” (see problem 105, page 445). The solution developed here relies on
an original technique. As a matter of fact, we often exploit the proven technique based on
the strengthening of the postcondition for efficiency purposes. Here, in contrast, we will
weaken the postcondition in order to get an algorithm which is simple but which provides
only a possible solution requiring a “confirmation”. The solution obtained is concise, efficient
and elegant.
If V is an array or a bag, the expression mult(x, V) represents the multiplicity (i.e. the
number of occurrences) of x in V. We consider the bag S of N (N ⩾ 1) strictly positive
integers. S is called majority if there is an integer x such that:
N
mult(x, S) ⩾ + 1;
2
x is called the majority element of S (it is unique). The problem posed is that of the search
for the majority element in S. We would like to build a program whose specification is:
The identification of a candidate who got the absolute majority in an election or the
design of fault tolerant algorithms are possible applications of this problem.
A naïve algorithm
It is easy to specify a naïve algorithm, at best in Θ(N) and at worst in Θ(N2 ) comparisons
solving this problem (the comparison between two elements of S being the elementary
operation). An element of S is arbitrarily selected and its number of occurrences in S is
calculated. If it is not majority, another element of S is chosen, and so on until a majority
element is found or half of the elements of S are treated without finding any.
A second approach
So as to enhance complexity at worst, we envisage a three step solution: first S is refined
by the array T , then T is sorted, last a sequence of identical values of length greater than
⌊N/2⌋ is searched. The first step is in Θ(N), the second one in O(N · log2 (N)) and the last
one is linear, hence a complexity at worst in O(N · log2 (N)).
i i
i i
i i
i i
Invariant
Let S be the bag of values for which a potential majority element is searched and its multi-
set partition (according to the hypothesis of the work carried out partly) made of:
• C a bag called “ bag of bachelors” where all elements have the same value.
Example
Let S = J1, 3, 4, 1, 1, 3, 5, 2, 5, 1K and the possible configuration hereafter:
S
P R
× (1, 3) ×5 ×2
× (4, 1)
×5 ×1
× (1, 3)
C
The partition of S (in particular in the above situation) complies with the following
properties:
Property 2:
|S| = 2 · |P| + |C| + |R|.
Property 3:
If the bags R and C are empty, then S is not majority.
Property 4:
If the bag R is empty but C is not (let us call c the value present in C) then:
1. if S has a majority element, it is c,
2. if S has no majority element, nothing can be said about c (not even that c is the element with
the largest multiplicity in S).
i i
i i
i i
i i
Problems 121
In a way similar to the problem about the majority element (see problem 40, page 119), we
envisage a solution where the postcondition is weakened. The solution partly calls on the
bounded linear search (see section 3.5, page 107) and it turns out to be elegant and of linear
complexity.
In a group, a star is a person who is known by everyone and who knows nobody. We
consider a group of N (N ⩾ 1) people and we look for a star inside the group, if any.
By convention, a group made of a single person admits this person as a star. The only
authorized operation denoted by Knows(i, j) consists in choosing a person i who is asked
whether he/she knows the person j (i ̸= j) or not. The operation Knows(i, j) returns true
or false depending on the answer (mandatory and assumed to be truthful) of the person
who is questioned.
As there are N(N − 1)/2 pairs of persons, the problem can be solved, for sure, by at
most N(N − 1) operations Knows. However, we are interested in a solution requiring less
operations, if possible a (small) multiple of N.
Question 1. Prove that there is at most one star in any group. 41 - Q 1
Question 2. Prove that, in the absence of any additional information, when the oper- 41 - Q 2
ation Knows(i, j) is performed:
• if the answer is true, then j can be the star, but i cannot,
• if the answer is false, then i can be the star, but j cannot.
Question 3. Specify the precondition and the postcondition of the program solving the 41 - Q 3
problem posed.
Question 4. Specify the constituents of a loop identifying a person likely to be the star 41 - Q 4
of a group, called “potential” star.
Question 5. Specify the other components of the program determining the star of a 41 - Q 5
group or the fact that it involves no star. Write the program solving the initial problem.
i i
i i
i i
i i
41 - Q 6 Question 6. What is its complexity when Knows (i, j) is taken as the elementary opera-
tion?
The solution is on page 145.
In this problem, we are interested in weakening the precondition. This approach which is
legitimate, consists in resolving a problem in reference to a more general one for which a
solution is known. The weakening is made by the elimination of an hypothesis and we study
the impact of this choice on the performances through two examples.
We have seen in section 3.3.2 that it is legal that, trying to solve the problem specified by
{P} prog {Q}, we solve the problem specified by {P′ } prog′ {Q} with P ⇒ P′ . In other terms,
the precondition is weakened and we can wonder about the impact of this approach on
performances. Two examples are dealt with to shine a light on this matter.
Two strategies can be envisaged: (i) to develop a specific algorithm accounting for the fact
that T is decreasingly ordered or (ii) to weaken the precondition by suppressing the conjunct
related to the fact that the array is already ordered.
42 - Q 1 Question 1. Propose the principle of a solution of linear complexity in terms of ex-
changes in the context of the first option.
42 - Q 2 Question 2. Which complexity is obtained with the algorithm proposed in problem 33,
page 112? Can it be expected to do better with a “usual” sorting algorithm? Conclude.
i i
i i
i i
i i
Problems 123
Question 3. Prove that when T is such that the difference between two consecutive 42 - Q 3
elements of T is at most 1, then:
Question 4. Develop the specific solution based on a loop whose constituents will be 42 - Q 4
first explicited.
Question 5. What can be said about the impact of the choice in terms of complexity? 42 - Q 5
The problem dealt with here is a somewhat sophisticated variant of the sequential search. Usu-
ally, in this kind of problem, using the technique called “stop as early as possible” does not
impact asymptotic complexity. This is not what happens here, where this strategy is the back-
bone for the improvement of the efficiency obtained with respect to a naïve method. Moreover,
this problem has a formulation in a two-dimensional space generally solved by two nested
loops. Here, as in problem 32 page 111, the use of a single loop makes the design simpler.
We consider an arbitrary polygon of finite order N (N > 2) whose vertices are labelled
clockwise from 1 to N. We look for any arbitrary chord that separates (halves) the perime-
ter p of the polygon “as accurately as possible”, i.e. such that the absolute value of the
difference between the sum of the lengths of the sides bounded by the chord is minimum.
Complexity is evaluated in terms of the number of visited vertices.
i i
i i
i i
i i
1.6
d[3] = 1.6
3 •
1.3
d[4] = 1.6
• 7 = 1.1
.9
d[5]
• d[6] = 1.3
2
1.8
1.8
2.2 d[7] =
• 0.7
• • .7 8 d[8] =
1 .6 9 d[9] = 0.6
Fig. 3.4 – Example of a polygon of order 9 and its representation by the array d.
Definition 1 (Arc):
Base
case :
(i, i↷+ 1) = (i) i ∈ 1 .. N − 1
(N,
↷
1) = (N).
Inductive
↷ case:
(i, j) = (i, i↷+ 1) · (i +↷1, j) j ̸= i + 1 and i ̸= N
(N, j)
↷ ↷ ↷
= (N, 1) · (1, j)) j ̸= 1.
i i
i i
i i
i i
Problems 125
The problem
The objective of the problem is to find out a globally optimal chord (the problem has at
least one solution). A method consists in the evaluation of formula 3.1 and keeping one of
the pairs of vertices which complies with it. The corresponding algorithm is in Θ(N2 ). It is
also possible to exploit the following identity so as to avoid useless calculations (p is the
perimeter of the polygon):
↷ ↷ ↷ p
∥(i, j)∥ − ∥(j, i)∥ = 2 · ∥(i, j)∥ − . (3.2)
2.0
The pairs of vertices (j, k) complying with formula 3.1 are also those which comply with:
↷ ↷
∥(j, k)∥ − ∥(k, j)∥ ↷ p
= min ∥(u, v)∥ − .
2.0 u ∈ 1 .. N and 2.0
v ∈ 1 .. N and
u ̸= v
But, since |a − b| = |b − a|, to visit all of the arcs, the variable v does not need to scan the
whole set 1 .. N − {u}. It is sufficient that it takes the values of the interval u + 1 .. N ∪ {1},
hence:
↷ ↷
∥(j, k)∥ − ∥(k, j)∥ ↷ p
= min ∥(u, v)∥ − .
2.0 u ∈ 1 .. N and 2.0
v ∈ u + 1 .. N ∪ {1}
↷
If (j, k) is a locally optimal chord issued from j, the value ∥(j, k)∥ − p/2.0 is denoted
δj . The lengths of the arcs intervening in the calculation can be gathered in the following
triangular matrix (called triangle of lengths):
↷ ↷ ↷
∥(1, 2)∥ ∥(1, 3)∥ ......... ∥(1, 1)∥
↷ ↷
∥(2, 3)∥ ......... ∥(2, 1)∥
..
.
↷ ↷
∥(i, i + 1)∥ . . . . ∥(i, 1)∥
.. ..
. .
.. ..
. .
.. ..
. .
↷
∥(N, 1)∥
It can be noticed that the upper right corner of the triangle indicates the value of the
↷
perimeter p = ∥(1, 1)∥ of the polygon. In the case of the polygon of figure 3.4, page 124,
p = 11.8, and this triangle is valued as follows:
i i
i i
i i
i i
2 3 4 5 6 7 8 9 1
1 2.2 3.1 4.7 6.3 7.4 8.7 10.5 11.2 11.8
2 0.9 2.5 4.1 5.2 6.5 8.3 9.0 9.6
3 1.6 3.2 4.3 5.6 7.4 8.1 8.7
4 1.6 2.7 4.0 5.8 6.5 7.1
5 1.1 2.4 4.2 4.9 5.5
6 1.3 3.1 3.8 4.4
7 1.8 2.5 3.1
8 0.7 1.3
9 0.6
However, this type of triangle contains (N(N + 1))/2 elements and their exhaustive eval-
uation leads once again to a solution in Θ(N2 ). This result can be improved on the basis of
the following four observations:
1. For a given vertex j, there is either one, or two locally optimal chords.
2. If the chord (j, k) is the first2 locally optimal chord issued from j, then none of the
chords (j + 1, j + 2), (j + 1, j + 3),. . . ,(j + 1, k − 1) is globally as good as (j, k).
3. Let (j, k) be the first locally optimal chord issued from j. The chord (j + 1, k), if it exists,
may be better than (j, k).
4. When, for the vertex j, a locally optimal chord (j, k) is found out, it becomes useless to
test the optimality of (j, k + 1),. . . , (j, N + 1) (according to the usual principle “stop as
early as possible”).
As to observation 3, it is convenient to notice that other chords issued from the vertex
j + 1 can outperform the chord (j + 1, k).
43 - Q 1 Question 1. Demonstrate identity 3.2, page 125.
43 - Q 2 Question 2. In which situation are there two locally optimal chords issued from the
same vertex j ? Give an example.
43 - Q 3 Question 3. Prove the proposition related to the third above observation.
43 - Q 4 Question 4. In the example of figure 3.4, page 124, which are the arcs whose length
intervenes in the calculation? Which globally optimal chord is found out?
43 - Q 5 Question 5. Let us consider the following example:
5
1 • • 2
3 3
•
3
Specify (by means of a triangle of lengths) the arcs whose length intervenes in the calcula-
tion. What can be observed?
43 - Q 6 Question 6. We decide to build an algorithmic solution on the basis of a single loop.
Propose an invariant for this loop.
i i
i i
i i
i i
Solutions 127
3.8 Solutions
Answers to problem 29. White and red beans The problem is on page 110.
Answer 1. It is easy to see that, whatever the result of a draw, the number of beans in 29 - A 1
the box decreases by 1. After a while, the can contains a single bean and the process stops.
Answer 2. Let us try to find an invariant in the procedure described in the statement of 29 - A 2
the problem. Let nbW (respectively nbR) be the number of white (respectively red) beans
present in the can before any draw. If two red beans are drawn, nbW does not change and
nbR diminishes by 1. If two white beans are drawn, nbW decreases by 2 and nbR increases
by 1. Last, if one white bean and one red bean are drawn, NBW remains unchanged and
nbR diminishes by 1. This shows a property of nbW about its parity which remains un-
changed over time whatever the result of the successive draws. This is an invariant of the
mechanism described in the statement. It makes it possible to deduce that, if the initial
number of white beans is odd (respectively even), the last bean is white (respectively red).
Answers to problem 30. From a coder’s dustbin The problem is on page 111.
Answer 1. A first mistake lies in the fact that the variable sup is used in the invariant 30 - A 1
without its prior definition. Another error impacts the stopping condition which prevents
the accounting for T [N] in the search of the maximum.
Answer 2. An acceptable version is based on the following invariant: 30 - A 2
(i ∈ 1 .. N + 1) and (sup ∈ N) and (∀j · (j ∈ 1 .. i − 1 ⇒ T [j] ⩽ sup))
as well as on the stopping condition: (i = N + 1).
It can be noticed that the initialization establishes the invariant since it holds for i = 2 and
sup = T [1] (T [j] ⩽ sup is true for j = 1 – indeed, case of equality).
P
Answer 1. The initial expression of the postcondition is: s = N j=1 T [j]. It is not under 31 - A 1
conjunctive form and it will be strengthened by the replacement of (N + 1) by the variable
i, and the adjunction of the conjunct (i = N + 1). Thus, the postcondition becomes:
Postcondition : (s is the sum of the first (i − 1) elements of T ) and (i ∈ 1 .. N + 1) and (i =
N + 1).
The heuristics of the breakup leads to separate the postcondition and to suggest:
i i
i i
i i
i i
1. Invariant The first two conjuncts are easy to establish, so they are kept to form the in-
variant:
(s is the sum of the first (i − 1) elements of T ) and (i ∈ 1 .. N + 1)
graphically:
1 i N
T
X
i−1
s = T [j] and (i ∈ 1 .. N + 1)
j=1
In order to both “make the calculation progress” and restore the invariant, the pro-
gression chosen consists in the integration of T [i] into the sum and the increment of
i by 1. These two actions are possible since the formula ((i ∈ 1 .. N + 1) and not(i =
N+1)) ensures that both T [i] exists and i can be increased. We are thus in the following
situation:
0 i N−1
T
X
i−1
s = T [j] and (i ∈ 1 .. N + 1)
j=1
which is nothing but the invariant. So, we have built the progression: s ← s + T [i]; i ←
i + 1.
4. Initialization The initialization is specified by:
Precondition: (T is a constant array of N natural numbers) and (N ⩾ 0)
I NITIALIZATION
P
Postcondition: s = i−1
j=1 T [j] and (i ∈ 1 .. N + 1).
As usual when the initialization is designed, the postcondition of the specification is
the invariant of the loop under construction. Moving from the precondition to the
invariant can be done in attaining the following situation where i is identified to 1:
i i
i i
i i
i i
Solutions 129
1/i N
T
0
X
s = T [j] and (1 ∈ 1 .. N + 1)
j=1
1. constants
2. N ∈ N1 and N = . . . and T ∈ 1 .. N → N and T = [. . .]
3. variables
4. i ∈ 1 .. N + 1
5. begin
6. /% PRE: (T is a constant array of N natural numbers) and (N ⩾ 0) %/
7. i ← 1; s ← 0;
8. while not(i = N + 1) do
9. s ← s + T [i]; i ← i + 1
10. end while;
X
N
11. /% POST: s = T [j] %/
j=1
Answer 1. Let us assume that the work is carried out partly, which is schematized by: 32 - A 1
1 j C
1
i i
i i
i i
i i
The progression of the indexes i and j is handled here in order to examine the next
element (which exists according to the precondition and the fact that the stopping
condition is not met): j is incremented by 1, and if it exceeds C, we move to the begin-
ning of next line.
4. Initialization It allows to move from the precondition to the invariant, which is done in
giving the value 1 to both variables i and j.
5. Termination We can take the area of the white zone of the schema as the termination
expression since it decreases by 1 at each step of the loop: (R − i) · C + (C + 1 − j).
i i
i i
i i
i i
Solutions 131
∀j · (j ∈ 1 .. i − 1 ⇒ ∀k · (k ∈ i .. N ⇒ T [j] ⩽ T [k]))
1 i N
T
sorted
i i
i i
i i
i i
i i
i i
i i
i i
Solutions 133
Answer 5. The outer loop is achieved for i varying from 1 to N and the inner loop, 33 - A 5
which contains the exchange operation, for k varying from (i + 1) to N. It can be deduced
that the number of exchanges is in Θ(N2 ).
Answers to problem 34. Was it a car or a cat I saw The problem is on page 113.
Answer 1. Let us make a proof by contradiction. Let us consider the kth character of T 34 - A 1
starting from its beginning and its end, respectively T [k] and T [N − k + 1]. Let us assume
that T is a palindrome and that these two elements are different, the word (or sentence,
spaces being ignored) represented by T does not read the same in both directions, hence
there is a contradiction.
Answer 2. Let us remind that the pattern proposed in page 109 consists in deciding 34 - A 2
whether there is (or not) an element j in a structure of size N, that fulfills a given predicate
LP that does not depend on the elements preceding j. The result returned is either j itself,
or the conventional value (N + 1) indicating that the structure has been exhausted without
finding an element for which property LP is met. For the problem of decision about a
(possible) palindrome, the approach can be used with:
b (T [j] ̸= T [N + 1 − j])
LP(j) =
detecting a bad match leading to deciding that the string T is not a palindrome. However,
it should be noted that k never takes the value N+1 since elements are pairwise examined.
Indeed, if T represents a palindrome, the algorithm comes to an end with a value of k equal
to (or exceeding by 1) that of (N + 1 − k). For the same reason, the termination expression
must be adapted (see next question), although the generic expression suits well.
Answer 3. Taking these adaptions into account, we get the program hereafter: 34 - A 3
1. constants
2. T ∈ string and T = . . . and N = |T |
3. variables
4. j ∈ 1 .. N
5. begin
6. /% PRE: (T is a constant string of N characters) and (N ⩾ 0) %/
7. j ← 1 ;
8. while not((j ⩾ N + 1 − j) or else (T [j] ̸= T [N + 1 − j))) do
9. j←j+1
10. end while;
11. /% POST: ((j ⩾ N + 1 − j) and (T represents a palindrome)) or ((j < N +
1 − j) and (T does not stand for a palindrome)) %/
12. if j ⩾ N + 1 − j then
13. write(the string , T , represents a palindrome)
14. else
15. write(the string , T , does not represent a palindrome)
16. end if
17. end
Remark
This solution allows for handling strings whatever the parity of their size (odd or even).
i i
i i
i i
i i
34 - A 4 Answer 4. The number of conditions evaluated (for the control of the loop) is varying
from 1 (immediate stop in case of bad match or N = 0) to ⌈(N + 1)/2⌉ (T represents a
palindrome). Thus, complexity is in O(N).
values to be ordered
35 - A 2 Answer 2. We continue the construction of the loop with the four remaining elements.
2. Stopping condition The conjunct previously discarded is taken: (r = w).
3. Progression It is specified by:
Precondition: (b ∈ 1 .. N) and (w ∈ b + 1 .. N + 1) and (r ∈ w .. N + 1) and
(∀j · (j ∈ 1 .. b − 1 ⇒ T [j] < V)) and (∀j · (j ∈ b .. w − 1 ⇒ T [j] = V)) and
(∀j · (j ∈ r .. N ⇒ T [j] > V)) and not(r = w)
P ROGRESSION
Postcondition: (b ∈ 1 .. N) and (w ∈ b + 1 .. N + 1) and (r ∈ w .. N + 1) and
(∀j · (j ∈ 1 .. b − 1 ⇒ T [j] < V)) and (∀j · (j ∈ b .. w − 1 ⇒ T [j] = V)) and
(∀j · (j ∈ r .. N ⇒ T [j] > V)).
The area containing the values not yet sorted has two variable endpoints (w and r−1),
which are exploited to fulfill the constraint of the statement related to exchanges. Let
us review the various cases likely to happen:
a) when T [r − 1] > V, no exchange is needed and the invariant is restored by
decrementing r by 1,
b) when T [w] = V, here again, no exchange is required to restore the invari-
ant, w is incremented by 1,
c) when T [w] < V, T [w] should be placed in the first area and the values at
positions w and b are exchanged before the restoration of the invariant
with the incrementation of these two variables by 1,
i i
i i
i i
i i
Solutions 135
d) when T [w] > V, T [w] should be placed in the right area and the values at
positions w and (r − 1) are exchanged before the restoration of the invari-
ant in decrementing r by 1.
Whatever the situation, it can be observed that at most one exchange takes place.
4. Initialization The initialization is specified by:
Precondition: (T is an array of N natural numbers) and (N ⩾ 1) and (V = T [1])
I NITIALIZATION
Postcondition: (b ∈ 1 .. N) and (w ∈ b + 1 .. N + 1) and (r ∈ w .. N + 1)
(∀j · (j ∈ 1 .. b − 1 ⇒ T [j] < V)) and (∀j · (j ∈ b .. w − 1 ⇒ T [j] = V)) and
(∀j · (j ∈ r .. N ⇒ T [j] > V)).
values to be ordered
i i
i i
i i
i i
35 - A 4 Answer 4. The length of the area containing the values remaining to sort diminishes
by 1 at each step of the progression, while at the same time at most one exchange takes
place. More precisely, the number of exchanges varies from 0 (if the array T contains a
single value or if ∀i · (i ∈ 2 .. N ⇒ T [i] > T [1])) to (N − 1) (if ∀i · (i ∈ 2 .. N ⇒ T [i] < T [1])).
Answers to problem 36. 7’s and 23’s The problem is on page 115.
36 - A 1 Answer 1. Let us assume that the work has been carried out partly, i.e. that the “left”
(respectively “right”) part of T contains no 23 (respectively no 7), which is graphically
represented below:
1 i j N
no 23 to be examined no 7
knowing that this array has been obtained by means of exchanges between pairs (7, 23) or
(23, 7). Hence, the following invariant can be retained:
(i ∈ 1 .. j + 1) and (j ∈ i − 1 .. N) and (T [1 .. i − 1] contains no 23) and (T [j + 1 .. N]
contains no 7).
36 - A 2 Answer 2. When i and j are equal, the grey area contains a unique element which,
whatever it is, is located at the right place (no exchange required). We could think of tak-
ing this predicate as the stopping condition, but if T is empty, we have i = 1 and j = 0
(according to the invariant) and the condition (i = j) is not met. Therefore, we adopt the
stopping condition (i ⩾ j) which covers the case of a empty area either empty or contain-
ing a single element.
36 - A 3 Answer 3. Now, we continue the design of the loop.
3. Progression It is specified by:
Precondition: (i ∈ 1 .. j + 1) and (j ∈ i − 1 .. N) and (T [1 .. i − 1] does not contain any
23) and (T [j + 1 .. N] does not contain any 7) and not(i ⩾ j)
P ROGRESSION
Postcondition: (i ∈ 1 .. j + 1) and (j ∈ i − 1 .. N) and (T [1 .. i − 1] does not contain any
23) and (T [j + 1 .. N] does not contain any 7)
The two indexes i and j will be managed simultaneously in the following synthesized
way:
i i
i i
i i
i i
Solutions 137
T [i] = 23 T [i] ̸= 23
Exchange(i, j);
T [j] = 7 i ← i + 1; i←i+1
j←j−1
j ← j − 1;
T [j] ̸= 7 j←j−1
i←i+1
4. Initialization To reach the invariant from the precondition, it is sufficient to make the
assignments: i ← 1 and j ← N.
5. Termination The expression (j − i + 1) decreases by 1 or 2 at each step and it remains
nonnegative.
Answer 4. The number of exchanges is at best zero (23’s are all located after 7’s) and 36 - A 4
at worst ⌊N/2⌋ (T contains a sequence of ⌊N/2⌋ (respectively ⌈N/2⌉) 23’s followed by a
sequence of ⌈N/2⌉ (respectively ⌊N/2⌋) 7’s). Three comparisons are performed at each
step of the loop (one for the control of the loop and two for the comparisons between T [i]
and T [j]). The number of steps is at best equal to ⌊N/2⌋ (when both indexes i and j evolve
always together) and at worst (N − 1) (when only one of the two indexes i and j changes).
Thus, complexity is in Θ(N) in terms of both comparisons and exchanges.
Answers to problem 37. The Mth zero The problem is on page 116.
i i
i i
i i
i i
Answers to problem 38. Alternating odd and even The problem is on page 116.
38 - A 1 Answer 1. We have:
A and B and (C or D)
⇔ distributivity
(A and B and C) or (A and B and D)
⇒ (A and B) ⇒ A and (A and B) ⇒ B
(A and C) or (B and D).
i i
i i
i i
i i
Solutions 139
1 e o 2N
T
or in this one:
values with even indexes are correctly placed
1 o e 2N
T
The relative positions of o and e do not play any role and we can indifferently take
into consideration T [e] or T [o] (which, nevertheless, breaks the symmetry exploited
until now) to propose the progression:
i i
i i
i i
i i
o/1 e/2 2N
T
complies with the postcondition and the transition from the precondition is obtained
with the assignments: o ← 1; e ← 2.
5. Termination One of the two variables o and e decreases by 2 at each step of the pro-
gression. In contrast, the following expression is nonnegative and it diminishes by 1
at each step of the progression:
(2N − e + 2N + 1 − o)/2.
i i
i i
i i
i i
Solutions 141
16. write(T )
17. end
this latter expression being nothing but the postcondition used before. The newly proposed
postcondition is thus a (logical) strengthening of the initial postcondition; hence, it can
serve as a basis for the construction of a loop appropriate to solve the problem.
Answer 6. With this in mind, we can use the same invariant as before: 38 - A 6
(e ∈ 1 .. 2N + 2) and (e is even) and (positions with even indexes of the interval
2 .. e − 2 contain even values) and (o ∈ 1 .. 2N + 1) and (o is odd) and (positions
with odd indexes of the interval 1 .. o − 2 contain odd values)
and take the discarded conjunct as stopping condition:
((e = 2N + 2) and (o = 2N + 1)).
The progression is specified by:
Precondition: (e ∈ 1 .. 2N + 2) and (e is even) and (positions with even indexes of the
interval 2 .. e − 2 contain even values) and (o ∈ 1 .. 2N + 1) and (o is odd) and (positions
with odd indexes of the interval 1..o−2 contain odd values) and not((e = 2N+2) and (o =
2N + 1))
P ROGRESSION
Postcondition: (e ∈ 2..2N) and (e is even) and (positions with even indexes of the interval
2 .. e − 2 contain even values) and (o ∈ 1 .. 2N + 1) and (o is odd) and (positions with odd
indexes of the interval 1 .. o − 2 contain odd values).
Here again T [o] can be tested as to the fact that it is odd (or not), but since the stopping
condition is conjunctive, its negation is disjunctive. Therefore, we can be in the situation
where o = 2N + 1 (with e ̸= 2N + 2) which means that odd values are all well placed.
The exchange must not be done (2N + 1 being an invalid index for T ), but “force” the
variable p to its final value (2N + 2), since even values are necessarily well placed, hence
the progression:
1. if o ̸= 2N + 1 then
2. if odd(T [o]) then
3. o←i+2
4. else
i i
i i
i i
i i
5. Exchange(o, e) ; e ← p + 2
6. end if
7. else
8. e ← 2N + 2
9. end if
It can be noticed that this progression is slightly more tricky to build than the previous
one. Moreover, it is easy to see that the complexity of the program is the same in terms of
exchanges, but that the number of evaluated conditions for each iteration is now 3 instead
of 2 formerly.
1 i N
T 0 ········· 0 0 ··· 0
lg p
Despite appearances suggested by this schema, the subarrays associated with lg and p
may effectively be confused.
39 - A 2 Answer 2. The progression is specified by:
Precondition: (lg is the length of the longest sequence of zeros contained in the
subarray T [1 .. i − 1]) and (i ∈ 1 .. N + 1) and (p ∈ 0 .. i − 1) and (p is the length of
the longest sequence of consecutive zeros finishing in i − 1) and not(i = N + 1)
P ROGRESSION
Postcondition: (lg is the length of the longest succession of zeros contained in
the subarray T [1 .. i − 1]) and (i ∈ 1 .. N + 1) and (p ∈ 0 .. i − 1) and (p is the
length of the longest sequence of consecutive zeros finishing in i − 1).
It can be asserted that T [i] exists and that the invariant holds. It follows that, if T [i] = 0 then
p increases by 1, while lg becomes the greatest value between p and lg. Otherwise, lg re-
mains unchanged whereas p is set to 0. Restoring the invariant is obtained by incrementing
i by 1.
Hence, we have the following progression:
1. if T [i] = 0 then
2. p ← p + 1 ; lg ← max({lg, p})
3. else
4. p ← 0
5. end if;
6. i ← i + 1
i i
i i
i i
i i
Solutions 143
i i
i i
i i
i i
Answers to problem 40. The majority element (iterative issue) The problem
is on page 119.
40 - A 1 Answer 1. Demonstration of property 3 page 120 The only possibility is that one element
of P is majority. But, any element of P is present at most |P|/2 times (which, in this case, is
equal to |S|/2 times) and thus S cannot be majority.
Demonstration of property 4 page 120, part 1 Letting maj(S) be the predicate stating that S is
majority and maj(v, S) the predicate stating that v is a majority element in S, proposition 1
can be expressed a:
maj(S) ⇒ (c ∈ C ⇒ maj(c, S)),
proposition which will be proven by contradiction as follows:
Demonstration of property 4 page 120, part 2 It is enough to consider the schema in which the
bag R is empty: C contains the value 5, which is not a majority element, 1 is the value with
the highest multiplicity in S but it is not a majority element.
40 - A 2 Answer 2. When the loop stops, R is empty according to the stopping condition and:
• either C is also empty and according to property (3), page 120, it is known that
S is not majority,
• or C is nonempty and according to property (4), page 120, the value c con-
tained in C (in any number of occurrences) is the majority candidate of S, i.e.
the only potential majority element for S, but nothing is sure.
40 - A 3 Answer 3. The precondition and postcondition of the loop built with the proposed
invariant are:
Precondition: (S is a bag of N values) and (N ⩾ 1).
Postcondition: if C is nonempty, x contains the value of the majority candidate of S; if C
is empty, S is not majority.
Therefore, this loop has a weakened postcondition with respect to that of the initial prob-
lem. In order to solve it, in the case where a possible majority candidate has been identified,
it is necessary to check whether S is actually majority (or not).
40 - A 4 Answer 4. We now give the progression, the initialization and the termination func-
tion.
Progression We choose an arbitrary element t of R which is withdrawn from R, and:
(a) if C is empty, t is inserted in C,
(b) if t is already in C, it is added to C,
(c) if t is absent from C, t is paired with an arbitrary element of C (which is
suppressed from C) and the couple is moved to the bag P.
i i
i i
i i
i i
Solutions 145
Under the assumption of the negation of the stopping condition, this procedure is
feasible and it maintains the invariant.
Initialization The bag S is copied into R. The two bags P and C are emptied, which estab-
lishes the invariant.
Termination The value of |R| decreases by 1 at each step of the progression, which guar-
antees that the loop finishes.
Answer 5. The bag C is refined by the pair (x, nbx), where x is the value present in C 40 - A 5
and nbx is its multiplicity. The bag R is refined by the pair (T , i), where T is an array of N
elements and i is such that i ∈ 1 .. N. T [i .. N] materializes the bag R. Last, the bag P disap-
pears from the refinement since its components are never used. The following algorithm is
deduced:
1. constants
2. N ∈ N1 and N = . . . and T ∈ 1 .. N → N1 and T = [. . .]
3. variables
4. x ∈ N1 and nbx ∈ 0 .. N and i ∈ 1 .. N + 1
5. begin
6. /% PRE: (S is a bag of N values represented by the array T [1..N]) and (N ⩾
1) %/
7. nbx ← 0 ; i ← 1 ;
8. while i ̸= N + 1 do
9. if nbx = 0 then
10. x ← T [i] ; nbx ← 1
11. elsif T [i] = x then
12. nbx ← nbx + 1
13. else
14. nbx ← nbx − 1
15. end if;
16. i←i+1
17. end while;
18. /% POST: if C is nonempty (nbx > 0), x contains the value of the majority
candidate of S; if C is empty (nbx =0), S is not majority %/
N
19. if nbx = 0 or else mult(x, T ) ⩽ then
2
20. x ← −1 ;
21. write(No majority element in the array , T )
22. else
23. write(x, is the majority element of the array , T )
24. end if
25. end
The expression mult(x, T ) requires a refinement using a loop over the array T , which is
not made explicit here. This algorithm refined a second time evaluates (N + 1) times the
stopping condition of the first loop and at most (N + 1) times that of the second loop; thus
it is in Θ(N) in terms of comparisons.
Answers to problem 41. The celebrity problem The problem is on page 121.
Answer 1. By convention, a group with a single person has a star, thus at most one 41 - A 1
star. The property is proven by contradiction for a group made of at least two people.
i i
i i
i i
i i
Let us assume that i1 and i2 are two stars of a group. Since a star is known by everyone,
operations Knows(i1 , i2 ) and Knows(i2 , i1 ) both return true, which contradicts the fact that
a star knows nobody in the group.
41 - A 2 Answer 2. Let us assume that the operation Knows(i, j) is performed and that we are
only provided with the answer to rule on the existence of a star. If the answer is positive,
j can be the star of the group since he/she is known by i (who knows another member of
the group and thus cannot be the star). If the answer is negative, j cannot be the star since
he/she is not known by a member of the group, but i can be the star.
41 - A 3 Answer 3. The problem to solve is specified by:
Precondition: (We have group of N people) and (N ⩾ 1)
Postcondition: ((i is the star of the group) and (i ∈ 1 .. N)) or ((the group has no
star) and (i = N + 1)).
41 - A 4 Answer 4. The program allowing for the identification of a “potential” star has a post-
condition which is a weakened version of the initial problem, namely:
Postcondition: ((i is perhaps the star of the group) and (i ∈ 1 .. N)).
A “potential” star is identified by means of a loop whose specification is:
Precondition: (We have a group of N people) and (N ⩾ 1).
Postcondition: ((i is perhaps the star of the group) and (i ∈ 1 .. N)).
The components of the loop are as follows:
1. Invariant The postcondition is strengthened in:
Postcondition: (j ∈ 1 .. N + 1) and (i ∈ 1 .. N + 1) and (i is perhaps the star of
members 1 .. j − 1 of the group) and (j = N + 1).
The first three conjuncts are chosen for the invariant:
(j ∈ 1 .. N + 1) and (i ∈ 1 .. N + 1) and (i is perhaps the star of members 1 .. j − 1
of the group).
2. Stopping condition The discarded conjunct is taken: (j = N + 1).
3. Progression It is specified by:
Precondition: (j ∈ 1 .. N + 1) and (i ∈ 1 .. N + 1) and (i is perhaps the star of members
1 .. j − 1 of the group) and not(j = N + 1)
P ROGRESSION
Postcondition: (j ∈ 1 .. N + 1) and (i ∈ 1 .. N + 1) and (i is perhaps the star of members
1 .. j − 1 of the group).
The progression must deal with member number j of the group. We will use the op-
eration Knows(j, i), i being the “potential” star. From question 2, if the answer is true,
i keeps its status, otherwise it is replaced by j. Thus, we have the progression:
1. if not Knows(j, i) then
2. i ← j
3. end if;
4. j ← j + 1
4. Initialization In order to establish the invariant, it is sufficient to select person 1 as a
possible star (and therefore to assign 2 to j), i.e. to make the assignments: i ← 1 and
j ← 2.
i i
i i
i i
i i
Solutions 147
Answer 5. At the end of the previous loop, i identifies a member of the group which 41 - A 5
may be the star. It remains to confirm that i is actually the star of the group, or that there is
no star inside it (thanks to the principle of sequential composition introduced page 96.
First of all, let us remark that we know that any member j, with j greater than i, knows the
“potential” star i. Member i is actually the star only if: i) any member j with j less than i is
such that Knows(j, i) is true, and ii) any member j other than i is such that not(Knows(i, j)). It
is easy to observe that each situation corresponds to the special case described in section
3.5.2, page 109. Therefore, we will adapt the pattern given in page 109.
In the first loop, the generic property LP is identified to not(Knows(j, i)) and variable N to
(i − 1). In the second one, LP is identified to ((j ̸= i) and Knows(i, j)), hence the program:
1. constants
2. N ∈ N1 and N = . . .
3. variables
4. i ∈ 1 .. N + 1 and j ∈ 1 .. N + 1
5. begin
6. /% first loop: identification of a “potential” star %/
7. /% PRE: (We have a group of N people) and (N ⩾ 1) %/
8. i ← 1 ; j ← 2 ;
9. while not(j = N + 1) do
10. if not Knows(j, i) then
11. i←j
12. end if;
13. j←j+1
14. end while;
15. /% POST: (j ∈ 1 .. N + 1) and (i ∈ 1 .. N) and (i is perhaps the star of
members 1 .. j − 1 of the group) and (j = N + 1) %/
16. /% second loop %/
17. /% PRE: (i is perhaps the star of the group) %/
18. j ← 1 ;
19. while not((j = i) or else not Knows(j, i)) do
20. j←j+1
21. end while;
22. /% POST: (i ∈ 1 .. N) and (j ∈ 1 .. i + 1) and ((j = i) and (i is perhaps the
star of members 1 .. j − 1 of the group)) or ((j ̸= i) and the group has no
star %/
23. if j ̸= i then
24. write(no star in the group)
25. else
26. /% third loop %/
27. /% PRE: (i is perhaps the star of the group) %/
28. j←1;
29. while not((j = N + 1) or else ((j ̸= i) and (Knows(i, j)))) do
30. j←j+1
31. end while;
32. /% POST: ((i is the star of the group) and (j = N + 1)) or ((the group
has no star) and (j ∈ 1 .. N)) %/
33. if j = N + 1 then
34. write(i, is the star of the group)
i i
i i
i i
i i
35. else
36. write(no star in the group)
37. end if
38. end if
39. end
Remark
The complete presentation of this problem as well as its background can be found in [25].
42 - A 3 Answer 3. Let T [i] = k (k > 0). Since the difference between two consecutive elements
is at most 1, the most favorable case to find out a zero occurs with the program:
T [i] = k, T [i + 1] = k − 1, . . . , T [i + k − 1] = 1, T [i + k] = 0.
It appears that all the elements of T with indexes i to i + k − 1 (= i + T [i] − 1) are strictly
positive. When we have a longer sequence, to reach a zero the previous property over
elements with indexes i to (i + T [i] − 1) still holds. Formally, we have:
42 - A 4 Answer 4. We build the constituents of a loop in the spirit of those designed for the
search of the first zero, taking advantage of the result established in the previous question.
1. Invariant We take: (i ∈ 1 .. N) and (T [1 .. i − 1] contains no zero).
2. Stopping condition It is T [i] = 0.
i i
i i
i i
i i
Solutions 149
3. Progression From the property established previously, it is known that, since T [i] is not
equal to zero, it is possible to increment i by the value T [i] with the guarantee that no
zero is “missed” (T [i + T [i]] may be equal to 0), hence the progression: i ← i + T [i].
4. Initialization The initialization is restricted to the assignment i ← 1.
5. Termination The expression (N − i) is appropriate.
Answer 5. The specific algorithm which has been designed needs between one com- 42 - A 5
parison (if T [1] = 0) and N comparisons (if T [1] = . . . = T [N − 1] = 1 and T [N] = 0). It is the
same for the algorithm given in page 101. The two solutions are situated in the same class
of complexity O(N). However, in the specific algorithm the step of the loop is variable and
it is always greater than or equal to 1. Thus, it is preferable to use it since it never does
worse than the other one (even slightly better in general).
Answer 6. The discarded conjunct (the difference between two consecutive elements 42 - A 6
of T is at least 1) expresses the fact that it cannot exist two consecutive elements of T with
the same value, which does not help to resolve the problem of the search for the first zero.
As a consequence, there is no (obvious) specific program in this case. It is thus recom-
mended to use the program corresponding to the weakened precondition (see page 101),
choice solving ”at best” the problem in a performance perspective.
Answer 7. The three examples treated previously show that weakening the precondi- 42 - A 7
tion can lead to:
• a solution whose class of complexity is worse than that of a specific solution,
• a solution of same class of complexity, but after all less efficient,
• a good solution if the discarded conjunct cannot be exploited for building a
specific solution.
Answer 1. We have: 43 - A 1
↷ ↷
∥(i, j)∥ − ∥(j, i)∥
= arithmetics
↷ ↷ ↷
2 · ∥(i, j)∥ − (∥(j, i)∥ + ∥(i, j)∥)
= definition of p
↷
2 · ∥(i, j)∥ − p
= arithmetics
↷ p
2 · ∥(i, j)∥ − .
2
Answer 2. When the semi-perimeter having its origin in vertex j has exactly its end in 43 - A 2
the middle of a side, there are two optimal chords issued from vertex j. It is the case of the
pentagon hereafter: there are two optimal chords issued from j: (j, k) and (j, k + 1). The
↷ ↷
first one separates the pentagon into ∥(j, k)∥ = 4 units, and ∥(k, j)∥ = 8 units, the second
↷ ↷
one separates it into ∥(j, k + 1)∥ = 8 units, and ∥(k + 1, j)∥ = 4 units.
i i
i i
i i
i i
2
• •k
2
j• 4/8
4
×
8/
4
3
• •
1 k+1
Consequently, it is sufficient to restrict the proof to the longest arc among the set of arcs
↷ ↷ ↷ ↷
(j + 1, j + 2), (j + 1, j + 3),. . . ,(j + 1, k − 1), or (j + 1, k − 1). Thus, we will demonstrate that
↷ ↷
∥(j + 1, k − 1)∥ − p/2.0 > ∥(j, k)∥ − p/2.0 (= δj ).
Denoting by q the extremity of the semi-perimeter issued from j, two situations must be
singled out:
j + 1• •k − 1 j + 1• •k − 1
q
×
j• •k j• •k
×q
(a) •k + 1 (b) •k + 1
In both cases, we have:
↷ p
∥(j + 1, k − 1)∥ −
2.0
p ↷
= > ∥(j + 1, k − 1)∥ and property of the absolute value
2.0
p ↷
− ∥(j + 1, k − 1)∥
2.0 p
= development of
↷ ↷ ↷ ↷
2.0
∥(j, j + 1)∥ + ∥(j + 1, k − 1)∥ + ∥(k − 1, q)∥ − ∥(j + 1, k − 1)∥
= arithmetics
↷ ↷
∥(j, j + 1)∥ + ∥(k − 1, q)∥.
↷ ↷
In the first case (schema (a)), ∥(k − 1, q)∥ > ∥(q, k)∥ since otherwise the chord (j, k − 1)
would be the first locally optimal chord for the vertex j. Therefore, it comes:
↷ ↷
∥(j, j + 1)∥ + ∥(k − 1, q)∥
> arithmetics
↷
∥(k − 1, q)∥
> previous remark
↷
∥(k, q)∥
= definition of δj
δj
i i
i i
i i
i i
Solutions 151
and finally:
↷ p
∥(j + 1, k − 1)∥ − > δj .
2.0
In the second case (schema (b)), we have:
↷ ↷
∥(j, j + 1)∥ + ∥(k − 1, q)∥
↷
= development of ∥(k − 1, q)∥
↷ ↷ ↷
∥(j, j + 1)∥ + ∥(k − 1, k) + ∥(k, q)∥
> arithmetics
↷
∥(k, q)∥
= definition of δj
δj
and we also have:
↷ p
∥(j + 1, k − 1)∥ − > δj .
2.0
Answer 4. First of all, let us notice that the chord (j + 1, k) may not exist and we will 43 - A 4
come back to this point later (see question 5). To prove that the chord (j + 1, k) may be
better than (j, k) the first optimal chord issued from j, an example suffices. Let us consider
the following pentagon:
•
5 6
j+1
•
• k
1
•
j
5 • 5
The chord (j, k) is locally optimal and it separates the perimeter into two parts of respective
lengths 12.0 and 10.0. The chord (j + 1, k) separates the perimeter into two equal parts of
length 11.0. This division is optimal since the value of δj+1 is 0.0 and it outperforms the
previous one for which δj = 12.0 − 11.0 = 1.0.
Answer 5. The value of the perimeter of the polygon is 11.8 and the value of its semi- 43 - A 5
perimeter is 5.9. The arcs whose length intervenes in the calculation are greyed-out as , as
or as in figure 3.5.
We will go into the details of the calculations in order to highlight the properties and mech-
↷ ↷ ↷
anisms used. In the case of the first line, the respective lengths of the arcs (1, 2), (1, 3), (1, 4)
↷ ↷
and (1, 5) are calculated. Their values are 2.2, 3.1, 4.7 and 6.3. The length of the arcs (1, 6)
↷
to (1, 1) is not calculated (according to the heuristics “stop as early as possible”), since the
↷
length of the arc (1, 5) is greater than that of the semi-perimeter. The chord (1, 5) associated
with this arc (cell greyed-out as in the schema) is retained as the (first) locally optimal
↷
chord from the vertex 1, since the comparison with the previous arc (1, 4) is in favor of
↷
(1, 5).
As for the arcs whose origin is vertex 2, it is useless calculating the length of the arcs
↷ ↷ ↷
(2, 3) and (2, 4) (see question 3). The evaluation begins with the arc (2, 5) whose length is
↷ ↷
∥(1, 5)∥ − ∥(1, 2)∥ (or, 6.3 − 2.2 = 4.1). As a matter of fact, according to the definition of the
length of an arc (definition 2 page 124, inductive case), if j ̸= i + 1 and i ̸= N,
i i
i i
i i
i i
2 3 4 5 6 7 8 9 1
1 2.2 3.1 4.7 6.3 7.4 8.7 10.5 11.2 11.8
2 0.9 2.5 4.1 5.2 6.5 8.3 9.0 9.6
3 1.6 3.2 4.3 5.6 7.4 8.1 8.7
4 1.6 2.7 4.0 5.8 6.5 7.1
5 1.1 2.4 4.2 4.9 5.5
6 1.3 3.1 3.8 4.4
7 1.8 2.5 3.1
8 0.7 1.3
9 0.6
Fig. 3.5 – Example corresponding to figure 3.4, page 124, showing the arcs whose length is actually
calculated. The arcs greyed-out in are those corresponding to locally optimal chords. The arcs
↷
correspond to those visited whose length is less than p/2.0. An arc (i, k) greyed-out as is, for a
given origin i, the first arc whose length is greater than or equal to p/2.0, but which is not a locally
optimal chord (whilst (i, k − 1) is). The arcs on a white background ( ) correspond to those not
visited.
↷ ↷
∥(i, j)∥ = d[i] + ∥(i + 1, j)∥
⇔ first base case, definition 2, page 124
↷ ↷ ↷
∥(i, j)∥ = ∥(i, i + 1)∥ + ∥(i + 1, j)∥
⇔ arithmetics
↷ ↷ ↷
∥(i + 1, j)∥ = ∥(i, j)∥ − ∥(i, i + 1)∥
⇒ substitution (i by 1 and j by 5) and arithmetics
↷ ↷ ↷
∥(2, 5)∥ = ∥(1, 5)∥ − ∥(1, 2)∥
⇔ numerical application
4.1 = 6.3 − 2.2.
↷ ↷
We pursue with the arcs (2, 6) of length 5.2 and (2, 7) of length 6.5. This latter value is
greater than the semi-perimeter, which leads to select (2, 7) as the locally optimal chord
↷ ↷ ↷
issued from vertex 2 (the length of the following arcs – (2, 8), (2, 9), (2, 1) – is not cal-
culated applying the heuristics “stop as early as possible”). For the arcs starting at ver-
↷ ↷ ↷
tex 3, only length of the arcs (3, 7) and (3, 8) are calculated: ∥(3, 7)∥ − p/2.0 = 0.3 and
↷ ↷
∥(3, 8)∥ − p/2.0 = 1.5. The comparison is in favor of (3, 7); the chord (3, 7) is thus de-
↷ ↷
clared to be locally optimal. The length of the arcs (3, 9) and (3, 1) is not calculated.
Vertex 7 is the starting point of the calculation related to arcs starting at vertex 4. We calcu-
↷ ↷ ↷
late the length of the chords (4, 7), (4, 8) and (4, 9), whose respective values are 4.0, 5.8 and
6.5, which leads to take (4, 8) as the locally optimal chord issued from vertex 4. The length
↷
of (4, 1) is not calculated.
↷ ↷ ↷
As for vertex 5, we calculate the length of the arcs (5, 8), (5, 9) and (5, 1). Chord (5, 1) of
(maximum) value 5.5, is declared locally optimal.
i i
i i
i i
i i
Solutions 153
From now on, in vertue of observation 3 in the statement of the problem, for each vertex
↷ ↷ ↷ ↷
i of the interval 6 .. 9, there is a single candidate arc ((6, 1), (7, 1), (8, 1), (9, 1)); the related
chord ((6, 1), (7, 1), (8, 1), (9, 1)) is therefore locally optimal.
Eventually, the resulting global optimal chord is (4, 8). Figure 3.5, page 152 confirms this
result since, among all the values of the triangle of lengths, 5.8 is the one closest to 5.9,
which is the length of the semi-perimeter.
Answer 6. The perimeter of this polygon is 11.0. Therefore, the value of its semi- 43 - A 6
↷
perimeter is 5.5. For the arcs issued from the vertex 1, we have ∥(1, 2)∥ = 5.0, value which
does not allow for stopping the search for the locally optimal chord. On the contrary, the
↷
value ∥(1, 3)∥ = 8.0 exceeds the semi-perimeter and we can stop the search for arcs whose
↷
origin is the vertex 1. Among these two values, ∥(1, 2)∥ is the best one and the chord (1, 2)
is the local optimum for vertex 1.
2 3 1
1 5.0 8.0 11
2 3.0 6.0
3 3.0
However, to account for the arc whose origin is vertex 2, according to observation 3 of the
↷
statement, we should begin with the calculation of the arc ∥(2, 2)∥; yet, this one does not
exist in the triangle of lengths. This special case shall be taken into consideration in the
progression of the loop which will be built. It occurs when the row (i + 1) is dealt with and
the locally optimal chord of line i is (i, i + 1). So, this case is not specific to triangles, it is
also the case of the quadrangle below for which the calculation for the arcs whose origin is
↷
the vertex 3 cannot be done from ∥(2, 3)∥ since the chord (2, 3) is of type (i, i + 1).
1• 2 • 2 2 3 4 1
1
4• 1 2 7 10 11
2 5 8 9
3 3 4
3
• 4 1
3
i i
i i
i i
i i
2 3 j N+1
1
2
The length lgc of 3
↷
arc (i, j) is known.
i
i+1
Fig. 3.6 – An instance of the work carried out partly over the triangle of lengths.
i i
i i
i i
i i
Solutions 155
i i
i i
i i
i i
Complexity
The complexity, in terms of visited vertices, is in Θ(N). As a matter of fact, considering
two consecutive rows i and (i + 1) in the triangle of lengths (see for example, figure 3.5
page 152), visited vertices follow one another, with the possible exception of the overlap-
ping of one or two vertices. Finally, N vertices are visited once and at most (N − 2) are
visited twice, hence at most 3(N − 4) visited vertices. The calculation of the perimeter p,
present in the precondition, has no impact on the asymptotic complexity since it is per-
formed in Θ(N).
Remark
It can be observed that triangles of lengths are a kind of triangular saddle (see problem
102, page 439): rows (respectively columns) are increasingly (respectively decreasingly)
ordered. This property can be exploited to enhance the stopping condition of the loop and
↷
stop it when the locally optimal arc of origin i is (i, 1), that its length is less than or equal to
the semi-perimeter and that it does not improve the globally optimal arc known so far. In
↷ ↷
the situation of figure 3.5, page 152, it is the case of (5, 1) which is such that ∥(5, 1)∥ = 5.5.
↷
Yet, 5.5 is worse than the length (5.8) of the best arc known (4, 8) and less than the semi-
perimeter 5.9. It is useless evaluating all the arcs whose origin is a vertex greater than 5.
The expression of the new stopping condition is left to the reader. It has no incidence on
the asymptotic complexity since it is still necessary to reach the rightmost column of the
triangle of lengths, thus to visit at least N vertices.
i i
i i
i i
i i
4
Reduce and conquer, recursion
F. Cavanna
When the parameter is strictly greater than 100, termination is obvious, but what happens
otherwise? The reader can check in exercise 44, page 166, that, according to this hypothe-
sis, this function always ends and that the returned result is the value 91.
We now give an example of a problem for which a recursive approach allows to design
a simple elegant solution. Let us consider a series of positive integers terminated with a
marker, either −1, or −2. If the marker is −1, the objective is to compute the sum of the
preceding values, otherwise their product. The sequence of numbers must be read only
once and it must not be explicitly stored (for instance in an array). Indeed, recursion will
i i
i i
i i
be used to collect each of the numbers read in the local variable nb. The appropriate opera-
tion (sum or product) associated with the marker (global variable mark) will be performed
after the recursive call and, finally, the expected value (global variable res) is obtained by
means of the following procedure:
By doing so, no explicit storage is used for the numbers to be added or multiplied, those
being stored in the execution stack related to the handling of recursion. Clearly, no space
saving is achieved but this is not the objective in this case. It can be noticed that the pro-
cedure SomProd is not restricted to a conditional statement, although it involves one that
singles out the terminal case and the recursive one.
nbBT (0) = 1
X
n−1
nbBT (n) = nbBT (i) · nbBT (n − i − 1) n ⩾ 1.
i=0
i i
i i
i i
i i
1. constants
2. n = 15
3. begin
4. write(the number of binary trees having , n, nodes is , nbBinTr(n))
5. end
which delivers the same value as the one returned by the iterative program in page 13.
However, each number nbBT is computed several times. To realize this, it is sufficient
to observe what happens for n = 5. The call nbBinTr(5) causes two calls to nbBinTr(0),
nbBinTr(1), nbBinTr(2), nbBinTr(3) and nbBinTr(4). Except nbBinTr(0), these calls in turn
cause pairs of new calls (for example nbBinTr(4) calls nbBinTr(0), nbBinTr(1), nbBinTr(2)
and nbBinTr(3)), and so on. More precisely, nbMult(n) the number of multiplications re-
quired to calculate nbBT (n) is given by the recurrence:
nbMult(0) = 0
X
n−1
nbMult(n) = (1 + nbMult(i) + nbMult(n − i − 1)) = 1 + 2 · nbMult(n − 1)n ⩾ 1
i=0
whose solution is nbMult(n) = (3n − 1)/2 for any n ⩾ 1 (this result can be proven by
strong induction). The number of multiplications required by this algorithm is thus in
Θ(3n ), whereas that in page 13 is in Θ(n2 ).
Another illustration of the interest for an iterative implementation of the computation
of a value defined by a recurrence relation is given in exercice 45, page 167.
i i
i i
i i
i i
4.3.1 Presentation
We consider a one-dimensional problem of size n denoted by Pb(n). To resolve it, we call
on (i) a sub-problems of size (n − 1) (hence the term “reduce”) of the same nature as the
initial problem and (ii) the additional function f. This latter aims at the generation of the
sub-problems on the one hand and at the “combination” of their results in order to obtain
the final result on the other hand. There should be a size n0 (most often k = 0, i.e. f is a
function of constant complexity) for which the solution is known directly (the so-called ele-
mentary problem), i.e. without calling on sub-problems. So, we have the following generic
reduction resolution pattern (also called reduction model):
When a = 1, we have a “classical” recursion which, most often, can be easily transformed
into an iteration (see Chapter 1). In the general case, the structure of the program is:
were the generic procedure Assemble composes the final result from the partial results re-
turned by each of the invoked sub-problems. The initial call is made through the program:
1. constants
2. m ∈ N1 and m = . . .
3. begin
4. ReduceAndConquer(m)
5. end
C(1) = d (d ∈ Θ(1))
C(n) = a · C(n − 1) + c · nk n>1
P
whose general solution is C(n) = an−1 · d + c · n−2
i=0 a · (n − i) ; this solution can be
i k
i i
i i
i i
i i
C(n) = a · C(n − 1) + c · nk
C(n − 1) = a · C(n − 2) + c · (n − 1)k
C(n − 2) = a · C(n − 3) + c · (n − 2)k
...
C(2) = a · C(1) + c · (2)k
C(1) = d.
Multiplying the second line by a, the third one by a2 , . . . , the penultimate one by an−2 , the
last one by an−1 and summing up the left terms on the one hand and the right on the other
hand, it yields:
By simplifying, it comes:
and finally:
X
n−2
C(n) = an−1 · d + c · ai · (n − i)k .
i=0
In order to ensure the correctness of the proposed solution, we will systematically rely on
an inductive construction (most often a simple induction over N or N1 ) with three con-
stituents: (i) the base where the elementary case is made explicit together with its related
solution, (ii) the induction hypothesis where it is assumed that the problem of size (n − 1)
can be resolved for (n − 1) greater than or equal to the value of the base, and (iii) the in-
duction itself where it is demonstrated how to resolve the problem Pb(n) of size n using
the induction hypothesis. A fourth component of this type of proof will be omitted, the
termination, which is guaranteed here inasmuch as the size of the problem is an integer at
least equal to the value specified in the base (since starting with a positive integer greater
than or equal to that of the base, the value of the base is obtained by constant subtractions
of 1).
i i
i i
i i
i i
a, b
c
Base We know how to make the spiral of size 0 which consists in doing nothing.
Induction hypothesis We assume that, inasmuch as a is greater than 2 · α · (n − 1), we
know how to make the spiral of size (n − 1) (n − 1 ⩾ 0) having an upper horizontal
segment of length l equal to that of its right vertical segment and a lower horizontal
segment and a left vertical segment of length l − α.
Induction We specify how to make the spiral of size n assuming that a is greater than
2 · α · (n − 1). We begin with the trace of the upper horizontal segment of length a,
then the right vertical segment of the same length. Then, we trace the lower horizontal
segment of length (a − α), then the left vertical segment of the same length. Then, we
trace the spiral of size (n − 1) whose upper horizontal segment is of length (a − 2α),
which is feasible from the induction hypothesis since:
i i
i i
i i
i i
SpiralDraw(0, a) elementary
(nothing to do)
SpiralDraw(n − 1, a − 2α)
SpiralDraw(n, a) → + n > 0.
tracing of the outer pseudo-square
1. constants
2. x0 ∈ R∗+ and x0 = . . . and y0 ∈ R∗+ and y0 = . . .
3. begin
4. place(x0 , y0 );
5. SpiralDrawing(7, x0 , y0 , 24.0, 1.5)
6. end
and traces the spiral of size 7 whose initial upper side of length 24 cm starts at the point
of coordinates (x0 , y0 ). This call complies with the precondition evoked previously since
24 > 2 · 1.5 · 6 (= 18).
Remark
Here, we have a tail-recursive procedure and the actual implementation can be an iterative
procedure rather than a recursive one (see Chapter 1).
Finally, we calculate the length of the trace depending on n, a and α assuming that the
precondition a > 2·α·(n−1) is met. The length of the trace is the solution of the recurrence:
LG(0, −, −) = 0
LG(n, a, α) = 2a + 2(a − α) + LG(n − 1, a − 2α, α) n>0
For n = 7, we get LG(7, a, α) = 28a − 182α, i.e. 98 cm for a = 10.0 cm and α = 1.0 cm.
i i
i i
i i
i i
pi pa pf pi pa pf
(a) initial situation (b) final situation
• we can move a single disk at a time thanks to the operation move(p1 , p2 ), where p1
designates the pillar from which the upper disk is extracted and p2 the pillar on top of
which this disk is placed,
• a disk can be placed either on an empty pillar or over a larger disk.
An example of initial and final configurations is given in figure 4.2, for n = 6. We will
build a solution to move any tower of n disks (n ⩾ 1) according to the inductive schema
hereafter.
Base We know how to move a tower made of a single disk from a pillar to an empty one.
Induction hypothesis We assume that we know how to move a tower of (n−1) (n−1 ⩾ 1)
disks of decreasing diameters from a pillar to either an empty one or to a pillar housing
the largest disk using the auxiliary one which is initially empty.
Induction We show that we can move a tower made up of n disks of decreasing diameters
from pillar pi to pillar pf (initially empty) using the auxiliary pillar pa . To do this: (i) we
move the tower made of the (n − 1) upper disks from pi to pa (see figure 4.3, page 164),
which is feasible according to the induction hypothesis since the auxiliary pillar pa is
initially empty, (ii) then we move the last disk (the largest one) from pi to pf (see figure
4.4), which corresponds to an elementary move that can be made legally since the pillar
pf is empty, (iii) last we move the tower made of the (n − 1) disks on the pillar pa to
−→
pi pa pf pi pa pf
Fig. 4.3 – The first step of the inductive process of move of a tower of Hanoi.
i i
i i
i i
i i
−→
pi pa pf pi pa pf
Fig. 4.4 – The second step of the inductive process of move of a tower of Hanoi.
−→
pi pa pf pi pa pf
Fig. 4.5 – The last step of the inductive process of move of a tower of Hanoi.
the pillar pf (see figure 4.5), which is feasible according to the induction hypothesis,
noticing that, although nonempty, the arrival pillar pf contains the largest disk at its
base.
hanoi(1, pi , pf , pa ) elementary
(move(pi , pf ))
hanoi(n − 1, pi , pa , pf )
+
hanoi(n, pi , pf , pa ) → move(pi , pf ) n > 1.
+
hanoi(n − 1, pa , pf , pi )
Here, the generic function f consists in moving the largest disk from pi to pf . Choosing
the move of a disk as the elementary operation, we calculate nbMV(n), the number of
moves of disks necessary to move a tower of n disks. The number nbMV(n) is given by
the recurrence:
nbMV(1) = 1
nbMV(n) = 2 · nbMV(n − 1) + 1 n>1
We now show that this solution is optimal. Let minnbMV(n) be the minimum number of
disk moves required for a tower of n disks. The largest disk must be moved at least once.
To be “legally” moved, this disk must be alone on its pillar and the destination pillar must
be empty; all other disks must be placed, in right order, on the third pillar. Therefore, before
i i
i i
i i
i i
the first move of the largest disk, a tower of size (n − 1) would have had to be moved. It is
the same after the last move of this disk. Thus, we have:
minnbMV(n) ⩾ 2 · minnbMV(n − 1) + 1.
Since the algorithm designed before yields a number of moves which meets:
nbMV(n) = 2 · nbMV(n − 1) + 1,
4.5 Problems
Problem 44. A doubly recursive function ◦ •
This problem focuses on recursion. Its interest lies in the way the termination of the considered
recursive procedure is proven.
We consider the function Calc whose code has been given at the beginning of this chap-
ter. We will show that this function delivers the value 91 for any call parameter value
strictly less than 102.
44 - Q 1 Question 1. Establish that Calc(100) = Calc(101) = 91.
44 - Q 2 Question 2. Prove by induction (simple induction over k ∈ N) that, for any n in the
interval (90 − 11k) .. (100 − 11k), the call Calc(n) returns the value 91.
44 - Q 3 Question 3. What can be concluded about the termination of this function?
The solution is on page 174.
i i
i i
i i
i i
Problems 167
This problem aims mainly at the illustration of the soundness of a non-recursive implementa-
tion of a value defined by a recurrence relation.
We denote by F(n) the current term of the Fibonacci series defined for n strictly posi-
tive. By definition:
F(1) = 1
F(2) = 1
F(n) = F(n − 1) + F(n − 2) n ⩾ 2.
Question 1. Write the recursive function FiboR(n) modeled on this recursive definition 45 - Q 1
to compute F(n).
Question 2. Give the total number of additions performed for n = 6. 45 - Q 2
This problem takes place in the framework of the Euclidian geometry. It presents no significant
difficulties, except that the value associated with the base of the inductive reasoning used, is
neither 0 nor 1, cases announced as “regular” in the presentation of this chapter.
SameSide(xA , yA , xB , yB , xC , yC , xD , yD ) result B
deciding whether or not points C and D of coordinates (xC , yC ) and (xD , yD ), are located
on the same side of the line (AB). What is its complexity in terms of evaluated conditions?
Question 2. State an inclusion property of a point in an triangle and write the function: 46 - Q 2
InTriangle(xA , yA , xB , yB , xC , yC , xP , yP ) result B
deciding whether or not the point P of coordinates (xP , yP ) is inside (broadly speaking)
the triangle (ABC). What is its complexity in terms of evaluated conditions?
Question 3. Derive a function of type “Reduce and conquer”: 46 - Q 3
InPolygon(n, xP , yP ) result B
i i
i i
i i
i i
deciding whether or not the point P is inside the convex polygon of n vertices of coordi-
nates (x1 , y1 ), (x2 , y2 ), . . ., (xn , yn ) with n ⩾ 3.
46 - Q 4 Question 4. Give its temporal complexity at worst in terms of evaluated conditions.
46 - Q 5 Question 5. Why does polygon convexity matter?
The solution is on page 176.
The main interest of this problem lies in the design of the trace to be done, especially the
identification of its starting point.
We want to make the drawing presented in figure 4.6, inside which the base pattern is
made of two nested squares. We are provided with the two usual primitives place(x, y) and
draw(x, y) of example 4.3.2 page 162, and the drawing must be done under the following
constraints: