Greedy Algorithms
Greedy choice property, exchange-argument proofs, and — just as important — recognizing when greedy is NOT provably correct.
Why we need this / what value this brings
Greedy solutions are fast and simple when they work, but the interview trap is applying greedy where it silently gives a wrong (not just suboptimal) answer.
When to use this
Interval scheduling, Huffman coding, minimum spanning tree (Kruskal's/Prim's) — problems with a provable greedy-choice property.
How to use or implement this
Before trusting a greedy solution, try to construct a counterexample; if you can't, sketch why the exchange argument holds.
Research questions
- Worth pairing with DynamicProgramming/ notes on problems that LOOK greedy but actually need DP (e.g. coin change with arbitrary denominations).
Empty folder — drop notes, links, and findings here as you research.