Algorithm Basics

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.

---

What is an Algorithm?

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.

Examples of Algorithms

• A recipe for baking a cake (inputs: ingredients; output: cake).
• Searching for a name in a phone book.
• Sorting a list of numbers into ascending order.
• Finding the shortest route between two cities.

---

Representing Algorithms

Algorithms can be represented in three main ways:

1. Pseudocode

Pseudocode is a structured, human-readable description of an algorithm that resembles a programming language but is not tied to any specific language syntax.

OCR Pseudocode Conventions

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

Example Pseudocode

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

---

2. Flowcharts

A flowchart is a visual representation of an algorithm using standard symbols connected by arrows.

Standard Flowchart Symbols

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

Example Flowchart Logic (described textually)

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).

---

3. Trace Tables

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.

Purpose

• To verify that an algorithm produces the correct output.
• To find errors (bugs) in an algorithm.
• To understand how an algorithm works.

How to Create a Trace Table

1. Create a column for each variable (including any outputs).
2. Create a column for any conditions evaluated.
3. Step through the algorithm line by line, recording variable values after each step.

Worked Example

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

Worked Example: Finding the Largest Value

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

Dry-running (also called desk-checking) is the process of manually stepping through an algorithm without executing it on a computer. It involves:

1. Reading the algorithm line by line.
2. Keeping track of all variable values (using a trace table).
3. Following all branches (if/else) and loop iterations.
4. Recording the output.

Why Dry-Run?

• To check correctness before coding.
• To understand someone else's algorithm.
• To find logical errors.
• It is frequently tested in the OCR exam.

---

Common Algorithm Patterns

1. Counting

count = 0
for i = 0 to n - 1
    if condition then
        count = count + 1
    endif
next i

2. Accumulation (Summing)

total = 0
for i = 0 to n - 1
    total = total + data[i]
next i
average = total / n

3. Finding Maximum/Minimum

max = data[0]
for i = 1 to n - 1
    if data[i] > max then
        max = data[i]
    endif
next i

4. Linear Search

function linearSearch(data, target, size)
    for i = 0 to size - 1
        if data[i] == target then
            return i
        endif
    next i
    return -1
endfunction

---

Efficiency and Correctness

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.

---

Summary

• An algorithm is a finite sequence of well-defined instructions to solve a problem.
• Algorithms can be represented as pseudocode, flowcharts, or structured English.
• Trace tables are used to dry-run algorithms and verify correctness.
• OCR pseudocode has specific conventions (for loops, while loops, functions, arrays).
• Common patterns: counting, accumulation, finding max/min, linear search.

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.