From the problem to the algorithm

Summary

This lesson contains no code, and not by oversight: the algorithm comes before the program, and whoever cannot describe precisely what must be done will not be able to say it in C++ either. It first teaches how to specify a problem, that is, how to state what data it receives, what result it must deliver and what relation binds them, and it shows that one and the same statement admits different specifications. It then defines the algorithm as a finite, precise and general procedure, and writes in numbered steps the algorithm of division by repeated subtraction. It teaches how to trace an algorithm by hand with a trace table, which throughout the course will be the first instrument for understanding and for debugging. It presents the three ways of combining steps (sequence, decision and repetition), with which every algorithm is written, and it shows how to justify that a repetition terminates by means of a quantity that decreases on every iteration and cannot go down indefinitely.

Learning objectives

Specify a simple problem by stating its inputs, its outputs and the conditions they must satisfy.
Describe an algorithm in numbered steps, without ambiguity, with explicit decisions and repetitions.
Trace an algorithm by hand with a trace table and determine its result for a given input.
Distinguish, in a given procedure, sequence, decision and repetition, and justify that a repetition terminates.

What a computational problem is

A computational problem is a relation between two kinds of data: those that are received, called the input, and those that must be delivered, called the output. Solving it does not consist in obtaining an answer for one case, but in having a method that, for every admissible input, produces an output satisfying the relation. “What is 17 divided by 5?” is a question; “given two integers, obtain their quotient and their remainder” is a problem, because it speaks of all pairs of integers at once.

Now, ordinary language is imprecise, and the same statement can be understood in several ways. That is why, before solving, one specifies: one writes down what goes in, what comes out and what conditions each thing must satisfy. A specification has three parts. The input lists the data with their kind (integers, decimals, words) and the conditions required of them, which are called the precondition: whoever uses the solution undertakes to respect them. The output lists the results. The relation, or postcondition, states what the output must satisfy with respect to the input: whoever writes the solution undertakes to guarantee it whenever the precondition has been respected. It follows that a specification is a contract between whoever poses the problem and whoever solves it, and that outside the precondition the solution promises nothing.

ExampleThe maximum of three numbers

Ordinary statement: “find the largest of three numbers.” Specification:

Input: three numbers $x$ , $y$ , $z$ (integers or decimals, with no other condition).
Output: a number $m$ .
Relation: $m$ is one of the three given values, and none of them is greater than $m$ ; that is, $m \geq x$ , $m \geq y$ and $m \geq z$ .

The relation does not say “the largest of the three,” which is precisely what was to be made precise, but two checkable conditions. The first requires $m$ to be one of the given values (without it, the number 1000 would satisfy the second for almost any input); the second, that none of them exceed it. And the specification settles in passing a doubt that the statement left open: if two values tie for the maximum, as in $(4, 9, 9)$ , the output is $9$ , and there is nothing wrong with that.

One and the same statement admits different specifications, and choosing among them is a decision, not an oversight. The most instructive case is integer division. For integers $a \geq 0$ and $b > 0$ , everyone agrees: the quotient $q$ and the remainder $r$ are the only integers that satisfy

a = b \cdot q + r, \quad 0 \leq r < b

Thus, for $a = 17$ and $b = 5$ they are $q = 3$ and $r = 2$ , because $17 = 5 \cdot 3 + 2$ . But the statement “divide two integers” does not say what to do if $a$ is negative, and the question is not idle: for $a = -7$ and $b = 2$ there are two reasonable answers.

ExampleTwo specifications of division with a negative dividend

First specification: the remainder is never negative, $0 \leq r < b$ . Then $-7 = 2 \cdot (-4) + 1$ , and the output is $q = -4$ , $r = 1$ . This is the one studied in mathematics, in the lesson “Divisibility and division with remainder” of the course Algebra and Geometry I.

Second specification: the quotient is the result of the division with decimals, with its decimal part discarded, that is, rounded toward zero; the remainder is what is missing, and it has the sign of the dividend. Then $-7 / 2 = -3.5$ is truncated to $-3$ , and $-7 = 2 \cdot (-3) + (-1)$ : the output is $q = -3$ , $r = -1$ .

