Draft: Greedy Algorithms

What is a greedy algorithm?

I wondered this myself. What subjects an algorithm to avarice? As it turns out, the adjective “greedy” has nothing to do what one might consider greed, and everything to do with taking a chance on a solution that might be incredibly efficient if everything goes well.

In a way, it reminds me of how the Houston Rockets play basketball. Could they theoretically have James Harden shoot 3-pointers every time they have possession and have it turn out well?

Sure, maybe.

But there are edge cases, like when really good defenders guard him.

Nobody can defend his step back 3 though… ;)

In reality, a greedy algorithm is more about:

• picking a first approach,
• proving that that approach is safe to use,
• using that same approach to solve any remaining subproblem(s).

This, of course, can be problematic if you don’t verify that the chosen approach is actually safe to use, e.g., that it won’t break due to edge cases.

This differs from brute force algorithms, in which each and every possible approach is attempted.

What’s an example?

// Example to be added

Resources

• https://towardsdatascience.com/algorithms-in-c-62b607a6131d https://www.freecodecamp.org/news/brute-force-algorithms-explained/
• https://book.huihoo.com/data-structures-and-algorithms-with-object-oriented-design-patterns-in-c++/html/page441.html
• https://medium.com/self-training-data-science-enthusiast/brute-force-algorithm-and-greedy-algorithm-13195d48e9bf