<aside> <img src="https://super.so/icon/dark/alert-triangle.svg" alt="https://super.so/icon/dark/alert-triangle.svg" width="40px" /> In addition to the sub–optimality property from dynamic programming, greedy algorithms also need to satisfy the greedy exchange property for them to work

</aside>

Question. Can we find the optimal sequence of decisions without actually solving recursive subproblems?

$\star$ Greedy Algorithm Problems

Greedy

@Remark Both Prim’s and Kruskal’s MST are also greedy algorithms.

Summary & Patterns

Finding the Greedy Solution

Find the local best choice first, and keep making these choices if they are compatible with the previous ones. No recursive subproblems here.

Greedy Strategies From the Problems Above

• The class that ends the earliest and doesn’t conflict with previous choices from class scheduling
• The farthest gas station we can reach from the driving problem
• The safe edge that has the minimum weight in both Prims and Kruskal’s

The Greedy Exchange Argument

1. Show that there’s an arbitrary optimal solution $\ce {OPT}$ different from greedy solution $A$.
2. Find the “first difference” between $\ce{OPT}$ and $A$ .
   1. For a more rigorous proof, you also need to show that this difference actually exists
3. Argue that exchanging this optimal choice with a greedy choice will NOT make the solution worse. Doesn’t have to make it better.
4. Use induction to show that the entirety of $\ce{OPT}$ can be swapped with $A$
   • Depending on the professor, you probably don’t need to explicitly do this step

Go to next:

◈ The Only Graph Traversal Algorithm