• i. Greedy and Exchange Arguments: A greedy algorithm commits to the locally best choice and never undoes it.
• ii. Matroids: A matroid is exactly the structure on which the sorted greedy is always optimal.
• iii. Interval Problems: Intervals on a line produce interval graphs, which are perfect:
• iv. Scheduling and Partitioning: Scheduling problems are a map of what’s easy and what’s NP-hard.