Pseudocode

Introduction

Pseudocode is a tool for representing algorithms without the use of a particular programming language and related syntax.

It is written in a combination of plain English and common symbols, and describes, in a detailed step-by-step manner, the processes used in the algorithm.

There are some basic principles to be followed in using pseudocode which include:

  • Have only one statement per line.
  • Use indentation to show the hierarchy of processes within an algorithm such as repeating sections and conditional decisions.
  • End nested processes with an end keyword (end if, end while).

The constructs of pseudocode

Entering values into an algorithm

Values can be entered into an algorithm as part of the algorithm name or as input within the algorithm.

Assigning values to variables

A variable is a string of one or more letters that acts as a placeholder that can be assigned different values. For example:

${\large x \leftarrow 5}$ means ‘assign the value 5 to the variable ${\large x}$’.

product ${\large \leftarrow 3}$ means ‘assign the value 3 to the variable product’.

${\large x \leftarrow x + 1}$ means ‘assign the value ${\large x + 1}$ to the variable ${\large x}$’.

Decisions in pseudocode

if – then blocks provide a means of making decisions within an algorithm. Certain instructions are only followed if a condition is true.


 

if condition is true  then

follow these instructions

end if


 

We can expand this process by specifying alternative instructions if the condition is false.


 

if condition is true  then

follow these instructions

else

follow these instructions

end if


An example for finding the smaller of two numbers a and b.


 

Algorithm: minimum of two numbers

input a, b

if a ≤ b then

print a

else

print b

end if


 

Further decisions can be added inside if – then blocks to include more conditions are nested (indented) within the previous block.


 

if first condition is true then

follow these instructions

else if second condition is true then

follow these instructions

else

follow these instructions

end if


Repetition

Loops are used to repeat a process. How many repetitions (iterations) take place is controlled by either specifying and counting the number of times (a for loop) or by specifying a condition which must be met for the process to continue, otherwise it ends (a while loop). An example of each of these approaches is shown below:

For loops provide a means of repeatedly executing the same set of instructions in a controlled way. A counter (i) is increased by one, each time through the loop.


 

for i from 1 to n

follow these instructions

end for


 

