Proving Greedy Correctness
How do you know greedy works? Learn two proof techniques: the exchange argument and the stays-ahead argument to verify greedy strategies.
Lessons
1. Intro
Why proofs matter
2. The Problem with Intuition
When feelings fail
3. Two Proof Techniques
Your toolkit
4. Vocabulary - Exchange Argument
Swap to improve
5. Exchange Argument Structure
The template
6. Quiz: Exchange Argument
Test your understanding
7. Example - Activity Selection Exchange
Proving earliest-end-first
8. Activity Selection - The Exchange
Constructing the swap
9. Activity Selection - Completing the Proof
Induction finishes it
10. When Exchange Works Best
Problem characteristics
11. Vocabulary - Stays Ahead Argument
Always leading
12. Stays Ahead Structure
The template
13. Quiz: Stays Ahead
Test your understanding
14. Example - Activity Selection Stays Ahead
Alternative proof
15. Activity Selection - Base Case
First activity
16. Activity Selection - Inductive Step
Maintaining the lead
17. Activity Selection - Conclusion
Finishing the proof
18. When Stays Ahead Works Best
Problem characteristics
19. Exchange vs Stays Ahead
Choosing your approach
20. Quiz: Choosing a Technique
Apply your knowledge
21. Finding Counterexamples
When greedy fails
22. Counterexample - 0/1 Knapsack
Greedy ratio fails
23. Counterexample - Better Example
A clearer failure
24. Counterexample - The Classic
When fractional thinking fails
25. Why Greedy Fails for 0/1 Knapsack
The blocking problem
26. How to Find Counterexamples
Systematic approach
27. Quiz: Counterexample Thinking
Finding failures
28. Problem - Minimum Waiting Time
Proving shortest-first
29. Minimum Waiting - The Greedy Claim
Shortest first
30. Minimum Waiting - Exchange Proof
Swapping adjacent pairs
31. Minimum Waiting - Algorithm
Simple implementation
32. Problem - Tandem Bicycle
Maximize or minimize speed
33. Tandem Bicycle - Maximize Speed
Pair fast with slow
34. Tandem Bicycle - Minimize Speed
Pair fast with fast
35. Tandem Bicycle - Proof Sketch
Exchange argument
36. Problem - Class Photos
Taller in back row
37. Class Photos - Greedy Solution
Match by rank
38. Class Photos - Proof
Why sorting works
39. Quiz: Class Photos
Apply the algorithm
40. Common Proof Mistakes
Avoid these errors
41. Practice Strategy
Building proof skills
42. Section Recap
What we learned