Both satisfy $a = b \cdot q + r$ ; they differ in the condition imposed on the remainder. Neither is an error, but a program that uses one believing that it uses the other will give wrong results with negative numbers. Let us anticipate a fact: C++ adopts the second, as will be seen in the lesson Arithmetic; whoever expects the first is in for a surprise.

There is a third option, which is the most common in practice: excluding the case through the precondition. If the specification requires $a \geq 0$ , the problem of negative numbers disappears, not because it has been solved, but because whoever uses the solution has undertaken not to pose it. What cannot be done is to leave the question undecided. And for the same reason the specification requires $b > 0$ : with $b = 0$ there are no $q$ and $r$ that satisfy the relation, and the contract must say so.

A frequent error consists in specifying with an example: “the output for 17 and 5 is 3 and 2.” An example illustrates, but it does not specify, because it does not say what happens with the other inputs; infinitely many different relations agree on one case. A specification is written as a general condition, and examples serve afterward to check it.

Algorithms

Once the problem has been specified, one looks for a method to solve it. An algorithm is a sequence of instructions that, applied to any input satisfying the precondition, produces in a finite number of steps an output satisfying the postcondition. The definition contains three requirements.

Finiteness. The algorithm is written with a finite number of instructions and, for every admissible input, it terminates after executing a finite number of them. A procedure that for some input goes on forever is not an algorithm for that input.
Precision. Each instruction has a single meaning, and whoever executes it knows at every moment what to do and which instruction comes next. No decision is left to the judgment of whoever executes it.
Generality. The algorithm solves the problem for all admissible inputs, not just for one case.

With some latitude, the name algorithm is also given to a procedure that is precise and terminates but that, for some admissible input, does not satisfy the postcondition: strictly speaking it is an algorithm for another problem, and it will be said to be incorrect for the specified problem. That is how the problems of this lesson will speak, since they refute incorrect algorithms with a counterexample.

A cooking recipe resembles an algorithm, and that is why it is the usual comparison; but almost no recipe is one. “Add a pinch of salt” is not precise, because a pinch is not a quantity; “bake until golden” depends on a judgment that two people would make differently; “beat several times” does not say how many. A cook fills those gaps with experience; a computer has none. From this follows the requirement that governs the whole course: an algorithm must be followable by someone who does not understand the problem, without guessing anything. If one has to know what a step is for in order to execute it, the step is badly written.

The algorithms of this course are first written in numbered steps, in English, with a few conventions. The data that change during the algorithm are named with letters or words, such as $q$ or $r$ , and are called variables. One writes “ $r$ takes the value $r - b$ ” to say that $r - b$ is computed with the current value of $r$ and the result becomes the new value of $r$ ; the previous value is lost. In the abbreviated form, which is used when taking notes, the same instruction is written with a left-pointing arrow, which on the keyboard is r <- r - b. The instructions are executed in the order of their numbers, unless one of them says otherwise.

ExampleDivision by repeated subtraction

The problem is the one specified in the previous section: input, two integers $a \geq 0$ and $b > 0$ ; output, two integers $q$ and $r$ with $a = b \cdot q + r$ and $0 \leq r < b$ . The idea is that of sharing out: from $a$ one removes groups of $b$ as long as possible, counts the groups removed, and what is left over is the remainder.

$q$ takes the value $0$ , and $r$ takes the value $a$ .
While $r \geq b$ holds, repeat steps 3 and 4; when it stops holding, continue at step 5.
$r$ takes the value $r - b$ .
$q$ takes the value $q + 1$ ; go back to step 2.
Return $q$ and $r$ , and stop.

Step 2 is a question that is asked every time: before the first iteration and after each one. Steps 3 and 4 form the body of the repetition, what is repeated. Nothing is left to the judgment of whoever executes it: at each moment there is a single next instruction.

The algorithm is slow (to divide a million by three it makes more than three hundred thousand iterations), and the school method of division is much faster; but it is correct, and its simplicity makes it ideal for learning to reason about algorithms. The course will return to the difference between a correct algorithm and an efficient one in the lesson The cost of an algorithm.

Finally, it is worth separating the algorithm from its writing. The algorithm of division by subtraction is the same whether it is written in English, in a diagram, in C++ or in any other programming language: what defines it is the sequence of operations, not the words. A program is the writing of an algorithm in a language that a machine can run, and the lesson Programs, compilers and C++ will explain how that execution takes place. If this is so, a program can be wrong in two very different ways: because the algorithm is incorrect, and then no language saves it, or because the algorithm is correct but was badly written. Telling the two cases apart is half the work of debugging, and that is why the course always writes the algorithm first.

Tracing an algorithm by hand

Reading an algorithm is not enough to know what it does; one has to execute it. Following it by hand, as the machine would, without skipping steps or guessing results, is the most useful skill of a programmer: with it one checks an algorithm before writing it, predicts the output of a program before running it and finds the error in one that fails.

The instrument is the trace table: a column for the number of the step being executed, one column per variable and, if useful, one for the conditions being evaluated; and one row for each step executed. In each row one writes the new value of the variable that changed in that step and leaves blank what did not change, so that the current value of a variable is the last one written in its column. Conditions are written down with their result.

ExampleThe trace of the division of 17 by 5

We trace division by repeated subtraction with $a = 17$ and $b = 5$ . The arrow in the figure points to the step just executed; the dotted line recalls that step 4 goes back to step 2.

Proof

$(q, r) = (0, 17)$
Step 1: the initial values are given. The input satisfies the precondition, because $17 \geq 0$ and $5 > 0$ .
$(q, r) = (1, 12)$
First iteration. In step 2 it is checked that $17 \geq 5$ , so the body is executed: step 3 removes a group of five and step 4 counts it.
$(q, r) = (2, 7)$
Second iteration: $12 \geq 5$ , and the body is executed again.
$(q, r) = (3, 2)$
Third iteration: $7 \geq 5$ , and the body is executed again.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
In step 2 the condition fails, because $2 < 5$ : the algorithm continues at step 5 and returns $q = 3$ and $r = 2$ . The output satisfies the postcondition.

The complete table has twelve rows: step 1, three iterations of three rows each (steps 2, 3 and 4), the check that fails and the return.

Two observations about the table. First: the number of iterations equals the quotient, $3$ , and step 2 was executed once more than the body, $4$ times; this always happens in a repetition of this form, because the last check is the one that fails. Second: the trace shows something that the text of the algorithm does not say at first sight; if $a < b$ , for example $a = 3$ and $b = 5$ , the condition fails the first time, the body is executed zero times, and the output is $q = 0$ , $r = 3$ , which is correct, because $3 = 5 \cdot 0 + 3$ . Forgetting the case in which the repetition is not executed is one of the most frequent errors in designing algorithms, and a trace with small inputs uncovers it.

The trace of one case does not prove that the algorithm is correct: it checks one case. But a well-chosen trace (a common case, a boundary case, the case in which the repetition is not executed) uncovers most errors, and the one that fails says where they are. The lesson Designing correct loops will teach how to go from cases to a proof.

Sequence, decision and repetition

Seen up close, algorithms are built from very few pieces. There are elementary instructions (giving a value to a variable, returning a result) and three ways of combining them.

Sequence: one instruction after another, in order. Steps 3 and 4 of the division are a sequence: first one subtracts, then one counts.
Decision: depending on whether a condition holds or not, one part or another is executed (or one part or nothing). “If $y > m$ , $m$ takes the value $y$ ” is a decision.
Repetition: while a condition holds, a part is executed again and again. Step 2 of the division, with its body, is a repetition.

Each form has a single entry and a single exit, and its interior can in turn be any of the three: the body of a repetition can contain decisions, a branch of a decision can contain a repetition, and so on. If this is so, with the three forms one builds algorithms of any complexity, just as any building is built with a few pieces that fit together. That they suffice to express every algorithm is a well-known result of the theory of programming (Corrado Böhm and Giuseppe Jacopini proved it in 1966); it is not proved here, but the whole course confirms it: the programs to be written in it, however long, will use nothing other than these three forms, written in C++ as if for decision and while or for for repetition, in the lessons Decisions and Loops.

