Topic 1: Computational Thinking

Computational Thinking

Key Definition

Computational Thinking is a set of problem-solving methods that involve expressing problems and their solutions in ways that a computer could execute. It allows us to take complex problems and break them down into a series of smaller, more manageable problems.

Simple Way to Think About It

Computational thinking is like being a detective! When a detective solves a crime, they don't try to figure everything out at once. They:

Break the mystery into smaller clues (decomposition)
Focus only on important evidence, not every tiny detail (abstraction)
Look for patterns - "This looks like other cases I've solved!" (pattern recognition)
Create a step-by-step plan to catch the criminal (algorithmic thinking)

There are four key principles of computational thinking that you must understand:

1. Decomposition

Breaking down a complex problem into smaller, more manageable sub-problems.

Benefits:

Easier to understand and solve
Different people can work on different parts
Each part can be tested separately
Parts can be reused in other programs

Example: Creating a game could be decomposed into: graphics, sound, player controls, scoring system, and levels.

Everyday Analogy: Think about cleaning your bedroom. Instead of panicking about the mess, you break it into smaller tasks: make the bed, pick up clothes, tidy the desk, vacuum the floor. Each task is easier to handle on its own!

2. Abstraction

Removing unnecessary details to focus only on the important information needed to solve the problem.

Key idea: Identify what is relevant and ignore what isn't.

Example: The London Tube map is an abstraction - it doesn't show the exact geographical routes or distances between stations, just the connections needed to navigate.

Everyday Analogy: If someone says "I saw a cat on the street", you immediately picture a cat and a street in your mind. You don't need to know the exact colour of the cat, how many whiskers it has, or the postcode of the street. Your brain automatically focuses on the important details!

3. Pattern Recognition

Looking for similarities among and within problems that can help solve them more efficiently.

Benefits:

Solutions can be reused
Problems become easier to solve
Code can be more efficient

Example: Recognising that calculating VAT always uses the same formula, regardless of the product.

4. Algorithmic Thinking

Developing a step-by-step solution to a problem, or rules to follow to solve the problem.

Requirements:

Clear, unambiguous instructions (no confusion!)
Defined start and end points
Correct sequence of steps

Example: A recipe is an algorithm - it has clear steps that must be followed in order.

Why computers need EXACT instructions: If you tell a human "wait for the water to boil", they know to keep checking until it boils. But a computer would just wait... forever! You'd need to say "keep checking if the temperature equals 100°C, and only stop when it does."

The Three Programming Constructs

All algorithms are built from just three basic building blocks called constructs:

Sequence

Instructions that are carried out one after another, in order.

Like following a recipe: You do step 1, then step 2, then step 3 - in that exact order. You can't ice a cake before you've baked it!

Selection

Making a decision - choosing which path to take based on a condition (IF...THEN...ELSE).

Like checking the weather: IF it's raining THEN take an umbrella ELSE wear sunglasses. You make a choice!

Iteration (Loops)

Repeating instructions until a condition is met. Also called a "loop".

Like eating dinner: You keep eating UNTIL your plate is empty or you're full. You repeat the "take a bite" action over and over!

Did You Know?

We use iteration in our daily lives all the time! When traffic lights are red, you keep waiting UNTIL they turn green. When learning lines for a play, you repeat them over and over UNTIL you know them all. Every video game loop checks "has the player won?" repeatedly until you finish the level!

Craig 'n' Dave: Decomposition

Breaking down complex problems into smaller parts

Craig 'n' Dave: Abstraction

Removing unnecessary details to focus on what's important

Craig 'n' Dave: Using Abstraction and Decomposition

Applying abstraction and decomposition to solve problems

Sample Question - 3 marks 3 marks

Explain how decomposition and abstraction could be used when designing a school management system.

Show Mark Scheme Answer

Decomposition (1-2 marks):

Break the system into smaller parts such as: student records, attendance tracking, timetabling, report generation
Each module can be developed and tested separately

Abstraction (1-2 marks):

Focus only on relevant student details (name, ID, classes) not irrelevant details (favourite colour)
Remove unnecessary complexity to make the system manageable

Content based on: BBC Bitesize, Save My Exams

Algorithms & Representations

Key Definition

An algorithm is a sequence of steps that can be followed to complete a task. Every algorithm must have a clear starting point, a clear ending point, and produce the same result each time when given the same input.

Real-World Example: GPS Navigation

When you use Google Maps or a sat-nav to get from home to school, it uses an algorithm! The algorithm:

Takes your input: Where you are (home) and where you want to go (school)
Processes the data: Looks at all possible roads, distances, traffic
Produces output: The fastest route with turn-by-turn directions

Every time you put in the same start and end point with the same traffic conditions, it gives you the same route. That's what makes it an algorithm!

What Makes a Successful Algorithm?

A good algorithm isn't just any set of instructions - it must have these three essential qualities:

1. Accuracy

The algorithm must produce the correct result every single time.

Example: If your calculator said 2 + 2 = 5, it would be useless! The algorithm for addition must always give the right answer.

2. Consistency

Given the same input, the algorithm must produce the same output every time.

Example: When you scan the same barcode twice at a shop, it should show the same product and price both times!

3. Efficiency

The algorithm should solve the problem without wasting time or resources.

Example: If Google took 10 minutes to search for something, nobody would use it! Good search algorithms work in milliseconds.

Simple Way to Remember

Think of a vending machine algorithm:

Accurate: Press A3 and you get the crisps from slot A3, not chocolate from B2
Consistent: Press A3 ten times (with money each time) and you get crisps all ten times
Efficient: It dispenses the crisps in seconds, not hours!

Representing Algorithms

Algorithms can be represented in three main ways:

Pseudocode

A structured way of writing algorithms using plain English-like statements. Not a real programming language but follows programming conventions.

SET total TO 0
FOR each number IN list
    ADD number TO total
END FOR
OUTPUT total

Flowcharts

Visual diagrams showing the flow of a program using standard symbols.

Advantages: Easy to follow visually, good for showing decision points and loops.

Understanding Pseudocode - A Beginner's Guide

Pseudocode is like writing instructions in simple English that look a bit like computer code. It's not a real programming language - it's a way to plan your algorithm before writing actual code!

Why Use Pseudocode?

Focus on Logic

Don't worry about programming syntax - just think about the steps!

Anyone Can Read It

No need to know a programming language to understand it!

Easy to Convert

Can be turned into Python, Java, or any other language!

Common Pseudocode Keywords

These are the words you'll use most often in pseudocode:

Keyword	What It Does	Example
`SET / ASSIGN`	Give a variable a value	`SET score TO 0`
`INPUT / READ`	Get data from the user	`INPUT userName`
`OUTPUT / PRINT`	Display something on screen	`OUTPUT "Hello!"`
`IF...THEN...ELSE`	Make a decision	`IF age >= 18 THEN...`
`FOR...END FOR`	Repeat a set number of times	`FOR i = 1 TO 10`
`WHILE...END WHILE`	Repeat while condition is true	`WHILE count < 10`

Complete Pseudocode Example

Here's a complete example - a simple program to check if someone can vote:

Pseudocode

START
    OUTPUT "What is your age?"
    INPUT age

    IF age >= 18 THEN
        OUTPUT "You can vote!"
    ELSE
        OUTPUT "Sorry, you're too young"
    END IF
END

Same Thing in Python

# Python version
age = int(input("What is your age? "))

if age >= 18:
    print("You can vote!")
else:
    print("Sorry, you're too young")

Important: There's no "wrong" way to write pseudocode as long as it's clear and logical. Different exam boards use slightly different styles, but the meaning should always be obvious!

Flowchart Symbols

You must know these standard flowchart symbols:

Shape	Name	Purpose	Example
	Terminator	Start or End of algorithm	"Start", "Stop", "End"
	Process	An instruction or calculation	"total = total + 1"
	Decision	Yes/No question (selection)	"Is x > 10?"
	Input/Output	Data input or output	"INPUT name", "OUTPUT result"
→	Flow Line	Shows direction of flow	Connects symbols

Flowchart Examples

Here are two complete flowchart examples to help you understand how the symbols connect together:

Selection (IF Statement)

Check if someone can vote (age 18+)

Pseudocode equivalent:

INPUT age
IF age >= 18 THEN
    OUTPUT "You can vote"
ELSE
    OUTPUT "Too young"
END IF

Iteration (WHILE Loop)

Count and display numbers 1 to 5

Output: 1, 2, 3, 4, 5

Pseudocode equivalent:

count = 1
WHILE count <= 5 DO
    OUTPUT count
    count = count + 1
END WHILE

Spot the Difference!

Selection (IF): The flowchart splits into two paths that BOTH lead to the end. The decision is made ONCE.

Iteration (WHILE): The flowchart has an arrow that loops BACK to the decision. It keeps repeating until the condition is false.

