Greedy Algorithms Unleashed: A Journey into Intelligent Decision Making

What is Greedy Algorithm?

Greedy algorithm is nothing but a paradigm which builds problems piece by piece. In Greedy, at any instant, we choose a piece of solution which will offer the most obvious and immediate benefit. For example the famous problem Fractional Knapsack. We keep on choosing the items which are local maxima that is, the items which have maximum value of "profit per unit weight" and in the end get the global maximum.

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result.

The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top-down approach.

This algorithm may not produce the best result for all the problems. It's because it always goes for the local best choice to produce the global best result.

List of Greedy Algorithm

• Dijkstra’s Shortest Path
• Kruskal’s Minimum Spanning Tree (MST)
• Prim's Minimum Spanning tree
• Huffman Coding

When to use?

Whenever we see optimum or maximum or minimum or largest or smallest, the first approach which should strike our mind should be Greedy or Dynamic Programming. If the problem is solvable via recursion, one should do for memoized recursion or DP else start with the brute force and reduce it to Greedy.

That's all in this blog. Will see couple of questions in next blog. Meanwhile you can book 1:1 session with me to discuss any thing about software development.