A useful notation for seeing the shape of an algorithm is the flowchart: each instruction is a rectangle, each condition a diamond with two exits (satisfied, which the figure labels $1$ , and not satisfied, $0$ ), and the arrows say which step comes next. It is a notation, not an end in itself: it serves to take in a small algorithm at a glance, but it does not scale, and nobody writes a large program by drawing it.

ExampleThree forms and their composition

The figure draws the three forms with generic instructions $A$ and $B$ and a condition $c$ , and then composes them in the diagram of division by repeated subtraction.

Proof

$A ; B$
Sequence: $A$ is executed and then $B$ ; there is a single entry and a single exit.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Decision: if $c$ holds, $A$ is executed; if not, $B$ . Both branches meet in a single exit.
$c, A, c, A, \ldots, c$
Repetition: $c$ is evaluated; if it holds, $A$ is executed and $c$ is evaluated again; if not, the repetition is left. The condition is evaluated once more than the body.
$a = b \cdot q + r, \quad 0 \leq r < b$
Composition: division by repeated subtraction is a sequence (the initial values, the repetition, the return) whose repetition has as its body another sequence (subtract, count).

Recognizing the three forms in a procedure written in ordinary language is the first step toward translating it. The sign of a decision is an “if,” an “in case” or a “depending on”; that of a repetition, a “while,” an “until,” a “for each” or an “as many times as.” A procedure without any of those words is a sequence, and if it must handle inputs of variable size (a list of numbers, a text), it lacks a repetition.

Does it terminate?

Finiteness is part of the definition of an algorithm, and a repetition is the only place where it can be lost: a sequence of five steps executes five steps, and a decision executes one of its branches; but a repetition executes its body as many times as the condition holds, and nothing guarantees in advance that it will stop holding.

To justify that a repetition terminates, one looks for a quantity, computed from the variables, that satisfies two conditions: it is a natural number (an integer and nonnegative) while the repetition continues, and it strictly decreases on every iteration. If this is so, the repetition terminates: a strictly decreasing sequence of natural numbers cannot be infinite, because each iteration lowers it by at least one, and from a natural number $n$ there are no more than $n$ rungs down to zero. Such a quantity is called a variant or bound function, and the lesson Designing correct loops will use it systematically.

ExampleThe variant of division by subtraction

In division by repeated subtraction, the variant is $r$ . While the repetition continues, $r \geq b > 0$ , so $r$ is a natural number. On every iteration, $r$ takes the value $r - b$ , and since $b > 0$ (precondition), the new value is strictly smaller. Therefore the repetition terminates, and it does so after at most $a$ iterations (in fact, after exactly $q$ iterations, the quotient).

Note where the precondition $b > 0$ was used. If the algorithm is executed with $b = 0$ , step 3 leaves $r$ unchanged, the condition $r \geq 0$ always holds and the repetition never terminates: the algorithm is not wrong; it was given an input that the contract excluded. And if $b$ were negative, $r$ would grow on every iteration. The precondition is not an ornament: it is exactly what is needed for the reasoning to work.

Both conditions of the variant are necessary, and it is easy to get either of them wrong. Consider this procedure, which claims to decide whether a natural number $n$ is even: “while $n \neq 0$ , $n$ takes the value $n - 2$ ; if zero is reached, $n$ was even.” The quantity $n$ decreases on every iteration, and even so the procedure does not terminate if $n$ is odd: with $n = 5$ it passes through $3$ , $1$ , $-1$ , $-3$ , and the condition $n \neq 0$ never fails. What is not satisfied is the other condition: $n$ stops being a natural number, because the condition of the repetition does not prevent it from going below zero. The fix consists in repeating while $n \geq 2$ and deciding at the end according to the value that remains, $0$ or $1$ ; now $n$ is a natural number on every iteration, because one subtracts only when $n \geq 2$ , and it decreases: the procedure terminates.

Deciding whether a repetition terminates is not always easy. A famous example: starting from a natural number $n \geq 1$ , while $n \neq 1$ , if $n$ is even it is divided by two, and if it is odd it is replaced by $3n + 1$ . With $n = 6$ the sequence is $6, 3, 10, 5, 16, 8, 4, 2, 1$ , and it terminates. Nobody has found an $n$ for which it does not terminate, and it has been checked with computers for enormous numbers of values; but nobody has managed to prove that it always terminates: this is the Collatz conjecture, an open problem in mathematics. No known quantity decreases on every iteration. The moral for whoever programs is modest and firm: an algorithm whose termination one cannot justify is not finished.

