Algorithm classification
CIE A-Level Computer ScienceΒ· Unit 9: Algorithm design & problem solvingΒ· 15 min read
1. Brute Force Algorithmsβ β ββββ± 4 min
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.
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
- Calculate the total number of pairs: , which is a small, manageable number.
- 2
- Generate every possible pair of students from the group.
- 3
- Check the birthday of each pair to see if they match.
- 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.
2. Divide and Conquer & Greedy Algorithmsβ β β βββ± 5 min
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.
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
- At each step, the algorithm chooses the best possible coin (largest denomination) for the current remaining amount.
- 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
- This matches the core definition of a greedy algorithm, so the classification is greedy.
3. Dynamic Programming & Backtrackingβ β β β ββ± 6 min
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.
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
- The algorithm builds the solution one cell at a time (incrementally).
- 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
- This matches the core definition of backtracking, so this is the correct classification.
4. Answering Exam Questionsβ β β βββ± 4 min
Test your understanding:
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
Reveal answer
Divide and Conquer βCorrect! Quick sort is a classic divide and conquer algorithm.
Calculating the 20th Fibonacci number by storing each previous result instead of recalculating it is which classification?
Backtracking
Greedy
Brute Force
Dynamic Programming
Reveal answer
Dynamic Programming βRight! Storing overlapping sub-problem results is the core of dynamic programming.
5. Common Pitfalls
Wrong move:
Calling any recursive algorithm divide and conquer
Why:
Not all recursive algorithms split the problem into independent sub-problems. Many classifications can use recursion.
Correct move:
Confirm the problem is split into independent sub-problems with results combined before classifying as divide and conquer.
Wrong move:
Refusing to classify an algorithm as greedy because it doesn't find the optimal solution
Why:
Classification is based on approach, not outcome. Greedy approaches are still classified as greedy even if they don't guarantee the global optimum.
Correct move:
Classify based on the approach (locally optimal step choices) regardless of the final outcome.
Wrong move:
Confusing dynamic programming with divide and conquer
Why:
Both split problems into sub-problems, but divide and conquer only works for non-overlapping sub-problems.
Correct move:
If sub-problems repeat and results are stored to avoid re-calculation, it is dynamic programming.
Wrong move:
Confusing backtracking with brute force
Why:
Brute force checks all possible solutions, while backtracking prunes invalid partial solutions early, checking far fewer candidates.
Correct move:
If the algorithm abandons invalid partial solutions, it is backtracking, not brute force.
Wrong move:
Only writing the classification when an explanation is asked for
Why:
2-mark questions allocate 1 mark for the classification and 1 mark for the supporting explanation.
Correct move:
Always add one sentence linking the algorithm's approach to the classification's core characteristic when explanation is required.
6. Quick Reference 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 |
7. Frequently Asked
How many marks do algorithm classification questions carry?
Most are 1-2 marks: 1 mark for the correct classification, 1 mark for a supporting explanation of why it fits.
When this came up on past exams
AI-estimated based on syllabus patterns β cross-check with official past papers for accuracy. Use only as revision-focus signals.
- 2022 Β· 2
Identify algorithm classification
- 2023 Β· 2
Explain algorithm type choice
Going deeper
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.