# 3.1.9 Algorithms

## 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

WHILE num > 0
r <-- num MOD 2
num <-- num / 2
ENDWHILE

```nums = [6,2,8,1,9,2]