greedy-algorithms

Greedy Algorithms

Overview

Greedy algorithms are not justified by intuition that a local choice "seems good." They require a proof that one locally best choice can be part of some global optimum, and that the remaining work is a smaller problem of the same kind.

Core principle: name the greedy choice, prove it is safe by exchange or transformation, then prove the residual subproblem combines with that choice to form an optimum.

Shared CLRS Conventions

Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style. Keep recurrences, costs, inequalities, and asymptotic bounds in display LaTeX blocks rather than inline prose.

When giving examples or pressure-test answers, do not write interval notation, set notation, objective functions, asymptotic bounds, capacities, or inequalities inline. Introduce them in prose, then put the notation in a display block.

When to Use

• A prompt asks for a greedy algorithm, a proof of greedy correctness, an exchange argument, or a counterexample to a proposed greedy rule.
• The problem asks for maximizing compatible activities, fractional knapsack value, prefix-free Huffman codes, or offline cache hits with a known request sequence.
• You need to compare greedy with dynamic programming or explain why a locally attractive rule fails.
• A production question involves scheduling intervals, priority-queue merging, compression codes, cache replacement policies, or canonical coin systems.

Do not use this skill merely because an algorithm makes choices. If the choice must be made after comparing solved subproblems, use dynamic-programming. If the problem only needs repeated extrema or sorting mechanics, use sorting-and-order-statistics unless greedy correctness is central.

Greedy Proof Checklist

Before presenting a greedy algorithm, answer these questions:

1. What exactly is the greedy choice? Earliest finish, highest value density, two minimum frequencies, furthest next use, shortest processing time, or another explicitly ordered choice.
2. What is the subproblem after the choice? It should be one residual instance, not a family of alternatives that still need comparison.
3. Why is the choice safe? Use an exchange argument, cut-and-paste proof, or transformation from an arbitrary optimum to an optimum that includes the greedy choice.
4. Why does optimal substructure hold? An optimal solution to the residual subproblem plus the greedy choice must produce an optimal solution to the original problem.
5. What preprocessing or data structure makes choices fast? Sorting, a min-priority queue, next-use tables, or a sweep structure often carries the running time.
6. What tempting greedy rules fail? Give a concrete counterexample when rejecting a rule; do not merely say it is not locally safe.