Greedy Algorithms Explained: A Guide for A-Level Computer Science

Introduction to Greedy Algorithms

In the study of algorithms, a greedy algorithm is a strategy that makes the best possible decision at each individual step, hoping that these local choices will lead to a globally optimal solution. For your A-Level Computer Science course, understanding this paradigm is essential because it provides a simple, efficient way to solve many optimisation problems without the computational overhead of more complex methods like dynamic programming.

Think of a greedy algorithm as a hiker trying to reach the highest peak in a mountain range by always moving in the direction of the steepest incline. While this strategy is intuitive and fast, it does not always guarantee reaching the absolute highest peak (the global optimum). In this article, we will explore how these algorithms function, when they succeed, and why they are a staple of algorithmic design.

The Core Concept: Local vs Global Optima

The defining characteristic of a greedy algorithm is the 'greedy-choice property'. At every stage of the process, the algorithm selects the option that looks best at that specific moment. It never reconsiders its previous choices; it is 'myopic' or short-sighted.

• Local Optimum: The best choice available at the current step.
• Global Optimum: The best possible solution for the entire problem.

For some problems, such as finding the shortest path in specific graph types or making change with standard currency denominations, the greedy approach is guaranteed to find the global optimum. For others, it may only provide an approximation. Understanding this distinction is a key learning objective for your exams.

Worked Example 1: The Change-Making Problem

Imagine you are a cashier needing to return 67p in change using the fewest number of coins. The available denominations are 50p, 20p, 10p, 5p, 2p, and 1p.

Step-by-step greedy approach:

1. Start with the largest denomination less than or equal to the remaining total (67p).
2. Select 50p. Remaining: $67 - 50 = 17p$.
3. Select 10p. Remaining: $17 - 10 = 7p$.
4. Select 5p. Remaining: $7 - 5 = 2p$.
5. Select 2p. Remaining: $2 - 2 = 0p$.

Result: You used four coins (50p, 10p, 5p, 2p). Because our currency system is 'canonical', this greedy choice is also the global optimum. If you had chosen a 20p coin first, you would have failed to reach the target or used more coins.

Worked Example 2: Activity Selection

The Activity Selection problem is a classic A-Level topic. You are given a set of activities, each with a start time and a finish time. Your goal is to select the maximum number of non-overlapping activities that can be performed by a single person.

The Greedy Strategy: Always pick the activity that finishes earliest. This leaves the maximum amount of time remaining for other activities.

Scenario:

• Activity A: 1-4
• Activity B: 3-5
• Activity C: 0-6
• Activity D: 5-7
• Activity E: 8-9

Step-by-step:

1. Sort by finish time: A(4), B(5), C(6), D(7), E(9).
2. Select A (finishes at 4).
3. Check B: Starts at 3, which is before A finishes (4). Skip B.
4. Check C: Starts at 0, which is before A finishes (4). Skip C.
5. Check D: Starts at 5, which is after A finishes (4). Select D.
6. Check E: Starts at 8, which is after D finishes (7). Select E.

Result: You selected activities A, D, and E. This is the maximum set of 3 compatible activities.

Why Greedy Algorithms Matter

Greedy algorithms are highly valued for their efficiency. Because they make a single pass through the data and do not backtrack, they often run in linear or near-linear time, $O(n)$ or $O(n \log n)$. In real-world computing, where we often deal with massive datasets, an algorithm that provides a 'good enough' solution in milliseconds is often preferable to one that takes hours to find the perfect solution.

Common Mistakes

1. Assuming Greedy Always Works: Students often assume that because a greedy approach is simple, it must be the correct way to solve every optimisation problem. Always check if the problem has 'optimal substructure' before applying it.
2. Backtracking: A true greedy algorithm never changes a decision once it is made. If your logic requires you to go back and change a previous choice, you are likely looking at dynamic programming, not a greedy algorithm.
3. Ignoring Sorting: Many greedy algorithms require the input to be sorted (e.g., by finish time or weight-to-value ratio) before the greedy choice can be made. Forgetting to sort will lead to incorrect results.

Frequently Asked Questions

Q: Do greedy algorithms always find the best solution? No. They find the best local choice, which may or may not lead to the global optimum. They are often used for heuristics where an approximate solution is acceptable.

Q: What is the difference between greedy and dynamic programming? Greedy algorithms make a single, irrevocable choice at each step. Dynamic programming considers all possible sub-problems and stores their results to build the final solution, ensuring global optimality.

Q: Can I use greedy algorithms for the Knapsack Problem? For the 'Fractional Knapsack' problem, yes. For the '0-1 Knapsack' problem (where you cannot break items), a greedy approach does not guarantee the optimal solution.

Conclusion

Greedy algorithms are a powerful, intuitive tool in your computer science toolkit. By focusing on the best immediate choice, they offer a fast path to solving complex problems. To solidify your understanding, head over to MathInstructor AI to generate a free, narrated animated lesson that visualises these steps in action.