The Paradigm Lens: Brute Force, Greedy, Divide-and-Conquer, and How to Recognise Which One Fits

Hook #

You've spent the last 8 courses building algorithms one at a time. Quicksort, BFS, Dijkstra, quickselect — each handled separately, each with its own analysis. This course is different. It steps back and asks: across all those algorithms, what patterns keep repeating? It turns out there are roughly four — brute force, greedy, divide-and-conquer, and dynamic programming — and almost every algorithm you'll meet for the rest of your career is a member of one of these families. The skill this course trains isn't "memorise more algorithms." It's paradigm recognition — given a problem, look at its structure and know which family to reach for.

What you'll be able to do by the end of this lesson #

• Name the four major algorithmic paradigms — brute force, greedy, divide-and-conquer, dynamic programming — and state their core technique in one sentence each.
• Recognise the recurring features of a problem that suggest each paradigm: optimal substructure, overlapping subproblems, greedy choice property, independent subproblems.
• Apply a simple decision tree to a new problem to identify which paradigm fits.
• Identify when no polynomial-time paradigm applies and the problem requires brute force (or approximation).

A quick try before we start #

Here are three problems. For each, predict which technique you'd reach for before reading the lesson:

1. Given a road map and a start city, find the shortest route to every other city.
2. Given a list of meeting times, schedule as many non-overlapping meetings as possible.
3. Given a sorted array of 1 billion numbers, find a specific value.

Don't worry about getting them right — the point is to notice what shape of reasoning each problem invites. Write your answers down. We'll return to them.

The core idea, from first principles #

An algorithmic paradigm is a high-level strategy for breaking a problem into pieces that can be solved. The four paradigms most useful for everyday engineering:

1. Brute force / exhaustive search #

Strategy: try every possibility. Pick the one that satisfies the constraints (or the best one, by some metric).

When to use: as a baseline, always. As the actual solution when the search space is small enough.

Examples: check every pair in an array; try every subset; permute the input and test each ordering.

