4.3. Think, write and test algorithms

Writting an algorithm to solve a problem acts in several steps. From a clear statement, the analyst should:

  1. Extract and formalize input data

  2. Determine what will be the result

  3. Elaborate the process that will produce the result from input data

4.3.1. Thinking and writting algorithm

In the major cases, the analyst is not producing the “good” algorithm the first time. It is common to produce several versions of an algorithm until it reaches the objectives. One can retain some general method to write an algorithm:

  • Read and understand the statement.

  • Imagine the discussion between the user and the processor: what should the user give to the processor and what does it return in exchange.

  • Solve the problem by hand on typical example to verify the understanding and begin to structure what kind of instructions will be necessary.

  • Isolate the problem data and make a first version of variable declarations.

  • Organise ideas to find complex successive instructions that can solve the problem. Take care about conditions and repetitive instructions that can emerge from any reformulation of the statement.

  • Treat independantly each complex instruction in elementary instructions that will represent instruction blocks of the written algorithm. This step may require to add new variables to the declaration section of the algorithm. If some operations seems very complex, do not hesitate to structure the algorithm using functions.

4.3.2. Testing: trace table

When a version of an algorithm has been written, it should be tested and eventually corrected. This is a complex step in algorithm writting because the more the tests will be exhaustive, the more the validation of the safety of the produced algorithm will be. For example, if one of the input of the algorithm is an integer, one can test positive, nul and negative values for this integer.

There are at least two possibilities to test an algorithm:

  • Traduce it in a programming language and run it on a computer on different data sets.

  • Test by hand using a trace table

A trace table is representing the value of variables (and eventually the screen output) at each line during the algorithm execution.

Let us take the example of the conversion algorithm seen in section A first example. This algorithm is recalled hereafter:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
Algorithm convertTemperatureCtoK
--------------------------------
Description
  Print temperature in Kelvin from input read temperature in Celcius
--------------------------------
Constants
  zeroC = 273.15
Variables
  tempC : real
  tempK : real
Start
  Print("Enter temperature in Celcius :")
  Read(tempC)
  tempK <- tempC + zeroC
  Print(tempC, "°C is ", tempK, "K")
End

A possible trace table for this algorithm is:

line

zeroC

tempC

tempK

screen

7

273.15

12

Enter temperature un Celcius :

13

42.0

14

315.15

15

42.0°C is 315.15K

Testing this algorithm with a temperature of -300 °C will send an unphysical result and shows one of the algorithm limitations.

4.3.3. Basic exercices

Here are presented some basic exercices that needs to be understand before writting more complex algorithms. This section is a practicing section that should be done sequentially to understand the basic instructions to build algorithms.

4.3.3.1. Permutation

The aim is to permut the content of two variables. This kind of instruction may be used when sorting data in arrays for example. Consider the following algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
Algorithm permutation_V0
------------------------
Description
  Permuts the content of variables var1 and var2
------------------------------------------------
Variables
  var1 : integer
  var2 : integer
Start
  var1 <- 25
  var2 <- 63

  var2 <- var1
  var1 <- var2

  Print("Permuted variables are: var1 = ", var1, " and var2 = ", var2)
End

  1. Write the trace table of the algorithm permutation_V0 and explain why it is wrong.

  2. Propose a new version permutation_V1 that correct the algorithm (use a third variable).

4.3.3.2. Accumulation

The value of an accumulation variable increases during the execution of the algorithm. As example, the following algorithm proposes to accumulate points during darts game with 3 throws.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
Algorithm accumulation_V0
-------------------------
Description
  Three successive throws permits to accumulate point at darts game
--------------------------------
Variables
  points : integer   /to read points of a throw
  score : integer    /to accumulate points
Start
  Print("Enter the first throw points: ")
  Read(points)
  score <- score + points
  Print("Enter the second throw points: ")
  Read(points)
  score <- score + points
  Print("Enter the third throw points: ")
  Read(points)
  score <- score + points

  Print("Your total score is: ", score)
