5 ms·

Thanks for this! This is something I've been practicing of late. I realized that have a lot of problem in arguing the correctness of greedy algorithms. Do you h

by svrma 6y ago

Thanks for this! This is something I've been practicing of late. I realized that have a lot of problem in arguing the correctness of greedy algorithms. Do you have any recommendation for a collection of proof techniques useful for greedy algorithms?

drallison 6y ago
Kinda depends whether by "correctness" you mean "proof". I always found Social Processes and Proofs of Theorems and Programs by Richard A. De Millo, Richard J. Lipton, and Alan J. Perlis inspirational. I do not know of any collection of proof techniques that would be uniformly useful for greedy algorithms. If you discover such a collection, please share it with me.