Note: We will follow the convention that `from 1 to n’ is inclusive. For example: for i from 1 to 3, i takes values 1, 2 and 3,

Algorithm: First 5 perfect squares


 

for i from 1 to 5

print i2

end for


 

While loops provide another means of repeatedly executing the same set of instructions in a controlled way. This is achieved by performing iterations as long as some condition remains true.


 

while condition is true

follow these instructions

end while


 

Algorithm: Perfect squares less than 1000


 

x ← 1

while x2 < 1000

x ← x + 1

print (x - 1)2

end while


Functions

Are sections of pseudocode that can be used to complete a specific task. Once a function is defined, it can be used (called) within another algorithm. A function takes one or more input values and returns an output value.


 

define function_name (input for function):

follow these instructions

return output

 

define factorial(n):

product 1

for i from 1 to n

product ← product x i

end for

return product


Examples

Numerical integration using trapezium method

Algorithm


 

define f(x)

return (enter required function rule)

sum ← 0

a ← lowest x-value

b ← highest x-value

n ← number of trapeziums

h ← (b-a)/n

left ← a

right ← a + h

for  from 1 to  n

strip ← 0.5(f(left) + f(right)) x h

sum ← sum + strip

left ← left + h

right ← right + h

end for

print  sum


Comments

The trapezium method algorithm gives an approximation of ${\large \int_a^bf(x)dx}$ 
The function being considered is first defined.
For example, ${\large f(x) = x^2}$, choose a = 1 and b = 4 to approximate ${\large \int_1^4x^2dx}$ 
n is the number of trapeziums chosen. 
In the for loop the area of each trapezium is calculated as you move from left to right and added to sum.
The final value of sum is printed.

The trapezium algorithm may be implemented by using a function structure.
The function f must be defined first.

define  Trap(a, b, n)
(Insert algorithm as shown)
return (sum)

The advantage of this is that it may be implemented simply by changing the values of the variables.

Estimate of the long-term average for the number of rolls to get a six

Algorithm


 

sum ← 0

for from 1 to 1000

outcome ← 0

count ← 0

while outcome ≠ 6

outcome ← randominteger(1, 6)

count ← count + 1

end while

sum ← sum + count

end for

print sum/1000


Comments

Many devices have a random number function. We use the function: randominteger(1, 6) to return one of the numbers 1,2,3,4,5,6 randomly.

The while loop continues until the value 6 is given by randominteger(1, 6). The variable count  gives the number of iterations before a 6.

The for loop repeats this 1000 times. The variable sum gives the total of the 1000 values of count.

The print statement is for the average

Bisection Method for finding x-intercepts

Algorithm


 

define  f(x)

return(enter required function rule)

a ← lower guess

b ← upper guess

c ← (a + b)/2

t ← tolerance

if  f(a) × f(b) > 0 then

print "Incorrect initial guesses"

else

while b - a > 2×t

if f(af(c) < 0 then

b ← c

else

a ← c

end if

c ← (a+b)/2

end while

print(c)

end if


Comments

Function f(x) is chosen.
For example:
define f(x)

return x2 – 2

Good choices for a and b are a = 1 
and a = 2. (f(1) f(2) > 0.)

If this is the choice we go to the else section of the algorithm and the outer if statement has done its job.

The while loops requires that we continue the iteration until the desired accuracy is reached.

The if statement inside the algorithm ensures that we continue to choose values for which there is a sign difference. For each iteration an average of the new pair is determined by the if statement is calculated.


Euler’s method for differential equations

Consider a differential equation

${\large \frac{dy}{dx} = f(x,y)}$

Define a function euler${\large (x_0, y_0, h, xfin)}$ where h is the step size and ${\large xfin}$ is the value at which we want to approximately solve the differential equation.

Algorithm


 

define  function( x, y )

return(enter required function rule)

define euler${\large (x_0, y_0, h, xfin)}$

${\large y ← y_0}$

${\large x ← y_0}$

while ${\large x < xfin}$

${\large y ← y + h x f(x, y)}$

${\large x ← x + h}$

end while

return ${\large (xfin, y)}$


Comments

The differential equation is ${\large \frac{dy}{dx} = f(x,y)}$

For example ${\large f(x,y) = xy}$.

${\large x_0 }$ is the initial x value and ${\large h_0 }$ the corresponding y value. Let h = 0.1

If you start at (1,2) the next ordered pair is (1.1, 2.2) and the following (1.2, 2.442)

The iteration continue for the required number of iterations.

Content from the areas of study where pseudocode can be used

Mathematical Methods

  • piecewise defined functions
  • bisection (and using the mean of the endpoints as a point estimate)
  • numerical evaluation of limits for derivatives
  • Newton’s method for polynomials (Units 1 and 2) and other functions (Units 3 and 4)
  • Polynomial approximations to transcendental functions
  • Counting in a probability context
  • Simple simulations for probability
  • Optimisation of integer valued functions
  • Simulations for sampling distributions, central limit theorem
  • Numerical integration, left and right interval values, trapezium method point estimate

Specialist Mathematics

  • Investigation of number properties, sequences, partial sums and products
  • Numerical integration – Reimann sums for areas, volumes and surface areas of solids of revolution, length of segments of a curve
  • Vector operations including scalar product, cross product, projections
  • Numerical solution of differential equations including Euler’s method
  • Sums of random variables
  • Sample distributions for means

Sample Questions

1 The algorithm shown on the right will print the value

 

A 16

B 24

C 28

D 30

E 32

Answer: E


 

a ← 2

while  a < 20

a ← 2a

end while

print(a)


 

2 The algorithm shown on the right will print the value

 

A 15

B 17

C 19

D 21

E 23

Answer: E


 

sum ← 2

for from 1 to 3

for y from 1 to 2

sum = sum + x + y

end for

end for

print(sum)


 

3 For the algorithm shown opposite, the value of c when count = 3, is

 

A 2.125

B 2.15625

C 2.1875

D 2.25

E 2.5

Answer: C


 

define  f(x)

return (2ex – 17) a ← 2

b ← 3

c ← (a+b)/2

count = 0

while b - a > 0.002

count = count + 1

if f(af(c) < 0 then

b ← c

else

a ← c

end if

c ← (a+b)/2

end while


 

4 Three dice are rolled at the same time. The algorithm shown opposite generates the sample space for this experiment.
The print statement when count = 4 gives (4, x). The value of x is

 

A 4

B 5

C 6

D 7

E 8

Answer: C


 

count ← 0

for from 1 to 6

for from 1 to 6

for from 1 to 6

count ← count + 1

print(counti + j + k)

end for

end for

end for


 

5 a For the code opposite give the resulting printout.


 

for  from 1 to 4

print i3 + 2

end for


 

b For the code opposite give the resulting printout.


 

for from 1 to 5

if i2 < 10

print i2

else

printi2 + 2

end if

end for


 

6

The surface area, S, of a rectangular prism box with the top open and fixed volume V
is given by ${\large S = xy + \frac{2V}{x} + \frac{2V}{y}}$ where the side lengths take only integer values. Assume x and y are the side lengths of the base of the box.

For a given value of V, describe the algorithm using pseudocode to find the integer valued side lengths that maximise the surface area of the box.