decision procedure
A fixed series of questions that, answered in order, tells you which technique to try on an unfamiliar problem.
In more detail
The course asks: need every solution, then backtracking; optimal substructure with overlapping subproblems, then dynamic programming; a greedy-choice property as well, then greedy; independent halves, then divide and conquer. Earlier questions take priority. Verifying by running two approaches and comparing answers catches mistakes.
Related terms
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
Taught in
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers