Greedy Module • Page 21

Greedy Strategy — Introduction

Greedy algorithms build a solution step-by-step by choosing the best-looking option right now, then committing to it (no backtracking). They can be extremely fast — but only work when the problem has the right structure.

Key idea: best now + commit

Two properties: Greedy-choice + Optimal substructure

Goal today: know when greedy works and when it fails

Learning goals Start here

What should you learn from this page?

Explain what a greedy algorithm is (and what it is not).
Differentiate local best choices from a global best solution.
Understand the two correctness ideas: Greedy-choice property and Optimal substructure.
See a real counterexample where greedy fails.
Recognize the common greedy template used in many problems.

Remember: Greedy is confident. It commits early. That’s why it’s fast — and why it can fail.

Local vs Global optimal Intuition

Local vs Global intuition

Start → “Best now” → … later choices → Final answer

Greedy bets that choosing “best now” will not block the best final solution.

Greedy template

A common exam-friendly pattern:

1) Decide a greedy rule
2) Sort by that rule (often)
3) Pick best feasible item
4) Commit and repeat

Greedy Skeleton (Select + Feasible) Template

Generic Greedy Skeleton (the template you'll see again)

Many greedy algorithms look different on the surface, but they share the same skeleton: keep selecting the “best” remaining candidate, and only accept it if the partial solution stays feasible.

Greedy(A) — pattern

Greedy(A):
  solution = ∅
  repeat:
      x = Select(A)            // greedy choice rule
      if Feasible(solution ∪ {x}):
          solution = solution ∪ {x}
  return solution

What does Select(A) mean?

It picks the next candidate using the greedy rule.
The rule depends on the problem:
Fractional Knapsack: max (value/weight) Job Sequencing: max profit first Kruskal: minimum edge weight Huffman: minimum frequency

What does Feasible(...) mean?

It checks whether adding x violates any constraints.
If the check fails, we skip that candidate (or try the next best one).
Examples:
Knapsack: total weight ≤ capacity MST: no cycle formed Scheduling: deadline not missed

Feasible vs Optimal + Solution Space Definitions

Feasible vs Optimal + Solution Space (tiny example)

Think in terms of “all valid solutions”

Solution space = the set of all feasible solutions (valid ones). The optimal solution is the best among them for the objective (maximum profit, minimum cost, etc.).

Example

Choose a subset from {2,3,5,7} such that sum ≤ 10. Objective: maximize the sum.

Feasible: {2,3} (sum 5) Feasible: {3,7} (sum 10) Feasible: {5,2,3} (sum 10) Not feasible: {5,7} (sum 12)

Key takeaway

All optimal solutions are feasible, but not all feasible solutions are optimal.
Greedy grows a solution by staying inside the feasible region step-by-step.
DP explores the solution space more thoroughly to guarantee the global optimum.

Exam line: Greedy builds a feasible solution incrementally; if the greedy-choice property holds, those local choices lead to an optimal solution.

Why greedy can be correct Two properties

The two properties (intuition)

A) Greedy-choice property

There exists an optimal solution that begins with the greedy choice.

Student version: Picking best now doesn’t block the best final answer.

B) Optimal substructure

After making a choice, the remaining problem is a smaller version of the same problem.

Student version: Optimal solution contains optimal solutions of its subproblems.

Important: Optimal substructure alone is not enough. Many DP problems have it, but greedy still fails unless the greedy-choice property also holds.

Greedy vs D&C vs DP Compare

Greedy vs Divide & Conquer vs Dynamic Programming

Paradigm	Key idea	Revisits choices?	Typical examples
Greedy	Pick best now, commit	No	Kruskal, Prim, Dijkstra, Huffman
Divide & Conquer	Split → solve → combine	No	Merge sort, Quick sort, Karatsuba
Dynamic Programming	Try alternatives + store best	Yes	0/1 Knapsack, LCS, Matrix-chain

Sticky takeaway Summary

Sticky takeaway

Greedy = best now + commit

Works when greedy-choice + optimal substructure

Can fail → test with counterexamples

Next pages will apply this template in classic greedy problems (Knapsack, Job Sequencing, Huffman).

Coin Change counterexample Interactive

Interactive: Greedy can fail (Coin Change)

Try the famous counterexample: coins {1,3,4}, amount 6. Greedy picks 4+1+1 (3 coins) but optimal is 3+3 (2 coins).

Coin denominations (comma-separated)

Positive integers only. Order doesn’t matter.

Amount

Try 6, 7, 10, 11…

Greedy rule

Largest-coin greedy is the usual one.

Tip: hit Enter to run.

Greedy result

—

Optimal result (DP)

—

Verdict: —

Key terms — 1-minute recall Definitions

Greedy choice
Choosing the best available option at the current step.

Feasible solution
A partial or complete solution that satisfies all constraints.

Optimal solution
The best solution among all feasible solutions.

Solution space
The set of all feasible solutions to a problem.

Mini-checkpoint quiz 3 questions

Mini-checkpoint (3 questions)

Q1. Greedy algorithms revise earlier choices. (True/False)

Q2. Name the two ideas behind greedy correctness.

Q3. For coins {1,3,4} and amount 6, greedy uses how many coins?

—

Next pages Navigation

22 — Fractional Knapsack 23 — Job Sequencing 24 — Huffman Coding 25 — Union–Find

Note: File names above are placeholders. Adjust them to your actual page names.