Paradigms

Divide and conquer, greedy, dynamic programming, backtracking — the recognisable shapes of a solution, and how to tell which one a problem is asking for.

• Divide and ConquerSplit, solve, combine — and the Master Theorem that tells you which of those three steps actually decides the cost.core· typical O(n log n)· merge-sort O(n log n)· binary-search O(log n)
• Greedy AlgorithmsTaking the locally best option and never reconsidering — which is either optimal or badly wrong, and the only way to know is to prove it.core· typical O(n log n)· after-sort O(n)
• Dynamic ProgrammingRecursion plus a cache — and the real skill, which is choosing a state that makes the recurrence obvious rather than memorising table-filling loops.advanced· typical O(states × transitions)· knapsack O(n·W)· lcs O(n·m)
• BacktrackingExhaustive search that undoes its choices — and pruning, which is the entire difference between a solver that finishes and one that does not.advanced· permutations O(n!)· subsets O(2ⁿ)· n-queens O(n!) pruned