Choosing an Approach
Five approaches, one question: which does this problem call for?
That is the question Module 1 opened with — recognising which strategy a problem needs, rather than mastering one and applying it everywhere. The course closes on the same idea with real algorithms behind it.
The five, side by side
| Approach | Idea | Optimal? | Cost | Fails when |
|---|---|---|---|---|
| Brute force | Try everything | Yes | Grows with the search space | The space is too large |
| Divide-and-conquer | Split, solve, combine | Yes | Recursion + extra memory | Sub-problems overlap |
| Dynamic programming | Store sub-answers | Yes | Table of results | No overlap to exploit |
| Greedy | Best-looking step now | Only sometimes | Very cheap | Greedy-choice property fails |
| Randomized | Use chance | Expected / probable | Cheap | You need a hard guarantee |
Questions that decide it
1. How large is the search space? Small enough to enumerate → brute force, and be done. This is not a failure of ambition; it is the right answer when it is the right answer.
2. Does the problem split into independent pieces? Yes → divide-and-conquer.
3. Do the pieces repeat? Yes → dynamic programming. This is the one distinction students most often miss, and it is exactly the difference between merge sort and Fibonacci.
4. Is there an obvious best next step, and can you argue it is safe? Yes to both → greedy. The second half matters. Without the argument you have a heuristic, not an algorithm.
5. Would unpredictability help, or is a good average enough? Yes → randomized.
The same structure, different answers
Two problems can look alike and need opposite approaches.
| Merge sort | Fibonacci | |
|---|---|---|
| Recursive definition | Yes | Yes |
| Splits into smaller problems | Yes | Yes |
| Sub-problems overlap | No | Yes |
| Right approach | Divide-and-conquer | Dynamic programming |
| Wrong approach costs | – | 2,692,537 calls for fib(30) |
And the greedy example from earlier:
| Maximise task count | Maximise task value | |
|---|---|---|
| Same tasks, same time limit | Yes | Yes |
| Greedy shortest-first | Optimal | Wrong by 35 |
| Right approach | Greedy | Dynamic programming |
Nothing about the algorithm changed. Only the objective did.
The honest summary
- Brute force is not a beginner's approach to be outgrown. It is correct, simple, and the baseline you check clever code against.
- Divide-and-conquer wins on scale, not on small inputs. Sorting four items with it costs more than it saves.
- Dynamic programming is not the opposite of recursion. Memoisation is recursion, with a memory.
- Greedy is fast and often wrong. Its correctness is a claim requiring proof, not an observation from a few examples.
- Randomized trades certainty for either time or correctness — and you should know which.
Back to Module 1
The problem-solving process was: understand the problem, formulate a model, develop an algorithm, write the program, test it, evaluate the solution.
Choosing an approach happens at develop an algorithm — and it depends entirely on having done the first two properly. You cannot tell whether sub-problems overlap until you have modelled the problem. You cannot argue a greedy choice is safe until you know precisely what "best" means.
That is why the course begins with problem-solving strategies rather than syntax. The Python was the easy half.