You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson introduces algorithms — what they are, how to represent them, and how to trace through them. This is fundamental to the OCR A-Level Computer Science (H446) specification, covering sections 1.4 and 2.3.
An algorithm is a finite sequence of well-defined instructions designed to perform a specific task or solve a particular problem. Every algorithm must have:
| Property | Description |
|---|---|
| Input | Zero or more inputs are provided. |
| Output | At least one output is produced. |
| Definiteness | Each step is precisely and unambiguously defined. |
| Finiteness | The algorithm must terminate after a finite number of steps. |
| Effectiveness | Each step must be basic enough to be carried out in practice. |
Algorithms can be represented in three main ways:
Pseudocode is a structured, human-readable description of an algorithm that resembles a programming language but is not tied to any specific language syntax.
The OCR exam uses specific pseudocode conventions. Key constructs include:
| Construct | OCR Pseudocode |
|---|---|
| Assignment | variable = value |
| Output | print(value) |
| Input | variable = input("prompt") |
| If statement | if condition then ... elseif ... else ... endif |
| For loop | for i = 0 to 9 ... next i |
| While loop | while condition ... endwhile |
| Do-until loop | do ... until condition |
| Function | function name(parameters) ... return value ... endfunction |
| Procedure | procedure name(parameters) ... endprocedure |
| Array declaration | array name[size] |
| Array access | name[index] |
| String length | name.length |
| Substring | name.substring(start, length) |
| MOD | a MOD b (remainder) |
| DIV | a DIV b (integer division) |
| AND, OR, NOT | Boolean operators |
function findMax(numbers, size)
max = numbers[0]
for i = 1 to size - 1
if numbers[i] > max then
max = numbers[i]
endif
next i
return max
endfunction
A flowchart is a visual representation of an algorithm using standard symbols connected by arrows.
| Symbol | Shape | Purpose |
|---|---|---|
| Terminator | Rounded rectangle (oval) | Start or end of the algorithm |
| Process | Rectangle | An instruction or action |
| Decision | Diamond | A yes/no question (branching) |
| Input/Output | Parallelogram | Reading input or displaying output |
| Flow lines | Arrows | Direction of flow between steps |
START
-> Input: number
-> Decision: Is number > 0?
Yes -> Output: "Positive"
No -> Decision: Is number < 0?
Yes -> Output: "Negative"
No -> Output: "Zero"
END
Exam Tip: You must be able to both read flowcharts and create them from a problem description. Ensure all paths lead to a terminator, and decision boxes have exactly two outputs (Yes/No or True/False).
A trace table is a technique for dry-running (manually stepping through) an algorithm. Each row represents one step of execution, and each column tracks a variable's value.
Algorithm:
x = 3
y = 5
while x < y
x = x + 1
y = y - 1
endwhile
print(x)
print(y)
Trace Table:
| Step | x | y | x < y | Action |
|---|---|---|---|---|
| 1 | 3 | 5 | - | x = 3 |
| 2 | 3 | 5 | - | y = 5 |
| 3 | 3 | 5 | true | Enter loop |
| 4 | 4 | 5 | - | x = x + 1 |
| 5 | 4 | 4 | - | y = y - 1 |
| 6 | 4 | 4 | false | Exit loop |
| 7 | - | - | - | print(4), print(4) |
Output: 4, 4
array data[5] = [7, 2, 9, 4, 6]
max = data[0]
for i = 1 to 4
if data[i] > max then
max = data[i]
endif
next i
print(max)
| Step | i | data[i] | max | data[i] > max | Action |
|---|---|---|---|---|---|
| Init | - | - | 7 | - | max = data[0] = 7 |
| 1 | 1 | 2 | 7 | false | No change |
| 2 | 2 | 9 | 9 | true | max = 9 |
| 3 | 3 | 4 | 9 | false | No change |
| 4 | 4 | 6 | 9 | false | No change |
Output: 9
Exam Tip: Trace table questions are worth several marks. Be meticulous — show every variable change, not just the final values. If you make an error early, subsequent rows will be wrong, so take your time.
Dry-running (also called desk-checking) is the process of manually stepping through an algorithm without executing it on a computer. It involves:
count = 0
for i = 0 to n - 1
if condition then
count = count + 1
endif
next i
total = 0
for i = 0 to n - 1
total = total + data[i]
next i
average = total / n
max = data[0]
for i = 1 to n - 1
if data[i] > max then
max = data[i]
endif
next i
function linearSearch(data, target, size)
for i = 0 to size - 1
if data[i] == target then
return i
endif
next i
return -1
endfunction
| Concept | Description |
|---|---|
| Correctness | The algorithm produces the right output for all valid inputs. |
| Efficiency | The algorithm uses minimal resources (time and memory). |
| Termination | The algorithm always finishes (does not loop forever). |
Algorithms can be correct but inefficient, or efficient but incorrect. A good algorithm is both correct and efficient.
Exam Tip: Practise writing pseudocode using OCR conventions and creating trace tables. These skills are tested in almost every H446 paper. When writing pseudocode, be precise with your syntax — marks can be lost for ambiguous or incomplete instructions.