# Algorithm classification

> CIE A-Level Computer Science · 9618
> Source: https://www.owlsprep.com/study/cie-9618-u9-algorithm-classification/

This module covers the main classifications of algorithms for problem solving, their core characteristics, and how to correctly identify each type in CIE 9618 exam questions.

**Prerequisites:** [Basic algorithm design fundamentals](https://www.owlsprep.com/study/cie-9618-u9-algorithm-design-fundamentals/)

## Learning objectives

- Classify algorithms by their problem-solving approach
- Distinguish key characteristics of different algorithm types
- Identify the correct classification for a given problem scenario
- Answer algorithm classification questions meeting CIE mark scheme requirements

## Brute Force Algorithms

Brute force is the simplest algorithm classification, relying on checking every possible solution rather than using a more optimized approach.

**Brute Force Algorithm** — A brute force algorithm generates and checks every possible candidate solution to a problem, guaranteeing it will find all valid solutions if they exist.

*Example:* Checking all possible 3-digit combinations to open a locked padlock.

**Worked example:** A class of 10 students need to find all pairs of students that share the same birthday. What classification is a brute force approach to this problem?

1. 1. Calculate the total number of pairs: $C(10,2) = 45$, which is a small, manageable number.
2. 2. Generate every possible pair of students from the group.
3. 3. Check the birthday of each pair to see if they match.
4. 4. Since we check every possible pair (all possible candidate solutions), this matches the definition of a brute force approach.

> **Exam tip:** You must mention that brute force checks all possible solutions to get the explanation mark in exams.

## Divide and Conquer & Greedy Algorithms

Two of the most common optimized algorithm classifications are divide and conquer and greedy, both used for large problems that brute force would solve too slowly.

**Divide and Conquer** — Divide and conquer repeatedly splits a large problem into smaller, independent sub-problems of the same type, solves each recursively, then combines results to solve the original problem.

*Example:* Binary search, merge sort.

**Greedy Algorithm** — A greedy algorithm makes the locally optimal choice (the best possible choice at the current step) at each stage of the problem, rather than planning ahead for future steps.

*Example:* Dijkstra's shortest path algorithm, minimum spanning tree algorithms.

**Worked example:** A vending machine gives change using the fewest coins possible, and always uses the largest denomination coin that fits the remaining change. What classification is this approach?

1. 1. At each step, the algorithm chooses the best possible coin (largest denomination) for the current remaining amount.
2. 2. It does not check all combinations of coins to find the global minimum, it only makes the best local choice at each step.
3. 3. This matches the core definition of a greedy algorithm, so the classification is greedy.

## Dynamic Programming & Backtracking

Dynamic programming and backtracking are classifications used for more complex problems that require exploring or reusing partial solutions.

**Dynamic Programming** — Dynamic programming solves problems with overlapping sub-problems and optimal substructure by storing the results of previously solved sub-problems to avoid redundant calculation.

*Example:* Calculating Fibonacci numbers, longest common subsequence.

**Backtracking** — Backtracking builds solutions incrementally, and abandons (prunes) any partial solution as soon as it determines it cannot lead to a valid complete solution.

*Example:* Solving Sudoku, N-queens problem.

**Worked example:** To solve a 9x9 Sudoku, an algorithm tries a number in an empty cell, checks if it is valid, then moves to the next empty cell. If it gets stuck, it undoes the last number tried and tries the next possible value. What classification is this?

1. 1. The algorithm builds the solution one cell at a time (incrementally).
2. 2. If a partial solution is invalid (gets stuck with no valid numbers for the next cell), it abandons that partial solution and backtracks to try a different value earlier on.
3. 3. This matches the core definition of backtracking, so this is the correct classification.

## Answering Exam Questions

**Exam command terms**

CIE 9618 uses consistent command terms for algorithm classification questions:

- **State the classification** — Only name the algorithm type, no explanation needed for 1 mark *(State the classification of binary search (1 mark))*

- **Explain your answer** — Give one key characteristic of the classification that matches the given problem, 1 extra mark *(Explain why binary search fits your classification (2 marks))*

**Check your understanding**

Test your understanding:

1. Quick sort, which splits an array around a pivot, sorts each half, then combines results, is which classification?

   - Brute Force
   - Divide and Conquer
   - Greedy
   - Dynamic Programming

   *Why:* Correct! Quick sort is a classic divide and conquer algorithm.

2. Calculating the 20th Fibonacci number by storing each previous result instead of recalculating it is which classification?

   - Backtracking
   - Greedy
   - Brute Force
   - Dynamic Programming

   *Why:* Right! Storing overlapping sub-problem results is the core of dynamic programming.

## Common pitfalls

- **Wrong:** Calling any recursive algorithm divide and conquer
  - Why it fails: Not all recursive algorithms split the problem into independent sub-problems. Many classifications can use recursion.
  - Correct: Confirm the problem is split into independent sub-problems with results combined before classifying as divide and conquer.
- **Wrong:** Refusing to classify an algorithm as greedy because it doesn't find the optimal solution
  - Why it fails: Classification is based on approach, not outcome. Greedy approaches are still classified as greedy even if they don't guarantee the global optimum.
  - Correct: Classify based on the approach (locally optimal step choices) regardless of the final outcome.
- **Wrong:** Confusing dynamic programming with divide and conquer
  - Why it fails: Both split problems into sub-problems, but divide and conquer only works for non-overlapping sub-problems.
  - Correct: If sub-problems repeat and results are stored to avoid re-calculation, it is dynamic programming.
- **Wrong:** Confusing backtracking with brute force
  - Why it fails: Brute force checks all possible solutions, while backtracking prunes invalid partial solutions early, checking far fewer candidates.
  - Correct: If the algorithm abandons invalid partial solutions, it is backtracking, not brute force.
- **Wrong:** Only writing the classification when an explanation is asked for
  - Why it fails: 2-mark questions allocate 1 mark for the classification and 1 mark for the supporting explanation.
  - Correct: Always add one sentence linking the algorithm's approach to the classification's core characteristic when explanation is required.

## Cheatsheet

| Classification | Key Characteristic | Common Example |
| --- | --- | --- |
| Brute Force | Checks all possible solutions | PIN cracking |
| Divide and Conquer | Split into independent sub-problems | Binary search, merge sort |
| Greedy | Locally optimal choice at each step | Coin change, Dijkstra's |
| Dynamic Programming | Store overlapping sub-problem results | Fibonacci, LCS |
| Backtracking | Prune invalid partial solutions early | Sudoku, N-queens |

## What's next

Algorithm classification is a core foundation for all further work in algorithm design and analysis for CIE 9618. It helps you select appropriate approaches for new problems, understand why different algorithms are used for the same problem, and answer classification questions that regularly appear in Paper 2. Building a clear understanding of each classification's characteristics also prepares you for topics like time complexity analysis, where you compare the efficiency of different approaches to the same problem. Explore the following topics to build on this knowledge.

- [Standard searching algorithms](https://www.owlsprep.com/study/cie-9618-u9-standard-searching-algorithms/)
- [Standard sorting algorithms](https://www.owlsprep.com/study/cie-9618-u9-standard-sorting-algorithms/)
- [Algorithm tracing](https://www.owlsprep.com/study/cie-9618-u9-algorithm-tracing/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u9-algorithm-classification/