Cost: typically exponential — O(2ⁿ⁾ for subsets, O(n!) for permutations. Fine for n ≤ 20-25; infeasible beyond.

The honest engineering use: brute force is the correctness baseline. When you write a cleverer algorithm, run it against the brute-force version on small inputs to confirm correctness. The brute-force version is also the fallback when the input is small enough to make cleverness unnecessary.

2. Greedy #

Strategy: at each step, make the locally optimal choice. Don't reconsider.

When to use: when the problem has the greedy choice property (a locally optimal choice leads to a globally optimal solution) and optimal substructure (the problem reduces to a smaller version of itself after the choice).

Examples: activity selection (always pick the meeting that ends earliest), fractional knapsack (always grab the highest value-per-weight item), Huffman coding (always merge the two lowest-frequency nodes), Dijkstra's algorithm (always finalise the closest unfinalised vertex), Kruskal's MST (always add the cheapest unused edge that doesn't form a cycle).

Cost: typically O(n log n) — you sort the choices, then process in order. Cheap and elegant when it works.

The trap: greedy fails on problems that look similar but don't have the greedy choice property. The classic example: 0/1 knapsack (binary items, can't split) — fractional knapsack's greedy strategy (highest value-per-weight) gives a suboptimal answer. Lesson 3 covers proving when greedy is correct.

3. Divide and conquer #

Strategy: divide the problem into independent subproblems. Solve each recursively. Combine the results.

When to use: when the problem has independent subproblems (no shared work between them) and a way to combine them.

Examples: merge sort (split in half, sort each, merge), quicksort (partition, sort each side), closest-pair-of-points (split by median x-coordinate, recurse, handle boundary), binary search (one subproblem, half the size — sometimes called decrease and conquer), Strassen's matrix multiplication (split into 4 quadrants, recurse, combine with 7 multiplications instead of 8).

Cost: typically O(n log n) — analysed by the master theorem (Course 1.2 lesson 4).

Recognising D&C: look for the words "split," "halve," "independent halves." If you can recurse on smaller versions of the same problem and combine the results, D&C applies.

4. Dynamic programming #

Strategy: divide into subproblems that share work. Compute each subproblem once, store the answer, reuse it.

When to use: when the problem has overlapping subproblems (the same sub-problem appears in many recursive calls) and optimal substructure.

Examples: Fibonacci numbers (without memoisation, exponential recursion; with memoisation, linear), longest common subsequence, edit distance, knapsack (0/1 variant), all-pairs shortest paths (Floyd-Warshall), matrix-chain multiplication.

Cost: typically polynomial — O(n²) or O(n³), where the polynomial degree is the number of dimensions of the subproblem table.

Recognising DP: look for problems with "find the optimal way to..." that don't satisfy the greedy choice property. If naive recursion computes the same subproblem multiple times, DP is likely the answer.

(DP is on the menu of paradigms but this course covers brute-force, greedy, and D&C. DP gets its full treatment in Course 4.3 or later — but you'll see it here as the foil that explains why some problems need more than greedy.)

The decision tree #

Given a new problem, here's the rough reasoning to pick a paradigm:

text1. Is the input small (n ≤ 20)? → Brute force is fine.
2. Can you split the problem into independent subproblems and combine?
   → Divide and conquer.
3. Is there a locally optimal choice that's always part of a globally optimal solution?
   → Greedy. (Prove it — lesson 3.)
4. Are subproblems shared across the recursion tree?
   → Dynamic programming.
5. Does none of these fit? Is the problem combinatorial in nature with no
   obvious structure?
   → It might be NP-hard; consider approximation, randomisation, or brute force.

This isn't a strict algorithm; it's a triage. Real problems often invite multiple paradigms; the choice is shaped by input size, accuracy requirements, and code complexity. But the questions above are the right first ones to ask.

Back to the warm-up #

1. Shortest routes from one city to all others → Greedy (Dijkstra's algorithm). At each step, finalise the closest unfinalised vertex. Course 3.3 covers Dijkstra explicitly later; the greedy paradigm is what powers it.
2. Schedule as many non-overlapping meetings as possible → Greedy (activity selection). Always pick the meeting that ends earliest among compatible candidates. Classic introduction to greedy in lesson 2.
3. Find a value in a sorted array of 1 billion → Divide and conquer (binary search). Halve the search space at each step. Course 3.2 lesson 4 covered this.

If your warm-up answers matched (or got close), the paradigm lens is already partly there. If not, that's what this course will sharpen.

Why this works the way it does #

The deep reason paradigm thinking helps: most algorithm-design problems are recombinations of a small set of underlying patterns. Once you've internalised the patterns, novel problems become "is this a greedy problem dressed up?" rather than "I've never seen this; I have to invent something."

A second deep reason: the cost analysis is paradigm-specific. Greedy algorithms are typically O(n log n) because they sort first; D&C algorithms are typically O(n log n) by master theorem; DP is typically O(n²) or O(n³) by table size; brute force is exponential. Knowing the paradigm predicts the asymptotic class — and when an interviewer or colleague says "I have an O(n) algorithm for X," the paradigm tells you what would have to be true (likely greedy with O(n) processing, or a clever D&C with linear merge).

A third reason: paradigm recognition is a transferable skill across decades. The specific algorithms in CS textbooks rotate over time — heap sort was canonical in 1980, less so today; randomised algorithms were exotic in 1990, standard now. But the paradigms — divide work, choose greedily, exhaust possibilities, remember subproblem answers — are stable. A senior engineer in 2050 will still ask "is this greedy-shaped?" before reaching for a specific algorithm.

Explain it back to me #

A colleague asks: "I have a problem where I need to schedule jobs on machines to minimise total completion time. I tried greedy (always assign next job to least-loaded machine) and got the right answer on my test cases. Is greedy correct here?"

In your own words, untangle the question. What's the next thing they should do — not to find a faster algorithm, but to verify their greedy actually works? (Hint: lesson 3 is about exactly this.)

And one more: a teammate shows you an algorithm that uses recursion to solve a problem, recomputing the same subproblems millions of times. They ask: "is there a way to make this faster?" Without knowing the specific problem, name the paradigm shift they likely need.

A small exercise #

For each problem, name the most likely paradigm and justify in one sentence:

1. Find the largest sum of any contiguous subarray in an array of integers (some negative).
2. Schedule classroom assignments: given lectures with start/end times and a number of classrooms, assign each lecture to a classroom such that no classroom has overlapping lectures.
3. Optimal binary search tree: given keys with access frequencies, build a BST that minimises expected access cost.
4. Find all triples (a, b, c) in an array such that a + b + c = 0.
5. Given a tree, find the diameter (longest path between any two nodes).

Where this connects #

Backward: Course 3.2 lesson 5 (quickselect) was your first taste of "partition once, recurse into one side" — a divide-and-conquer variant. Course 3.1 (Graph Fundamentals) introduced BFS and DFS; both are paradigms in their own right (graph search) but used to implement greedy algorithms like Dijkstra's. Course 1.2 lesson 4 (master theorem) gave you the tool to analyse D&C recurrences. Course 2.3 lesson 4 (Bloom filters) showed an approximate algorithm — sometimes the right answer when none of the four standard paradigms gives you what you need.

Forward: Lesson 2 (Greedy in depth) covers the canonical greedy examples (activity selection, fractional knapsack, Huffman). Lesson 3 (greedy correctness) teaches you to prove greedy works — without which you'll guess wrong half the time. Lesson 4 (D&C) covers master theorem applications including Strassen's and closest pair. Lesson 5 (decrease-and-conquer) is the special case where one of the D&C subproblems is the full original problem minus a small piece. Course 4.3 (Algorithm Design Paradigms II) introduces dynamic programming properly, completing the paradigm menu.

The zc-greedy-vs-dp-showdown project is the natural capstone for this course — given a workload, compare greedy and DP solutions empirically. Build it after lesson 3; by then you'll know how to recognise when greedy is wrong and DP is required.

Carry forward one mental habit: the first question to ask about any algorithm is which paradigm it's from. Once you know, you know roughly what its cost will be, what its constraints are, and what's the standard trap. Paradigm-first thinking is the closest thing to a superpower in algorithm design.