Frequent errors

Ambiguous steps. “Repeat several times,” “until it is right,” “take a suitable number.” Each step must be executable without understanding the problem; otherwise, it is badly written.
Forgetting the case in which the repetition is not executed. Every repetition with the condition at the beginning can execute its body zero times. One must always ask what the algorithm returns in that case, and a trace with a minimal input answers it.
Specifying with an example. “For 17 and 5 it gives 3 and 2” is not a specification; the relation is written as a general condition, and the example illustrates it.
Confusing the algorithm with its program. A program that fails may have a wrong algorithm or a wrong writing of it. Whoever did not write the algorithm beforehand does not know which of the two things to look for.
Taking termination for granted. That a quantity decreases is not enough: it must also be a natural number while the repetition goes on.

Solved problems

Solved problem 1The largest of three numbers, with ties

Write an algorithm that satisfies the specification of the maximum of three numbers from the first section, and trace it by hand for the inputs $(7, 2, 5)$ and $(4, 9, 9)$ .

Solution

$m = x$
Idea: one goes through the input keeping the largest value seen so far in a variable $m$ . First step: $m$ takes the value $x$ . After it, $m$ is the maximum of the values seen, which are only $x$ .
$m = \max(x, y, z)$
Second step: if $y > m$ , $m$ takes the value $y$ . Third step: if $z > m$ , $m$ takes the value $z$ . Fourth step: return $m$ . These are three instructions in sequence, two of them decisions without an alternative branch.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Trace for $(7, 2, 5)$ : after the first step $m = 7$ ; in the second, $2 > 7$ is false and $m$ does not change; in the third, $5 > 7$ is false and $m$ does not change. It returns $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Trace for $(4, 9, 9)$ : after the first step $m = 4$ ; in the second, $9 > 4$ and $m$ becomes $9$ ; in the third, $9 > 9$ is false and $m$ does not change. It returns $9$ , which is correct: the tie requires no special treatment.
$m \geq x, \quad m \geq y, \quad m \geq z$
Justification: after each step, $m$ is one of the values seen and none of them exceeds it. This is true after the first step, and each decision preserves it: if the new value is greater, it becomes $m$ ; if not, it does not exceed $m$ . At the end all three have been seen, and $m$ satisfies the postcondition.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Had $y \geq m$ been written instead of $y > m$ , the result would be the same, because in case of a tie an equal value is assigned. The choice between $>$ and $\geq$ would matter if the position of the maximum were also requested: with $>$ the first of the tied positions is returned, and with $\geq$ the last; the formula calls the position $p$ .

Solved problem 2The leap year, corrected with a counterexample

In the Gregorian calendar, a year is a leap year if it is divisible by $4$ , except those divisible by $100$ , which are leap years only if they are also divisible by $400$ . A student proposes the algorithm “if the year is divisible by $4$ , return yes; if not, return no.” Find a year in which it fails and write a correct algorithm, with its specification.

Solution

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Specification. Input: an integer $n \geq 1583$ (the Gregorian calendar has been in force since October 1582). Output: yes or no. Relation: the output is yes exactly when $n$ is divisible by $4$ and not by $100$ , or is divisible by $400$ .
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
The proposed algorithm is right for most years, and that is why it seems correct. To refute it, a year divisible by $100$ and not by $400$ suffices: $1900$ is divisible by $4$ , and the algorithm says yes; but $1900$ was not a leap year.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Corrected algorithm, in three chained decisions. Step 1: if $n$ is divisible by $400$ , return yes and stop. Step 2: if $n$ is divisible by $100$ , return no and stop. Step 3: if $n$ is divisible by $4$ , return yes; if not, return no.
$2000, \quad 1900, \quad 2024, \quad 2023$
The order of the questions is essential: they go from the most particular rule to the most general. If divisibility by $4$ were asked about first, the year $1900$ would receive yes before reaching the exception. Trace for four years, one for each case: $2000$ (step 1: yes), $1900$ (step 2: no), $2024$ (step 3: yes), $2023$ (step 3: no).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
The moral is not only about calendars: an algorithm is refuted by a single counterexample, and counterexamples are sought at the boundaries of the rules, not in the common cases. Testing with $2024$ , $2020$ and $2016$ would not have uncovered anything.

