Study guides · Introductory

Choose among greedy methods, divide-and-conquer, and dynamic programming

Compare how algorithms reduce a problem and justify choices, using a coin example where a plausible greedy rule fails.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Separate a procedure from its justification
  2. A greedy choice needs a safety argument
  3. Distinguish division from reuse
  4. Count states and state the assumptions
  5. Ask Logeia about this articleCheck your understanding

Separate a procedure from its justification

Designing an algorithm means explaining both its steps and why those steps preserve a correct answer. Committing to a locally attractive choice, dividing into smaller independent problems, and reusing repeated subproblems are different ideas. Each becomes useful under particular assumptions rather than through its name alone.

Input properties can change which method works. Solve small instances by exhaustive search when possible, then look for repeated work or structure that can justify an improvement. Choosing a technique first and forcing the problem into it often hides the very conditions on which correctness depends.

A greedy choice needs a safety argument

A greedy method chooses by a local criterion and typically does not revisit earlier choices. For minimum coin change, taking the largest available coin looks plausible. With denominations 1, 3, and 4 and target 6, however, it chooses 4, 1, 1, while 3, 3 uses fewer coins. The attractive local rule is not a proof.

To justify a greedy algorithm, show that an optimal solution can include the selected choice, perhaps using an exchange argument. Passing a few examples is not the same as covering all allowed inputs. Searching for counterexamples helps reveal the assumptions that a successful proof must use.

Distinguish division from reuse

Merge sort divides an array, sorts smaller parts, and merges their results. Its design explains how solutions of smaller problems compose into a full solution. Dynamic programming identifies overlapping states and stores their answers for reuse. Whether code uses recursion is not the defining distinction.

For coin change, let f(x) be the smallest coin count for amount x. Compare candidates formed by adding one coin c to a reachable amount x-c, beginning with f(0)=0. Processing increasing amounts provides earlier answers when needed. Unreachable amounts and permitted denominations must be part of the state and transition definition.

Count states and state the assumptions

Dynamic programming does not make every difficult problem cheap. Too many states can exhaust time or memory. A table indexed by amounts up to A performs work depending on A, which is a different measure from the number of digits used to encode that amount. State what input-size measure a bound uses.

Explain the meaning of each state or subproblem, the transition or combination rule, the base case, a correctness argument, and the complexity. Saying only “it is recursive” or “the choice looks best” leaves essential reasoning out. Trace small cases and boundaries before drawing performance conclusions.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path