Algorithms

1. Name the inputs: what does the algorithm receive? Give each one a name.
2. Name the output: what is wanted at the end, and in what form, displayed or given back?
3. Write the steps in order, one instruction per line, each one applicable without deciding anything.
4. Check that it ends: count the steps, or say what makes the last one come.

Read length
Read width
p ← 2 × (length + width)
Display p

length = int(input())
width = int(input())
p = 2 * (length + width)
print(p)

Each construction of the pseudo-code has a standard Python writing. Translating is replacing line by line, keeping the order and the indentation.

Pseudo-code	Python
Read n	n = int(input())
Display x	print(x)
x \(\leftarrow\) 3	x = 3
If c then …Else …End If	if c: …else: …
Else If c then	elif c:
a = b  a \(\neq\) b	a == b  a != b
a \(\leqslant\) b  a \(\geqslant\) b	a <= b  a >= b
and  or  not	and  or  not
a \(\times\) b  a \(\div\) b	a * b  a / b
quotient when a is divided by b	a // b
remainder when a is divided by b	a \pourcent{} b
For k from 1 to n …End For	for k in range(1, n + 1): …
While c …End While	while c: …
Function f(a) …Return r	def f(a): …return r

In the other direction, read the Python line, name what it does in a sentence, and write that sentence as a pseudo-code line. Three places need care. Read is written by Python with two functions at once, and assumes here that the value read is a whole number. The bounded loop does not write its bounds the same way. And the End If, End For and End While have no Python writing at all: what tells Python where a block stops is the indentation. The sign = is the trap of the table: in Python it assigns, where pseudo-code writes \(\leftarrow\); and to compare, pseudo-code writes = where Python writes ==. The sign \(\div\) is the other one: it is the division that keeps the decimals, and the division of whole numbers that drops them is written quotient when a is divided by b, never with the same sign.

1. Draw the table: one column per variable of the algorithm, one column Display, and a first column for the instruction.
2. Take the instructions one at a time, in order, never two at once.
3. Compute the right-hand side first, with the values of the previous row, then write the new row.
4. Copy the unchanged values onto the new row, so that each row can be read alone.
5. Read the answer in the last row, or in the Display column if the question is about what is shown.

a ← 3
b ← a + 2
a ← b × 2
Display a

x ← 4
y ← 9
x ← y
y ← x
Display x
Display y

If a ≥ 0 and a ≤ 10 then
    Display "in range"
Else
    Display "out of range"
End If

1. Add a condition column to the state table, holding true or false for the row where the condition is evaluated.
2. Evaluate the condition with the values of the previous row, and write the result down: it is an answer, not a computation to redo later.
3. Follow one branch only, and write its instructions as rows; the instructions of the other branch produce no row at all.
4. Continue after the End If, whichever branch was taken.

If a > b then
    m ← a
Else
    m ← b
End If
Display m

n = 12
if n < 10:
    price = 5
elif n < 20:
    price = 4
else:
    price = 3
print("Total:", price * n)

Total: 48

1. Write the rows before the loop as usual: the accumulator receives its starting value there.
2. Write one row per turn, labelled by the value of the counter, and not one row per instruction of the body when the body is a single line.
3. Compute with the values of the previous row, turn after turn, never jumping ahead.
4. Count the turns and check the count against the bounds before reading the answer.
5. Write the rows after the loop: the accumulator is read there, with the value of the last turn.

s ← 0
For k from 1 to 4
    s ← s + k
End For
Display s

total = 0
for k in range(1, 6):
    total = total + k * k
print(total)

55

total ← 0
For k from 1 to 5
    total ← total + k × k
End For
Display total

1. Name the quantity that the body changes at every turn, among those the condition looks at.
2. Say that it is a whole number and in which direction it moves, strictly, at every turn: such a quantity is called a variant of the loop.
3. Say which bound the condition keeps it on the right side of, as long as the loop turns.
4. Conclude, and point at the column of the state table where that quantity is read, turn after turn.

1. Add a condition column to the state table: on a turn row it holds the test that licensed that turn, evaluated on the state of the row before.
2. Write a row per turn as for a bounded loop, once the condition has been found true.
3. Write a last row labelled end, carrying no instruction, where the condition is false: that row is what ends the trace, and forgetting it is forgetting why the loop stopped.
4. Read the number of turns as the number of rows labelled turn.