Exam Tip

In exams, you might be asked to:

Complete missing parts of flowcharts or pseudocode
Identify whether a flowchart shows selection or iteration
Convert between flowcharts and pseudocode
Trace through a flowchart with given input values

Arithmetic Operators

When writing algorithms, you'll need to perform calculations. Here are the arithmetic operators you must know:

Think of Operators Like a Calculator

Each operator tells the computer what mathematical operation to perform - just like pressing buttons on a calculator!

Operator	Name	What It Does	Example	Result
+	Addition	Adds two numbers together	`5 + 3`	8
-	Subtraction	Takes one number away from another	`10 - 4`	6
*	Multiplication	Multiplies two numbers	`4 * 3`	12
/	Division	Divides one number by another (includes decimals)	`7 / 2`	3.5
DIV	Integer Division	Divides and gives whole number only (no decimals)	`7 DIV 2`	3
MOD	Modulus (Remainder)	Gives the remainder after division	`7 MOD 2`	1
^	Exponent (Power)	Raises a number to a power	`2 ^ 3`	8 (2x2x2)

DIV and MOD Explained Simply

These two operators confuse many students, but they're actually simple once you understand them!

DIV - Integer Division

Analogy: Imagine sharing 7 sweets between 2 people equally.

Each person gets 3 sweets (the whole number part).

7 DIV 2 = 3

DIV ignores the remainder and only gives you the whole number!

MOD - Remainder

Analogy: After sharing 7 sweets between 2 people...

There's 1 sweet left over (the remainder).

7 MOD 2 = 1

MOD tells you what's left over after dividing as many times as you can!

Common Uses of MOD

Check if a number is even or odd: If number MOD 2 = 0, it's even!
Get the last digit: 1234 MOD 10 = 4 (the last digit)
Wrap around values: Clock times, game levels that repeat

Variables and Constants

When writing algorithms, you need places to store data. That's where variables and constants come in!

Think of Variables Like Labelled Boxes

📦

Variable

A box that can hold different things

The contents can change while the program runs

Example: A box labelled "score" - it might start at 0, then change to 10, then 25...

🔒

Constant

A locked box that never changes

The value is set once and stays the same forever

Example: A box labelled "PI" always contains 3.14159 - it never changes!

Variable Examples

Things that change during the program:

score - goes up when you get points
lives - goes down when you lose
userName - changes for each user
total - updates as you add items
temperature - changes with each reading

SET score TO 0
score = score + 10
OUTPUT score  // Shows 10

Constant Examples

Things that stay the same:

PI = 3.14159 (mathematical value)
VAT_RATE = 0.20 (20% tax rate)
MAX_PLAYERS = 4 (game limit)
DAYS_IN_WEEK = 7
SCHOOL_NAME = "Springfield High"

CONST VAT_RATE = 0.20
tax = price * VAT_RATE
// VAT_RATE never changes!

When Should I Use Constants?

Use a constant when:

The value has a special meaning (like PI or VAT rate)
The value should never accidentally change
You want to change the value easily in one place (like changing VAT from 20% to 25%)

Naming Conventions

When you create variables and constants, you need to give them names. There are rules and conventions to follow!

Rules for Naming (You MUST follow these)

Good Names

score
playerName
total_cost
age1

Bad Names