End

  1. This algorithm is wrong. Explain why.

  2. Propose a new version accumulation_V1 that correct the algorithm

4.3.3.3. if conditional instructions

Consider the two following algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Algorithm condition1
--------------------
Variables
  e : integer
Start
  Print("Enter an integer:")
  Read(e)
  if (e<0) then
    e = e + 10
  else
    e = e - 10
  endif
  Print("New value: ", e)
End

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
Algorithm condition2
--------------------
Variables
  e : integer
Start
  Print("Enter an integer:")
  Read(e)
  if (e<0) then
    e = e + 10
  endif
  if (e>=0) then
    e = e - 10
  endif
  Print("New value: ", e)
End

  1. Write the trace table for each algorithm with value for e = 20, -20 and -2

  2. Are these two algorithm equivalent ?

We want an algorithm that asks for three values entered by user and prints the maximum.

  1. Write this algorithm.

  2. Verify your algorithm using a trace table and different input values.

4.3.3.4. While repetitive instructions

Consider the following algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Algorithm repetitive1
---------------------
Variables
  x : integer
Start
  x <- 42
  while (x>=0)
    Print ("Current value: ", x)
    x <- x - 11
  endwhile
  Print ("Last value: ", x)
End

  1. Write the trace table of this algorithm and give the final value for x.

Consider the following algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Algorithm repetitive2_V0
------------------------
Variables
  i, x : integer
Start
  i <- 0
  x <- 2
  while (x < 4)
    Print ("Current value: ", x)
    i <- i + 1
  endwhile
  Print ("Last value: ", x)
End

  1. This algorithm is wrong as it contains an infinite loop. Propose a corrected version for this algorithm and write its trace table.

4.3.3.5. For repetitive instruction

Consider the following algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
Algorithm accumulation_V2
-------------------------
Description
  3 successive throws permits to accumulate point at darts game
--------------------------------
Variables
  points : integer   /to read points of a throw
  score : integer    /to accumulate points
  i: integer         /loop variable
Start
  score <- 0
  for i from 1 to 3 (include)
    Print("Enter the ", i, " throw points: ")
    Read(points)
    score <- score + points
  endfor

  Print("Your total score is: ", score)
End

  1. Write the trace table of this algorithm and compare it to the preceding algorithm accumulation_V1 of section Accumulation.

  2. Write an algorithm that asks n real to a user (n is also given by user) and prints the average.

4.3.3.6. Using and writting functions

Consider that you dispose the description (and not the definition) of the following functions:

units(number : integer) : integer
  /Returns the number of units in the positive integer number
  /ex : units(56) will return 6

tens(number : integer) : integer
  /Returns the number of tens in the positive integer number
  /ex : units(56) will return 5

hundreds(number : integer) : integer
  /Returns the number of hundreds in the positive integer number
  /ex : units(56) will return 0

  1. Write an algotrithm that asks user for a positive number and prints the reversed corresponding number (ex : 156 -> 651)

  2. Write the two functions tens and hundreds, the units fonction definition being:

1
2
3
4
5
6
7
8
9
Function units(number : integer) : integer
------------------------
Description
  Returns the number of units in the positive integer number
  ex : units(56) will return 6
------------------------
Start
  return number%10     / % is for the remainder of euclidian division
End

4.3.3.7. Playing with arrays

Consider the following algorithm that allows a user to enter 5 real numbers in an array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Algorithm playArrays
--------------------
Constants
  N = 5
Variables
  myArray : array[5] of real
  i : integer
Start
  for i from 0 to N-1
    Print ("Enter case", i+1, " of array:)
    Read(myArray[i])
  endfor
End

  1. Add to this algorithm instructions for printing the array.

  2. Add to this algorithm instructions for reversing the array. You can help with the permutation algorithm of section Permutation under a function form.

Example of reversed array:

original array

3.2

40.0

1.0

5.0

-26.1

reversed array

-26.1

3.2

  1. Write a function that sorts the array (ascending or descending)