3.1.9 Algorithms

Table of Contents

Fork me on GitHub

1 What is an Algorithm?

Learn It

  • Algorithms are computational solutions that always finish and return an answer.
  • For example, if we had a bag filled with scrabble tiles, and we wanted to find out how many letters of each type there were: 
Set count for each letter to 0
Until the bag is empty
    Take out a tile
    Look at the letter
    Add one to that letter's count

2 Interpreting pseudocode algorithms

Learn It

  • We can use pseudocode to write algorithms.
  • Pseudocode is useful as it can be read by any programmer, regardless of their language specialism.
  • In reality there is no formal syntax for pseudocode and computer scientists will use whatever notation they feel is best understood by the reader. Exam boards however don't seem to understand this concept, and insist on a formal syntax.
  • You can find AQA's pseudocode syntax here

Try It

  • For each of the pseudocode algorithms shown below, in a few sentences, explain their function. 
foo <-- 100
WHILE foo > 0
   IF foo % 2 = 0 THEN
      OUTPUT foo
      foo = foo - 1
   END IF
ENDWHILE

bar <-- 1
baz <-- 0

WHILE bar < 100
   bar <-- bar + baz
   baz <-- bar - baz
   OUTPUT bar
ENDWHILE

3 Writing pseudocode algorithms

Try It

  • You also need to be able to write simple algorithms using pseudocode. Try the following algorithms taken from Project Euler
    1. If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
    2. Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

4 Testing pseudocode algorithms

Learn It

  • Often, when we write an algorithm, we'll want to test that it works correctly.
  • We can use trace tables to achieve this. 
X <-- 1
Y <-- 2
WHILE X < 20
    OUTPUT X
    X <-- X + Y
    Y <-- Y + 1
ENDWHILE
  • The variable in the above pseudocode algorithm can traced using a trace table.
OUTPUT X Y
  1 2
1 3 3
3 6 4
6 10 5
10 15 6
15 21 7
  • The trace table allows us to understand what is happening to the values of variables within the algorithm.

Try It

  • Try drawing trace tables for the following algorithms. 
Y <-- 3
FOR X <-- 1 TO 5
   Y <-- Y + X
ENDFOR

OUTPUT Y

List <-- [10,8,3,5,6,1,2]
Total <-- 0

FOR i <-- 1 TO LEN(List)
   TOTAL <-- TOTAL + List[i]
ENDFOR

OUTPUT TOTAL

num <-- 78
answer <-- ''

WHILE num > 0
   r <-- num MOD 2
   num <-- num / 2
   answer <-- STR(r) + answer 
ENDWHILE

OUTPUT answer

nums = [6,2,8,1,9,2]
n = 0

FOR i <-- 1 TO LEN(nums)
   IF nums[i] > n THEN
      n = nums[i]
   ENDIF
ENDFOR

OUTPUT n