Proving Greedy Algorithms – Proof-First Notes (v1.0), Algorithm Theory, Academic Summary

What this is This is a proof-first set of handwritten notes on greedy algorithms. Most resources teach which greedy rule to apply. These notes focus on why the rule is correct. Every major greedy pattern is accompanied by: the exact greedy rule the correctness argument (exchange / invariant / cut) formal reasoning where it matters common failure boundaries This is not a beginner cheat sheet. It is meant for programmers who want clarity and correctness. What’s inside Foundations of greedy correctness greedy-choice property safety arguments proof templates Interval scheduling & partitioning Earliest Due Date (EDD) rule Fractional vs 0/1 knapsack (why greedy breaks) Priority-queue greedy patterns Job sequencing with deadlines (matroid view) Minimum Spanning Trees (Kruskal / Prim) Dijkstra’s algorithm (invariant proof) Matroids — the unifying theory behind greedy correctness All explanations are compact, math-driven, and handwritten. Who this is for Programmers preparing for: interviews competitive programming advanced DSA courses Students who want to prove greedy algorithms, not memorize rules Anyone tired of “trust me, this works” explanations