Solved problem 3How many iterations division by subtraction makes

Trace by hand division by repeated subtraction with $a = 20$ and $b = 5$ , and with $a = 0$ and $b = 7$ . Then justify that for every admissible input the algorithm terminates after exactly $q$ iterations and that its output satisfies the postcondition.

Solution

$20 = 5 \cdot 4 + 0$
Trace with $a = 20$ , $b = 5$ : $r$ passes through $20$ , $15$ , $10$ , $5$ , $0$ , and $q$ through $0$ , $1$ , $2$ , $3$ , $4$ . The fifth check, $0 \geq 5$ , fails. Output: $q = 4$ , $r = 0$ . Here the boundary case is exact division: the fourth iteration takes place because $5 \geq 5$ , and that is why the condition must be $\geq$ and not $>$ .
$0 = 7 \cdot 0 + 0$
Trace with $a = 0$ , $b = 7$ : the first check, $0 \geq 7$ , fails; the body is not executed even once. Output: $q = 0$ , $r = 0$ , which is correct.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
A relation that is preserved. Before the first iteration, $b \cdot q + r = b \cdot 0 + a = a$ . On every iteration $r$ decreases by $b$ and $q$ increases by $1$ , so $b \cdot q + r$ does not change. Therefore the equality holds after every iteration.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Termination. While the repetition goes on, $r \geq b > 0$ , and $r$ is a natural number; on every iteration it decreases by $b \geq 1$ . A strictly decreasing sequence of natural numbers is finite: the repetition terminates.
$a = b \cdot q + r, \quad 0 \leq r < b$
On termination, the condition has failed: $r < b$ . Moreover $r \geq 0$ , because $b$ is subtracted only when $r \geq b$ . Together with the relation that is preserved, the output satisfies the postcondition; and since $q$ counts the iterations, the number of iterations is the quotient.

Online exercises

Exercise 1Counting the iterations

Trace the following algorithm by hand and write in the box the value it returns, just the number.

$n$ takes the value $29$ , and $k$ takes the value $0$ .
While $n > 1$ holds, repeat steps 3 and 4; when it stops holding, continue at step 5.
If $n$ is even, $n$ takes the value $n / 2$ ; if it is odd, $n$ takes the value $n + 1$ .
$k$ takes the value $k + 1$ ; go back to step 2.
Return $k$ .

Your browser checks your answer instantly, without grading it.

Write your answer here

Hint

Make the table: $n$ goes from $29$ to $30$ in the first iteration. Count one iteration for each change of $n$ , until $n$ equals $1$ .

Exercise 2The missing condition

The following algorithm, written in the abbreviated form, should compute the quotient and the remainder of division by repeated subtraction, but the condition of the repetition is missing. Replace the line of underscores with the correct condition, without changing anything else.

Your browser checks your answer instantly, without grading it.

Write your answer here

Hint

Trace the algorithm by hand with $a = 10$ and $b = 5$ : the second iteration must take place even though the remainder is exactly $5$ .

Proposed problems

Each problem has a hint, best opened only after attempting it, and an answer, which appears after the hint is opened.

Proposed problem 1Specifying the order of three numbers

Write the specification of the problem “sort three numbers” (input, output and relation) and point out which decisions it forces that the statement did not make. Then check that the specification rules out these two outputs for the input $(5, 2, 5)$ : $(2, 5, 6)$ and $(2, 5, 5, 5)$ , and that it admits $(2, 5, 5)$ .

Hint

A “sorted” output may have nothing to do with the input. What condition links the numbers of the output with those of the input, including the repeated ones? Increasing or decreasing? Strict or not?

Answer