p ← 1
n ← 0
While p ≤ 100
    p ← p × 2
    n ← n + 1
End While
Display n

n ← 7
While n ≠ 0
    n ← n - 2
End While

n ← 7
While n > 0
    n ← n - 2
End While

1. Read the header: what are the parameters called, and how many are there?
2. Find every Return: each one is an exit, and the value it gives back is the result of that exit.
3. Say in one sentence what the function does from its inputs, without describing its lines.
4. Trace one call by hand, with a value for each parameter, to check that sentence.

Function max_of_two(a, b)
    If a > b then
        Return a
    Else
        Return b
    End If
End Function

def max_of_two(a, b):
    if a > b:
        return a
    else:
        return b

print(max_of_two(7, 12))
print(max_of_two(max_of_two(3, 8), 5))

12
8

1. Write the expected result first, for each test case, before executing anything; in the table, a column Expected carries it beside the value the algorithm produces.
2. Take an ordinary case and execute the algorithm by hand on it.
3. Take the limit cases: what happens for zero, for one, for equal values, for a negative value?
4. Compare, row by row, what the table gives with what was expected, and stop at the first row where they differ.
5. Conclude carefully: a case that fails proves the algorithm wrong; cases that pass prove nothing about the ones not tried.

m ← 0
For k from 1 to 4
    Read x
    If x > m then
        m ← x
    End If
End For
Display m

1. Find a case that fails, and write down the result expected on it.
2. Execute by hand and, at each row, ask what the value should be at that point, on a case small enough to be followed without the algorithm.
3. Stop at the first row where the table and the expectation part company: the fault is in the instruction of that row, not before.
4. Say what that instruction does and what it should have done, then correct it and re-run every test case, the ones that used to pass included.

Function count_positive(a, b, c)
    n ← 0
    If a > 0 then
        n ← n + 1
    End If
    If b > 0 then
        n ← n + 1
    End If
    If c > 0 then
        n ← 1
    End If
    Return n
End Function

1. Name the test that changes answer at the number sought, and a starting point where it answers one way.
2. Choose the step: it is the width of the bracket obtained, so a step of \(0.1\) gives one decimal, a step of \(0.01\) gives two.
3. Walk step by step as long as the test keeps its first answer.
4. Read the bracket: the first point where the test changed, and the one before it.
5. Sweep with whole numbers when the step is a decimal: count the steps in a whole counter and divide once at the end, never add the step to itself.

k ← 10
While k × k < 200
    k ← k + 1
End While
Display k - 1
Display k

k = 10
while k * k < 200:
    k = k + 1
print((k - 1) / 10)
print(k / 10)

1.4
1.5

1. Say what one turn advances: one step, one unit of a counter, one halving of a width.
2. Say what stops the loop: the bound its condition tests.
3. Count how many advances fit between the start and that bound, as a number written with what the algorithm receives.
4. Check the count against a trace already written, on a small case, where the turns can be counted by hand.
5. Never measure a run: the count is a property of the algorithm, and a machine that is twice as fast changes nothing to it.

x = 0
for k in range(10):
    x = x + 0.1
print(x)
print(x == 1)

0.9999999999999999
False

1. Start from a bracket that holds the answer, and name the test that tells the two halves apart.
2. Take the middle of the current bracket.
3. Keep the half where the test still changes answer, and throw the other away.
4. Repeat as long as the width is above the precision wanted.
5. Read the bracket, and say the sentence that stayed true at every turn.

a ← 1
b ← 2
While b - a > 0.1
    m ← (a + b) ÷ 2
    If m × m < 2 then
        a ← m
    Else
        b ← m
    End If
End While
Display a
Display b

a = 1
b = 2
while b - a > 0.1:
    m = (a + b) / 2
    if m * m < 2:
        a = m
    else:
        b = m
print(a)
print(b)

1.375
1.4375

1. Pair the factors: if k divides n, then the quotient when n is divided by k divides n too, and the two multiply to n.
2. Note that one of the two is small: in a pair whose product is n, both cannot be above the square root of n, or their product would pass n.
3. Test only the small ones, that is the k such that k \(\times\) k \(\leqslant\) n, and count each pair found as two factors.
4. Count once the k whose pair is itself, that is when k \(\times\) k = n.

