Algorithms

Overview

Algorithms are the foundation of Computer Science. They are simply finite sequences of clear, unambiguous instructions used to solve problems or achieve objectives. Whether you are programming a simple calculator or the AI behind a self-driving car, you are using algorithms.

In your GCSE exam, you won't just be asked to write code; you will be tested on your computational thinking. This means you must be able to design algorithms using flowcharts and pseudocode, trace existing algorithms to see what they do, and evaluate different algorithms to determine which is more efficient. This topic connects heavily to programming constructs and data structures. Examiners love testing this through trace tables, identifying errors in code, and comparing searching/sorting methods.

---

Key Concepts

Concept 1: The Three Constructs

Every single algorithm, no matter how complex, is built from just three fundamental building blocks:

1. Sequence: Instructions are executed one after another, in the exact order they are written.
2. Selection: The algorithm makes a decision and chooses a path based on a condition. We use IF...THEN...ELSE statements for this. In a flowchart, this is represented by a diamond.
3. Iteration: The algorithm repeats a block of code. This is also known as looping.

**Understanding Iteration:**There are two types of iteration you must distinguish between:

• Count-controlled iteration: Repeats a specific, known number of times. We use a FOR loop for this. (e.g., "Do this 10 times").
• Condition-controlled iteration: Repeats until a specific condition is met. We use a WHILE or REPEAT UNTIL loop for this. (e.g., "Keep asking for a password UNTIL the correct one is entered").

Examiner Tip: Confusing these two is a very common mistake. Remember: FOR loops count, WHILE loops check conditions.

Concept 2: Trace Tables

A trace table is a manual way of stepping through an algorithm to track the changing values of variables. It is the most reliable way to figure out what a piece of code does or to find a logic error.

How to use them:

1. Create a column for every variable in the algorithm.
2. Create a separate column for any OUTPUT.
3. Work through the algorithm line by line. Every time a variable changes, write the new value in the correct column on a new row.

Why this works: Computers don't skip steps or make assumptions. By forcing yourself to write down the value at every single step, you act like the CPU, preventing you from making human logic leaps that lead to wrong answers.

Concept 3: Types of Errors

When writing algorithms, things go wrong. You must be able to identify three types of errors:

• Syntax Error: A mistake in the grammar or rules of the programming language. (e.g., missing a bracket, misspelling WHILE as WHLIE). The code will not run.
• Logic Error: The code runs perfectly without crashing, but it produces the wrong result. (e.g., using > instead of >=). The programmer's reasoning was flawed.
• Runtime Error: The code is grammatically correct, but something goes wrong while the program is executing, causing it to crash. (e.g., trying to divide a number by zero, or trying to open a file that doesn't exist).

Concept 4: Searching Algorithms

Computers need to find data quickly. You must know two methods:

Linear Search:

• How it works: Starts at the first item and checks every single item one by one until the target is found or the end of the list is reached.
• Advantage: Works on unsorted lists.
• Disadvantage: Very slow for large lists (inefficient).

Binary Search:

• How it works: Looks at the middle item. If the target is smaller, it discards the right half. If the target is larger, it discards the left half. It repeats this halving process until the item is found.
• Advantage: Extremely fast and efficient for large lists.
• Disadvantage: The list MUST be sorted first. (Examiners will almost always test this fact!).

Concept 5: Sorting Algorithms

Organising data is crucial. You must know two sorting methods:

Bubble Sort:

• How it works: Compares adjacent pairs of items. If they are in the wrong order, it swaps them. It makes multiple passes through the list. After each pass, the largest unsorted item "bubbles" up to its correct position at the end.
• Pros/Cons: Simple to write and uses very little memory (sorts in place). However, it is very slow for large lists.

Merge Sort:

• How it works: Uses a "divide and conquer" approach. It repeatedly splits the list in half until every item is in its own list of one. Then, it merges pairs of lists back together in the correct order until one sorted list remains.
• Pros/Cons: Much faster than bubble sort for large lists. However, it requires more memory because it creates new lists during the splitting and merging process.

---

Listen to the Podcast

Reinforce your learning by listening to our 8-minute deep dive into Algorithms, featuring examiner tips and a quick-fire recall quiz.

---

Mathematical/Scientific Relationships

While not formulas in the traditional physics sense, you must understand the relational and logical operators used in algorithms:

• == or = : Equal to
• != or <> : Not equal to
• < : Less than
• <= : Less than or equal to
• > : Greater than
• >= : Greater than or equal to
• AND : Both conditions must be true
• OR : At least one condition must be true
• NOT : Reverses the logical state (True becomes False)

Practical Applications

• Binary Search in the real world: When you search for a contact in your phone, the software uses a binary search (or similar efficient algorithm) to find the name instantly out of thousands, because your contacts are kept alphabetically sorted.
• Trace Tables: Software developers use "debuggers" which essentially automate the trace table process, allowing them to step through code line-by-line to watch variables change and catch logic errors.