Algorithmic Paradigms
The handful of shapes a solution can take, and the condition each shape needs in order to be correct.
A paradigm is the shape of a solution rather than a solution: try everything, grow the answer one element at a time, take the best local step, split and combine, solve each subproblem once, search and undo. There are not many of them, and most problems give way to one. Working out which one applies is usually more of the job than writing the code afterwards.
Each shape carries a condition, and the condition is what makes it correct rather than merely fast. Greedy needs an exchange argument. Dynamic programming needs overlapping subproblems and optimal substructure. Divide and conquer needs the pieces to be independent. Backtracking needs a constraint that can be tested on a partial candidate, and branch and bound needs that bound to be optimistic. When the condition fails, the code still runs and still returns something.
Brute force is where all of them start. It is correct by construction, it measures the search space the others are trying to avoid, and it is what you check the clever version against on small inputs. Each paradigm is then a specific way of not visiting part of that space: greedy walks one path, divide and conquer discards a half, dynamic programming visits each state once, branch and bound cuts anything that cannot beat the best answer found so far.
After this you can
- Name the paradigm behind an algorithm from the shape of its loop or its recursion
- State the condition a paradigm needs, and check it before trusting the output
- Use brute force as both the baseline cost and the correctness check for a faster version
- Tell apart pruning by constraint and pruning by bound
- Say what a randomized guarantee does and does not promise
The search space is every pair (i, j) with i before j. That is the whole cost of brute force: the size of the space, since each candidate is checked in constant time.
In this order
- Brute ForceTry every candidate; correct by construction, the baseline to beat.
- Incremental AlgorithmsGrow the sorted prefix by one element at a time, repairing the order as each arrives.
- GreedyTake the locally best choice and never look back; correct only when an exchange argument holds.
- Divide and ConquerSplit, solve recursively, combine, as a balanced tree of ranges.
- Dynamic ProgrammingSolve each overlapping subproblem once and reuse the answer.
- BacktrackingDepth-first search over partial solutions, undoing choices that cannot work.
- Branch and BoundBacktracking with a bound; prune any branch whose best possible outcome cannot beat the current best.
- Randomized AlgorithmsUse random choices so no single input is always bad (Las Vegas) or accept a small error chance (Monte Carlo).
Where people go wrong
Picking the paradigm from the wording
Knapsack and fractional knapsack read almost identically and need different shapes, because one lets an item be cut and the other does not. The condition selects the paradigm, not the phrasing of the question.
Branch and bound with a bound that is not optimistic
The bound has to be at least as good as the true best in that subtree, or a branch holding the answer gets cut. A bound that is merely plausible turns an exact search into a heuristic without changing a line of the search code.
Treating a randomized bound as an average case
Randomized quick sort's O(n log n) is an average over its own pivot choices, so no input is reliably bad for it. That is a different promise from an average over inputs, and only one of the two holds up against an adversary who sees your code.
Or a different category
Problem-Solving Patterns
You want the recognition cues for a concrete question rather than the shape of the solution behind them.
Complexity Analysis
The algorithm already exists and the question is what it costs.