The test k \(\times\) k \(\leqslant\) n is what replaces a square root here: it asks the same question with a multiplication, which is exact on whole numbers where a square root would not be.

c ← 0
k ← 1
While k × k ≤ 36
    If remainder when 36 is divided by k = 0 then
        If k × k = 36 then
            c ← c + 1
        Else
            c ← c + 2
        End If
    End If
    k ← k + 1
End While
Display c

1. Reject the numbers below 2 first: they are not prime, and the loop would say nothing about them since it makes no turn.
2. Walk the possible factors from 2, as long as k \(\times\) k \(\leqslant\) n.
3. Leave at the first factor found: one is enough to answer no, and finishing the loop would cost turns for nothing.
4. Answer yes after the loop, which is reached only when no factor was found.

Function is_prime(n)
    If n < 2 then
        Return false
    End If
    k ← 2
    While k × k ≤ n
        If remainder when n is divided by k = 0 then
            Return false
        End If
        k ← k + 1
    End While
    Return true
End Function

def is_prime(n):
    if n < 2:
        return False
    k = 2
    while k * k <= n:
        if n % k == 0:
            return False
        k = k + 1
    return True

print(is_prime(91))
print(is_prime(97))

False
True

1. Ending: the second number of the pair is a whole number, and at every turn it becomes the remainder when a is divided by b, so it is strictly smaller than the b it replaces, and a remainder is never negative. A whole number cannot decrease for ever above zero, so the second number reaches zero.
2. Correctness: write the division as \(a = q \times b + r\). A number that divides a and b divides \(a - q \times b\), that is r; and a number that divides b and r divides \(q \times b + r\), that is a. The two pairs therefore have exactly the same common factors, and the highest of them travels unchanged from turn to turn.
3. Reading the answer: when the second is zero, the common factors of the pair are the factors of the first, whose highest is the first itself.
4. Point at the column of the state table that carries the argument: the second number, strictly decreasing, is the variant; the HCF, unchanged, is what stays true at every turn.

a ← 1071
b ← 462
While b ≠ 0
    r ← remainder when a is divided by b
    a ← b
    b ← r
End While
Display a

The system is \(a_1x + b_1y = c_1\) and \(a_2x + b_2y = c_2\). Multiplying the first equation by \(b_2\), the second by \(b_1\), and subtracting the second from the first eliminates \(y\): \((a_1b_2 - b_1a_2)x = c_1b_2 - b_1c_2\). The number \(d = a_1b_2 - b_1a_2\) is called the determinant of the system. When \(d\) is not zero, dividing by it gives \(x = (c_1b_2 - b_1c_2) \div d\), and eliminating \(x\) in the same way gives \(y = (a_1c_2 - c_1a_2) \div d\).

1. Compute the determinant \(d = a_1b_2 - b_1a_2\) from the four coefficients of the unknowns.
2. Read the case on it: when \(d\) is zero the system has no single solution, and the algorithm says so instead of computing.
3. Otherwise apply the two quotients that solve the system, and display them.
4. Count what it costs: no loop, so the same operations for every system, and the branch is the only thing that varies.

d ← a1 × b2 - b1 × a2
If d = 0 then
    Display "no single solution"
Else
    x ← (c1 × b2 - b1 × c2) ÷ d
    y ← (a1 × c2 - c1 × a2) ÷ d
    Display x
    Display y
End If

a1 = 2
b1 = 3
c1 = 8
a2 = 5
b2 = -1
c2 = 3
det = a1 * b2 - b1 * a2
if det == 0:
    print("no single solution")
else:
    print((c1 * b2 - b1 * c2) / det)
    print((a1 * c2 - c1 * a2) / det)

1.0
2.0

1. Name the outcome counted, and the number of draws.
2. Create the counter at 0 before the loop, as for any accumulator.
3. Repeat the draw the number of times chosen, and count the draws that give the outcome.
4. Divide the counter by the number of draws, after the loop.
5. Say what the result is worth: it is a frequency, not a probability. With many draws it is usually close to the probability; it may happen to fall exactly on it, and that is chance too, not a computation.

c ← 0
For i from 1 to 6
    Read d
    If d = 6 then
        c ← c + 1
    End If
End For
Display c

import random

c = 0
for i in range(1000):
    d = random.randint(1, 6)
    if d == 6:
        c = c + 1
print(c / 1000)