This page is due for review. Re-read the key points and answer the self-check questions before recording your video.
Algorithms · Hub
Algorithm paradigms
Five ways of thinking about a problem rather than five algorithms: split it (divide and conquer), grab the best option (greedy), remember sub-answers (dynamic programming), try and undo (backtracking), and recognise when no fast method is known (NP-completeness).
Why it matters: most new problems are solved by recognising which paradigm fits. The paradigm tells you the shape of the algorithm and roughly what it will cost.
5 random questions mixed from all five paradigms.
Mixed review
Answer each one out loud before opening the sample answer.
flowchart TD
A{"Does the problem split into smaller copies?"} -->|"yes, independent parts"| DC["Divide and conquer"]
A -->|"yes, but parts repeat"| DP["Dynamic programming"]
A -->|no| B{"Is there a provably safe 'best next choice'?"}
B -->|yes| G["Greedy"]
B -->|no| C{"Is it a known NP-complete problem?"}
C -->|yes| NP["Use approximation, heuristics, or exact search on small inputs"]
C -->|no| BT["Backtracking with pruning"]
Key points
Divide and conquer works because independent subproblems can be solved separately and combined.
Dynamic programming beats plain recursion because it never solves the same subproblem twice.
Greedy is only correct with a proof because a locally best choice can block a better overall answer.
Backtracking is practical because pruning removes whole branches of the search early.
NP-completeness changes the goal because no polynomial exact algorithm is known for those problems.