Input: three numbers $x$ , $y$ , $z$ . Output: three numbers $u$ , $v$ , $w$ . Relation: $u \leq v \leq w$ , and $(u, v, w)$ is a rearrangement of $(x, y, z)$ , that is, it contains the same values with the same repetitions. Decisions that the statement did not make: the direction (here, from smallest to largest); that the order is not strict ( $\leq$ and not $<$ , because with repeated values a strict order is impossible); and that the output must be a rearrangement. $(2, 5, 6)$ is sorted but contains a $6$ that was not there; $(2, 5, 5, 5)$ has four values; $(2, 5, 5)$ satisfies both conditions. Without the rearrangement condition, $(0, 0, 0)$ would be a correct output for any input.

Proposed problem 2The digits of a number, from right to left

Write an algorithm in numbered steps that receives a natural number $n$ and returns its digits from the last to the first (for $4072$ , it returns $2$ , $7$ , $0$ , $4$ ), using only the quotient and the remainder of division by $10$ . Trace it by hand for $4072$ and for $0$ , and justify that it terminates for every $n$ .

Hint

The remainder of dividing by $10$ is the last digit, and the quotient is the number without it. Decide whether the condition is asked before or after returning a digit, and look at what happens with $n = 0$ , which has one digit.

Answer

A correct algorithm: (1) return the remainder of dividing $n$ by $10$ ; (2) $n$ takes the value of the quotient of dividing $n$ by $10$ ; (3) if $n > 0$ , go back to step 1; if not, stop. The question comes after the body, so the body is executed at least once: for $n = 0$ it returns $0$ , which is its only digit. If the question were asked at the beginning (“while $n > 0$ ”), for $n = 0$ nothing would be returned; this is the error of forgetting the case in which the repetition is not executed. Trace for $4072$ : $2$ , $7$ , $0$ , $4$ are returned, and $n$ passes through $407$ , $40$ , $4$ , $0$ . Termination: the variant is $n$ , a natural number; if one goes back to step 1 it is because $n > 0$ , and for $n \geq 1$ the quotient by $10$ is strictly smaller than $n$ , so $n$ strictly decreases on every iteration.

Proposed problem 3Making change in coins

Coins of $50$ , $10$ and $1$ units are available, in unlimited quantity. Specification: input, a natural number $m$ ; output, three natural numbers $c_{50}$ , $c_{10}$ , $c_1$ with $50 c_{50} + 10 c_{10} + c_1 = m$ and the smallest possible number of coins, $c_{50} + c_{10} + c_1$ . Someone proposes the following algorithm. Find an input on which it fails, explain each defect and correct it.

$c_{50}$ , $c_{10}$ and $c_1$ take the value $0$ .
If $m \geq 50$ , $c_{50}$ takes the value $c_{50} + 1$ and $m$ takes the value $m - 50$ .
While $m > 10$ : $c_{10}$ takes the value $c_{10} + 1$ and $m$ takes the value $m - 10$ .
While $m > 0$ : $c_1$ takes the value $c_1 + 1$ and $m$ takes the value $m - 1$ .
Return $c_{50}$ , $c_{10}$ and $c_1$ .

Hint

The sum of the coins is always $m$ ; what can fail is the number of coins. Try an exact multiple of $10$ and an amount of more than $100$ , and ask yourself which way of combining steps step 2 uses and which one it should use.

Answer

There are two defects. First, step 3 uses $m > 10$ : with $m = 10$ it returns no coin of $10$ and returns ten of $1$ , instead of one. Second, step 2 is a decision where a repetition is needed: with $m = 120$ , the algorithm as written returns one coin of $50$ , six of $10$ and ten of $1$ (seventeen coins), and even with step 3 already corrected it would return one of $50$ and seven of $10$ (eight), instead of two of $50$ and two of $10$ (four). The input $m = 100$ shows both defects: the algorithm returns one of $50$ , four of $10$ and ten of $1$ , fifteen coins, instead of two. Correction: step 2, “while $m \geq 50$ , …”; step 3, “while $m \geq 10$ , …”. Corrected in this way, the algorithm always takes the largest coin that fits, and with these three coins that gives the smallest number: the units digit of $m$ can only be paid with coins of $1$ , and of what remains it is best to pay as much as possible with coins of $50$ , because five of $10$ are worth as much as one of $50$ . With other coins, for example of $1$ , $3$ and $4$ for $m = 6$ , always taking the largest one no longer gives the minimum ( $4 + 1 + 1$ versus $3 + 3$ ).