Hello friends! And, welcome to GeeksforGeeks. This tutorial will make you go through the Introductory concepts of Greedy Algorithms. Before we begin, lets consider a situation. There is this very intelligent guy who knows programming. He is very rich and has an infinite supply of 20$, 10$ and 5$ coins. Now he has a friend who needs some money. He ask for 35$ and that too in minimum number of coins. Now if he was to just give money he could have given it in quite a number of ways. He could give seven coins of 5$,a 10$ coin and five 5$ coins and so on. But since he is supposed to pay minimum number of coins, he has to come up with a greedy idea. After thinking for a while he proposes a solution. For every iteration, he has to give a coin of largest value that does not take him past the amount to be given. Now for 35$ the largest denomination he can start giving is 20$. Now 15$ are short to the amount, so the next largest he can give is 10$. Now he need 5$ more and since he have it as a denomination, one coin of 5$ and the loan is given in just 3 coins. Here the thing to note is that after every iteration he is making a choice, one which is greedy in nature giving the coin with largest value possible. This method will however not work for all denomination and currencies. Now we will formulate the idea of greedy algorithms. Greedy Algorithm follows problem solving approach of making the locally optimal choice at each stage with the hope of finding a global optimum. So at each stage we select a locally optimal value with the hope of getting to the best possible solution. This is a useful programming methodology. Lets see few of its Pros and Cons. So this approach is simple, easy to code and implement, and have reasonable running complexity. However the main drawback for this method is ,that there are very few cases wherein we end up getting the globally optimal value. With this example we'll see how the algorithm makes locally optimal choices however ending up at a non optimal solution. So in this tree we are required to get the largest root to leaf sum. That is starting from this root node here, we have to find a path ending at a leaf node and having sum of nodes as maximum. So lets start from our root node. The sum at start is 3. There are two possible path, 4 and 7 however here we make a greedy choice and choose the one that is maximum i.e 7. Our total now is 10. Now once at 7 we have to choose between 9 and 11. A greedy choice would be to select the larger of the two. We select 11 and end up having a path with sum as 21. Can we do better than this ? Yes! we have a path. If we start from 3, go to 4 and then to 20, this path would give us a sum of 27 which is greater than the one we have achieved through greedy method. So here we conclude that making locally optimal greedy choices don't always give us a globally optimal value. So, when are we suppose to use greedy methods ? All problems which are generally solved using greedy algorithms satisfy two properties. The greedy-choice property, i.e making the best choice at a moment leading to a global optimum. Next property is the optimal substructure, problems whose optimal solution can be constructed efficiently from optimal solutions of its subproblems This property may look similar to one in dynamic programming however one thing to note here is that greedy algorithm never reconsider its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find a solution. Finally we look at some applications which uses greedy algorithms. Activity Selection Problem, Huffman Coding, Job Sequencing Problem, Fractional Knapsack Problem, Prim's Minimum Spanning Tree are few of such applications. With this we wrap up this tutorial. If you have any doubts or suggestions please leave them in the comment section below. Thanks for watching!