Back to course

Exercise 2

Greedy Choice Lemma

ProofsAlgorithm AnalysisEasy-Medium Difficulty

Exam Format & Expectations

Greedy Choice questions typically ask you to:

  1. State the greedy algorithm - What choice does it make at each step?
  2. Prove correctness - Show the greedy choice is always safe
  3. State and prove the lemma - Formalize the greedy choice property

Key: The proof structure is usually: "Consider any optimal solution. We can modify it to include the greedy choice without losing optimality."

Past Exam Example: Interval Scheduling (2024)

Problem:

Given n intervals I = { I1, ..., In } where each interval Ii has:

  • Start time s(Ii)
  • Finish time f(Ii)

Two intervals Ii and Ij are compatible if they don't overlap. Goal: Find a maximum-size subset of mutually compatible intervals.

Question 2a: State the greedy algorithm

Full Solution(3/3)
Greedy Interval Scheduling
1. Sort intervals by finish time: f(I_1) ≤ f(I_2) ≤ ... ≤ f(I_n) 2. S = ∅ // selected intervals 3. last_finish = -∞ 4. for i = 1 to n: 5. if s(I_i) ≥ last_finish: 6. S = S ∪ {I_i} 7. last_finish = f(I_i) 8. return S

Greedy choice: Always select the interval with the earliest finish time that doesn't conflict with already selected intervals.

Question 2b: State and prove the Greedy Choice Lemma

Full Solution(7/7)
Greedy Choice Lemma

Lemma: Let I be a set of intervals. Let Ik be the interval in I with the earliest finish time. Then there exists an optimal solution that contains Ik.

Proof:

  1. Let OPT be any optimal solution.
  2. If Ik ∈ OPT, we're done.
  3. Otherwise, let Ij be the interval in OPT with the earliest finish time.
  4. By definition of Ik: f(Ik) ≤ f(Ij)
  5. Consider OPT' = (OPT \ { Ij }) ∪ { Ik }
  6. Claim: OPT' is a valid solution.
    • • Ik doesn't conflict with any interval in OPT \ { Ij }
    • • Because f(Ik) ≤ f(Ij), and Ij didn't conflict with them
  7. |OPT'| = |OPT| → OPT' is also optimal
  8. OPT' contains Ik. QED.

Example: Fractional Knapsack (2023)

Problem:

Given n items where item i has weight wi and value vi. We have a knapsack of capacity W. We can take fractions of items. Goal: Maximize total value while respecting weight constraint.

Greedy Strategy

Sort items by value-to-weight ratio: vi/wi in decreasing order. Take items in this order, taking as much as possible of each item.

Key Insight for Proof

If an optimal solution takes fraction x < 1 of the highest-ratio item, we can improve it by taking more of this item and less of lower-ratio items.

This exchange argument shows the greedy choice is safe.

Common Proof Techniques

Exchange Argument

  1. 1. Take any optimal solution OPT
  2. 2. If it contains greedy choice, done
  3. 3. Otherwise, exchange to include greedy choice
  4. 4. Show the exchange doesn't decrease quality
  5. 5. Conclude greedy choice is safe

Staying Ahead

  1. 1. Show greedy is "ahead" at each step
  2. 2. Define what "ahead" means precisely
  3. 3. Prove by induction on steps
  4. 4. Conclude greedy is optimal at end

Exam Tip: Structure is Key

Always use numbered steps in your proof. State the lemma formally before proving it. The structure often matters as much as the content for grading.

How to Excel at Greedy Choice Problems

1. Identify the Greedy Choice

Look for extremal properties:

  • Earliest/latest finish time
  • Highest/lowest ratio or density
  • Shortest/longest duration
  • Leftmost/rightmost position

2. State the Lemma Precisely

"∃ an optimal solution that contains the greedy choice" is different from "all optimal solutions contain the greedy choice"

3. Exchange Carefully

When exchanging elements, verify that:

  • The new solution is feasible
  • The objective value doesn't decrease
  • No constraints are violated
Previous: BacktrackingNext: Dynamic Programming