1score (can't start with number)
player name (no spaces!)
total-cost (no hyphens)
if (reserved keyword)

The Rules:

Must start with a letter (not a number)
Can contain letters, numbers, and underscores
No spaces or special characters (!@#$%-)
Can't use reserved words (like IF, WHILE, FOR)
Case sensitive: Score and score are different!

Common Naming Styles

There are two popular ways to write multi-word variable names:

camelCase

First word lowercase, then capitalize the first letter of each new word.

Called "camelCase" because the capitals look like camel humps!

Examples:

firstName
totalScore
numberOfPlayers
isGameOver

snake_case

All lowercase letters with underscores between words.

Called "snake_case" because it's long and low like a snake!

Examples:

first_name
total_score
number_of_players
is_game_over

Important for Constants

Constants are usually written in UPPERCASE with underscores (called SCREAMING_SNAKE_CASE) to make them stand out:

MAX_SCORE = 100
PI = 3.14159
VAT_RATE = 0.20

Exam Tip

In the exam, you may be asked to:

Identify errors in algorithms and correct them
Complete missing parts of flowcharts or pseudocode
Trace through algorithms with given inputs (trace tables)
Write your own algorithms for simple problems
Identify whether something should be a variable or constant
Fix incorrect variable names

Try It Yourself: Operators, Variables & Constants

Practice using operators, variables and constants in Python. Experiment with the code and see what happens!

Python Editor - Operators & Variables

# Variables and Constants Practice
# Try changing the values and see what happens!

# CONSTANTS (values that don't change)
PI = 3.14159
VAT_RATE = 0.20  # 20% VAT
MAX_LIVES = 3

# VARIABLES (values that can change)
player_name = "Alex"
score = 0
lives = MAX_LIVES

print("=== GAME START ===")
print(f"Welcome, {player_name}!")
print(f"You have {lives} lives")
print(f"Starting score: {score}")

# Let's play! Score some points
score = score + 100
print(f"\nYou scored 100 points! Score is now: {score}")

score = score + 50
print(f"You scored 50 more! Score is now: {score}")

# Oops, lost a life
lives = lives - 1
print(f"\nOh no! You lost a life. Lives remaining: {lives}")

# Calculate bonus using operators
bonus = score * 2
print(f"\nDouble score bonus: {bonus}")

# DIV and MOD examples
total_sweets = 17
num_friends = 5
sweets_each = total_sweets // num_friends  # DIV (integer division)
sweets_left = total_sweets % num_friends   # MOD (remainder)

print(f"\n=== SHARING SWEETS ===")
print(f"Total sweets: {total_sweets}")
print(f"Number of friends: {num_friends}")
print(f"Each friend gets: {sweets_each} sweets (DIV)")
print(f"Sweets left over: {sweets_left} (MOD)")

# Check if a number is even or odd
number = 17
if number % 2 == 0:
    print(f"\n{number} is EVEN")
else:
    print(f"\n{number} is ODD")

Click "Run Code" to see the output...

Challenges - Try These!

Modify the code above to complete these challenges:

Challenge 1: Change player_name to your own name
Challenge 2: Add another line to score 200 more points
Challenge 3: Change total_sweets to 23 - how many are left over?
Challenge 4: Change the number variable to 42 - is it even or odd?
Challenge 5: Calculate how many complete weeks are in 50 days (hint: use DIV with 7)

Variables and Constants

Variable

A named storage location in a program that holds a value which can change during execution.

                        score = 0
score = score + 10  # Now score is 10
                    

Constant

A named storage location that holds a value which cannot change once it's set.

                        PI = 3.14159
VAT_RATE = 0.20  # Always 20%
                    

Think of Variables as Labelled Boxes

Imagine you have boxes in your room with labels on them:

A box labelled "socks" contains 5 pairs. You can add more socks or take some out - the number changes (it's a variable)
A box labelled "birthday" contains "15th March". This date will never change - it's a constant!

Why use constants? They prevent accidental changes to important values and make code easier to understand. If VAT changes, you only update it in one place!

Arithmetic Operators

When writing algorithms, you need to know these arithmetic operators for calculations:

Operator	Name	Example	Result
+	Addition	`7 + 3`	10
-	Subtraction	`7 - 3`	4
*	Multiplication	`7 * 3`	21
/	Division	`7 / 3`	2.333...
DIV or //	Integer Division	`7 DIV 3`	2 (whole number only)
MOD or %	Modulus (Remainder)	`7 MOD 3`	1 (the remainder)
^	Exponentiation (Power)	`2 ^ 3`	8 (2×2×2)

DIV and MOD - The Tricky Ones Explained!

These two confuse a lot of students. Think of sharing sweets:

You have 17 sweets to share equally among 5 friends.

17 DIV 5 = 3 → Each friend gets 3 sweets (whole sweets only!)
17 MOD 5 = 2 → You have 2 sweets left over (the remainder)

Exam favourite: "Is a number even or odd?" → Use number MOD 2. If result is 0, it's even. If result is 1, it's odd!

Naming Conventions

When naming variables, constants, and functions, programmers follow naming conventions to make code readable:

camelCase

First word lowercase, each new word starts with a capital letter. No spaces!

                        playerScore
numberOfLives
calculateTotalPrice
                    

Used in: JavaScript, Java

snake_case

All lowercase, words separated by underscores.

                        player_score
number_of_lives
calculate_total_price
                    

Used in: Python, databases

Why Can't I Just Use Spaces?

Computer languages can't have spaces in variable names because spaces separate different parts of code. If you wrote player score = 10, the computer would think "player" and "score" are two different things!

Rules for Naming Variables

Must start with a letter (not a number) - score1 ✓ but 1score ✗
Cannot contain spaces - use camelCase or snake_case instead
Cannot use reserved words (like if, for, print)
Should be meaningful - age is better than x
Constants are often written in CAPITALS: MAX_SCORE = 100

Craig 'n' Dave: How to Produce Algorithms

Covers pseudocode conventions and flowchart creation

Craig 'n' Dave: Algorithmic Thinking

Developing step-by-step solutions to problems

Craig 'n' Dave: Pseudocode and Flow Diagrams

How to produce algorithms using pseudocode and flowcharts

Searching Algorithms

You need to understand two searching algorithms for the exam: Linear Search and Binary Search.

Simple Way to Remember

Linear Search = Looking through a messy drawer one item at a time until you find your keys.

Binary Search = Playing "higher or lower" to guess a number - you eliminate half the options each time!

Linear Search

Definition

Linear search starts at the first item in a list and checks each item one at a time until the target is found or the end of the list is reached. This is also called a sequential search because it goes through items in sequence (one after another).

Real-Life Example

Imagine looking for your friend's name in a paper phone book that isn't alphabetical. You'd have to start at page 1 and check every single name until you find it. If there are 1000 names and your friend is last, you'd check all 1000!

Linear Search Algorithm (Step by Step):

Start at the first item in the list
Compare the item with what you're searching for
If they're the same, stop - you found it!
If not, move to the next item
Repeat steps 2-4 until you find it or reach the end

Advantages

Works on unsorted data
Simple to understand and implement
No preprocessing required
Good for small datasets

Disadvantages

Slow for large datasets
Must check every item in worst case
Time complexity: O(n)

# Linear Search in Python
def linear_search(data_list, target):
    for i in range(len(data_list)):
        if data_list[i] == target:
            return i  # Return position if found
    return -1  # Return -1 if not found

# Example: Search for 7 in [4, 2, 7, 1, 9]
# Checks: 4? No → 2? No → 7? Yes! Found at index 2

Binary Search

Definition

Binary search works by repeatedly dividing a sorted list in half. It compares the middle item with the target and eliminates half the remaining items each time. This is called a "divide and conquer" method.

The Guessing Game - You Already Know Binary Search!

Have you ever played "guess the number between 1 and 100"? You probably:

First guess 50 (the middle)
If told "too high", you guess 25 (middle of 1-50)
If told "too low", you guess 37 (middle of 25-50)
Keep halving until you find it!

That's exactly how binary search works! You can find ANY number from 1-100 in just 7 guesses maximum.

Important Prerequisite

Binary search only works on sorted data. If the data is not sorted, you must sort it first (which takes time) or use linear search instead.

Think about it: The guessing game only works because numbers are in order (1, 2, 3...). If they were jumbled up randomly, "higher" and "lower" would be meaningless!

Binary Search Steps:

Find the middle item of the list
Compare the middle item with the target
If they match, return the position
If target is less than middle, search the left half
If target is greater than middle, search the right half
Repeat until found or no items left

Advantages

Very fast for large datasets
Eliminates half the data each step
Time complexity: O(log n)
1000 items = max 10 comparisons!

Disadvantages

Data must be sorted
More complex to implement
Sorting takes time if not already sorted

# Binary Search in Python
def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2

        if sorted_list[mid] == target:
            return mid  # Found it!
        elif sorted_list[mid] < target:
            low = mid + 1  # Search right half
        else:
            high = mid - 1  # Search left half

    return -1  # Not found

# Example: Search for 7 in [1, 2, 4, 7, 9]
# Mid=4 → 7>4 → Search right → Mid=7 → Found!

Comparison Table

Feature	Linear Search	Binary Search
Data requirement	Any order	Must be sorted
Time complexity	O(n) - slow	O(log n) - fast
Max checks (1000 items)	1000	10
Best for	Small/unsorted lists	Large sorted lists

Which Search Should I Use?

Use Linear Search when:

Your data is NOT sorted (and you only need to search once)
You have a small list
You need simple code that's easy to understand

Use Binary Search when:

Your data IS sorted (or you'll sort it and search many times)
You have a large list - the speed difference is HUGE!
Think about it: In a phone book with 1 million names, linear search might check all 1 million. Binary search finds anyone in just 20 checks!

Try It Yourself: Searching Algorithms

Practice implementing Linear Search and Binary Search. Modify the code and run it to see the results!

Python Editor - Searching Algorithms

# Searching Algorithms Practice
# Try modifying the list and target values!

def linear_search(data_list, target):
    """Search through each item one at a time"""
    for i in range(len(data_list)):
        print(f"Checking index {i}: {data_list[i]}")
        if data_list[i] == target:
            return i  # Found it!
    return -1  # Not found

def binary_search(sorted_list, target):
    """Search by dividing the list in half each time"""
    low = 0
    high = len(sorted_list) - 1
    step = 1

while low <= high:
        mid = (low + high) // 2
        print(f"Step {step}: Checking middle index {mid}, value = {sorted_list[mid]}")
        step += 1

if sorted_list[mid] == target:
            return mid  # Found it!
        elif sorted_list[mid] < target:
            low = mid + 1  # Search right half
            print("  -> Target is larger, search right half")
        else:
            high = mid - 1  # Search left half
            print("  -> Target is smaller, search left half")

return -1  # Not found

# Test data
numbers = [3, 7, 12, 18, 24, 31, 45, 52, 68]
target = 31

print("=== LINEAR SEARCH ===")
print(f"Searching for {target} in {numbers}")
result = linear_search(numbers, target)
if result != -1:
    print(f"Found at index {result}!")
else:
    print("Not found")

print("\n=== BINARY SEARCH ===")
print(f"Searching for {target} in {numbers}")
result = binary_search(numbers, target)
if result != -1:
    print(f"Found at index {result}!")
else:
    print("Not found")

Click "Run Code" to see the output...

Challenge

Try these modifications:

Search for a value that doesn't exist (e.g., 50)
Count how many comparisons each algorithm makes
What happens if you use binary search on an unsorted list?

Craig 'n' Dave: Linear Search

Detailed walkthrough with trace tables

June 2022 - Paper 1 4 marks

A sorted list contains these values: [3, 7, 12, 18, 24, 31, 45]

Show the steps a binary search would take to find the value 18.

Show Mark Scheme Answer

Step 1: Middle = 18, Target = 18 ✓ Found!

OR if showing working:

Step 1: low=0, high=6, mid=(0+6)//2=3

list[3] = 18, which equals target

Result: Found at index 3

(1 mark for correct method, 1 mark for each correct step, 1 mark for correct answer)

Content based on: BBC Bitesize, Save My Exams

Sorting Algorithms

You need to understand two sorting algorithms: Bubble Sort and Merge Sort.

Simple Way to Remember

Bubble Sort = Comparing neighbours and swapping if needed (like sorting people by height - swap if the taller person is in front)

Merge Sort = Split everything into tiny piles, then carefully combine them back in order (like sorting a deck of cards)

Bubble Sort

Definition

Bubble sort compares adjacent (next to each other) pairs of items and swaps them if they are in the wrong order. The largest values "bubble" to the end of the list with each pass.

Why is it Called "Bubble" Sort?

Watch the largest numbers carefully - they gradually move to the end of the list, like bubbles rising to the surface of water! After the first pass, the biggest number is in its correct place at the end. After the second pass, the second biggest is in place. And so on!

Bubble Sort Steps:

Start at the beginning of the list
Compare the first two items
If they are in the wrong order, swap them
Move to the next pair and repeat
Continue until you reach the end (one pass)
Repeat passes until no swaps are made

Real-Life Example: Sorting by Height

Imagine lining up students by height for a photo. You walk along the line comparing each pair of neighbours. If someone tall is in front of someone short, they swap places. You keep walking through the line until nobody needs to swap - then everyone is in height order!

Worked Example

Sort [5, 3, 8, 1] using bubble sort:

Pass 1: [5,3,8,1] → [3,5,8,1] → [3,5,8,1] → [3,5,1,8]

Pass 2: [3,5,1,8] → [3,5,1,8] → [3,1,5,8]

Pass 3: [3,1,5,8] → [1,3,5,8]

Pass 4: [1,3,5,8] → No swaps needed. Done!

# Bubble Sort in Python
def bubble_sort(data_list):
    n = len(data_list)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if data_list[j] > data_list[j + 1]:
                # Swap the items
                data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j]
                swapped = True
        if not swapped:
            break  # List is sorted, exit early
    return data_list

Try It Yourself: Bubble Sort

Watch how Bubble Sort swaps adjacent elements. The code shows each pass and swap!

Python Editor - Bubble Sort

# Bubble Sort with Step-by-Step Output
# Watch how the largest values "bubble" to the end!

def bubble_sort_visual(data_list):
    data = data_list.copy()  # Don't modify original
    n = len(data)
    total_swaps = 0

print(f"Starting list: {data}")
    print("-" * 40)

for i in range(n - 1):
        print(f"\nPass {i + 1}:")
        swapped = False

for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                # Show the swap
                print(f"  Comparing {data[j]} and {data[j+1]} -> SWAP!")
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True
                total_swaps += 1
            else:
                print(f"  Comparing {data[j]} and {data[j+1]} -> OK")

print(f"  After pass: {data}")

if not swapped:
            print("\n  No swaps needed - list is sorted!")
            break

print("-" * 40)
    print(f"Final sorted list: {data}")
    print(f"Total swaps: {total_swaps}")
    return data

# Try with different lists!
numbers = [12, 8, 15, 3, 9]
print("=== BUBBLE SORT ===")
sorted_nums = bubble_sort_visual(numbers)

Click "Run Code" to see the output...

Challenge

Experiment with different lists:

Try a list that's already sorted - how many swaps?
Try a list in reverse order - what's the maximum swaps?
Try [5, 3, 8, 1] from the example above

Merge Sort

Definition

Merge sort uses a "divide and conquer" approach. It repeatedly divides the list in half until each sublist has one item, then merges them back together in sorted order. This uses recursion - the same process applied over and over to smaller and smaller pieces.

Think of Sorting Playing Cards

Imagine you have a messy pile of cards to sort:

Split the pile in half, then split those halves, until you have individual cards
A single card is already "sorted" (it's just one card!)
Now merge pairs of cards, putting them in order as you combine
Keep merging the small sorted piles into bigger sorted piles
Eventually you have one fully sorted deck!

Merge Sort Steps:

Divide: Split the list in half repeatedly until each list has 1 item
Conquer: Merge pairs of lists together in sorted order
Continue merging until you have one sorted list

Worked Example

Sort [6, 3, 8, 2] using merge sort:

Divide: [6,3,8,2] → [6,3] [8,2] → [6] [3] [8] [2]

Merge: [6] [3] → [3,6] and [8] [2] → [2,8]

Merge: [3,6] [2,8] → [2,3,6,8] ✓

Try It Yourself: Merge Sort

Watch how Merge Sort divides and conquers. See the divide and merge phases!

Python Editor - Merge Sort

# Merge Sort with Visual Output
# Watch the divide and conquer in action!

def merge_sort_visual(data, depth=0):
    indent = "  " * depth

if len(data) <= 1:
        print(f"{indent}Base case: {data}")
        return data

# Divide
    mid = len(data) // 2
    left = data[:mid]
    right = data[mid:]
    print(f"{indent}Splitting {data} into {left} and {right}")

# Conquer (recursively sort each half)
    left_sorted = merge_sort_visual(left, depth + 1)
    right_sorted = merge_sort_visual(right, depth + 1)

# Merge
    result = merge(left_sorted, right_sorted)
    print(f"{indent}Merging {left_sorted} and {right_sorted} = {result}")
    return result

def merge(left, right):
    """Merge two sorted lists into one sorted list"""
    result = []
    i = j = 0

while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

# Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test with the example from above
numbers = [6, 3, 8, 2]
print("=== MERGE SORT ===")
print(f"Original list: {numbers}")
print("-" * 40)
sorted_nums = merge_sort_visual(numbers)
print("-" * 40)
print(f"Final result: {sorted_nums}")

Click "Run Code" to see the output...

Challenge

Try these experiments:

Try sorting [5, 2, 8, 1, 9, 3] - how many levels of splitting?
Compare the number of operations to bubble sort
Try a list of 8 items - notice the pattern of splits

Comparison Table

Feature	Bubble Sort	Merge Sort
Time complexity	O(n²) - slow	O(n log n) - fast
Space needed	In-place (minimal)	Needs extra memory
Complexity	Simple to code	More complex
Best for	Small lists, nearly sorted	Large datasets
Algorithm design	Brute force - tries everything	Divide and conquer

So Which Should I Use?

For small lists (less than ~1000 items): Both take about the same time. Bubble sort is easier to write, so use that!

For large lists: Merge sort is MUCH faster. Sorting 500,000 items with bubble sort could take minutes, but merge sort does it in seconds!

Exam Tip

In the exam, you don't need to show every single swap in bubble sort. You can show the state of the list after each complete pass. If each pass is correct, you'll get full marks!

Craig 'n' Dave: Bubble Sort & Merge Sort

Complete walkthrough of sorting algorithms with trace tables

June 2023 - Paper 1 4 marks

The following list needs to be sorted into ascending order using bubble sort:

[12, 8, 15, 3, 9]

Show the state of the list after each complete pass.

Show Mark Scheme Answer

Pass 1: [8, 12, 3, 9, 15]

Pass 2: [8, 3, 9, 12, 15]

Pass 3: [3, 8, 9, 12, 15]

Pass 4: [3, 8, 9, 12, 15] - no swaps, sorted

(1 mark for each correct pass)

Boolean Logic & Truth Tables

Key Definition

Boolean logic uses only two values: True (1) and False (0). Logic gates are electronic circuits that perform Boolean operations and form the basis of how computers make decisions.

Logic Gates You Must Know

For the Edexcel GCSE, you need to understand these logic gates:

NOT Gate (Inverter)

Inverts the input. 0 becomes 1, 1 becomes 0.

Input A	Output Q
0	1
1	0

Q = NOT A

AND Gate

Output is 1 only when BOTH inputs are 1.

A	B	Q
0	0	0
0	1	0
1	0	0
1	1	1

Q = A AND B

OR Gate

Output is 1 when AT LEAST ONE input is 1.

A	B	Q
0	0	0
0	1	1
1	0	1
1	1	1

Q = A OR B

XOR Gate (Exclusive OR)

Output is 1 when inputs are DIFFERENT.

A	B	Q
0	0	0
0	1	1
1	0	1
1	1	0

Q = A XOR B

NAND Gate (NOT AND)

Opposite of AND gate.

A	B	Q
0	0	1
0	1	1
1	0	1
1	1	0

Q = NOT (A AND B)

NOR Gate (NOT OR)

Opposite of OR gate.

A	B	Q
0	0	1
0	1	0
1	0	0
1	1	0

Q = NOT (A OR B)

Common Exam Mistake

Don't confuse OR and XOR! The key difference is when both inputs are 1:

OR: 1 OR 1 = 1 (at least one is true)
XOR: 1 XOR 1 = 0 (inputs must be different)

Constructing Truth Tables

For expressions with multiple inputs, list all possible combinations. For n inputs, you need 2ⁿ rows:

2 inputs = 4 rows (2² = 4)
3 inputs = 8 rows (2³ = 8)

Exam Tip: Input Pattern

For 2 inputs, use this pattern to ensure all combinations are covered:

Column A: 0, 0, 1, 1 (doubles up)
Column B: 0, 1, 0, 1 (alternates)

Craig 'n' Dave: Simple Logic Gates

Complete guide to all logic gates with examples

Craig 'n' Dave: Truth Tables

How to construct and interpret truth tables

June 2022 - Paper 1 3 marks

Complete the truth table for: Q = (A AND B) OR (NOT A)

Show Mark Scheme Answer

A	B	A AND B	NOT A	Q
0	0	0	1	1
0	1	0	1	1
1	0	0	0	0
1	1	1	0	1

1 mark for intermediate columns, 2 marks for correct Q values

Content based on: BBC Bitesize, Save My Exams

Topic 1 Quiz

Test your knowledge with this multiple-choice quiz. When you finish, you can download a PDF certificate with your results!

Quiz Instructions

Answer all 15 questions, then submit to see your score. You can then generate a PDF report to download or send to your teacher.

Enter Your Details

Your Name:

Teacher's Email (optional):

Key Terms Summary

Algorithm - Step-by-step instructions to solve a problem

Decomposition - Breaking problems into smaller parts

Abstraction - Focusing on essential details only

Pattern Recognition - Finding similarities to reuse solutions

Pseudocode - Plain English algorithm representation

Flowchart - Visual diagram showing algorithm flow

Variable - Named storage that can change value

Constant - Named storage with fixed value

DIV - Integer division (whole number only)

MOD - Remainder after division

camelCase - Naming style: firstWordLowerCase

snake_case - Naming style: words_with_underscores

Linear Search - Checking each item sequentially

Binary Search - Dividing sorted data in half repeatedly

Bubble Sort - Swapping adjacent elements

Merge Sort - Divide, sort, and merge approach

Boolean - True/False or 1/0 values

Truth Table - Shows all input/output combinations

AND Gate - Output 1 only if both inputs are 1

OR Gate - Output 1 if at least one input is 1