# Greedy Algorithm Tutorial – Examples, Application and Practice Problem

Greedy Algorithm is defined as a method for solving ** optimization problems** by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It works for cases where

**or**

**minimization****leads to the required solution.**

**maximization**Table of Content

- What is Greedy Algorithm?
- Characteristics of Greedy Algorithm
- Examples of Greedy Algorithm
- Why to use Greedy Approach?
- How does the Greedy Algorithm works?
- Greedy Algorithm Vs Dynamic Programming
- Applications of Greedy Algorithms
- Advantages of Greedy Algorithms
- Disadvantages of the Greedy Approach
- Greedy Algorithm Most Asked Interview Problems
- Frequently Asked Questions on Greedy Algorithm

## What is Greedy Algorithm?

A ** greedy algorithm** is a problem-solving technique that makes the best local choice at each step in the hope of finding the global optimum solution. It prioritizes immediate benefits over long-term consequences, making decisions based on the current situation without considering future implications. While this approach can be efficient and straightforward, it doesn’t guarantee the best overall outcome for all problems.

However, it’s important to note that not all problems are suitable for greedy algorithms. They work best when the problem exhibits the following properties:

The optimal solution can be constructed by making the best local choice at each step.**Greedy Choice Property:**The optimal solution to the problem contains the optimal solutions to its subproblems.**Optimal Substructure:**

## Characteristics of Greedy Algorithm

Here are the characteristics of a greedy algorithm:

- Greedy algorithms are simple and easy to implement.
- They are efficient in terms of time complexity, often providing quick solutions.
- Greedy algorithms are used for optimization problems where a
choice leads to a**locally optimal**solution.**globally optimal** - These algorithms do not reconsider previous choices, as they make decisions based on current information without looking ahead.
- Greedy algorithms are suitable for problems for optimal substructure.

These characteristics help to define the nature and usage of greedy algorithms in problem-solving.

## Examples of Greedy Algorithm

Several well-known algorithms fall under the category of greedy algorithms. Here are a few examples:

This algorithm finds the shortest path between two nodes in a graph. It works by repeatedly choosing the shortest edge available from the current node.**Dijkstra’s Algorithm:**This algorithm finds the minimum spanning tree of a graph. It works by repeatedly choosing the edge with the minimum weight that does not create a cycle.**Kruskal’s Algorithm:**This problem involves selecting items with the highest value-to-weight ratio to fill a knapsack with a limited capacity. The greedy algorithm selects items in decreasing order of their value-to-weight ratio until the knapsack is full.**Fractional Knapsack Problem:**: The greedy algorithm can be used to schedule jobs or allocate resources in an efficient manner.**Scheduling and Resource Allocation**: The greedy algorithm can be used to make change for a given amount with the minimum number of coins, by always choosing the coin with the highest value that is less than the remaining amount to be changed.**Coin Change Problem**: The greedy algorithm can be used to generate a prefix-free code for data compression, by constructing a binary tree in a way that the frequency of each character is taken into consideration.**Huffman Coding**

## Why to use Greedy Approach?

Here are some reasons why you might use the Greedy Approach:

The Greedy Approach is straightforward and easy to implement, making it a good choice for beginners.**Simple and easy to understand:**It usually finds a solution quickly, making it suitable for problems where time is a constraint.**Fast and efficient:**While not always optimal, the Greedy Approach often finds a solution that is close to the best possible solution.**Provides a good enough solution:**The Greedy Approach can be used as a starting point for developing more complex algorithms.**Can be used as a building block for other algorithms:**The Greedy Approach can be applied to a wide range of optimization problems, including knapsack problems, scheduling problems, and routing problems.**Useful for a variety of problems:**

However, it’s important to remember that the Greedy Approach doesn’t always find the ** optimal solution**. There are cases where it can lead to suboptimal solutions. Therefore, it is necessary to carefully consider the problem and the potential drawbacks before using the Greedy Approach.

## How does the Greedy Algorithm works?

** Greedy Algorithm** solve optimization problems by making the best local choice at each step in the hope of finding the global optimum. It’s like taking the best option available at each moment, hoping it will lead to the best overall outcome.

Here’s how it works:

- Start with the initial state of the problem. This is the starting point from where you begin making choices.
- Evaluate all possible choices you can make from the current state. Consider all the options available at that specific moment.
- Choose the option that seems best at that moment, regardless of future consequences. This is the “greedy” part – you take the best option available now, even if it might not be the best in the long run.
- Move to the new state based on your chosen option. This becomes your new starting point for the next iteration.
- Repeat steps 2-4 until you reach the goal state or no further progress is possible. Keep making the best local choices until you reach the end of the problem or get stuck..Â

**Example:**

Let’s say you have a set of coins with values** {1, 2, 5, 10, 20, 50, 100} **and you need to give minimum number of coin to someone change for

**.**

**36**The greedy algorithm for making change would work as follows:

- Start with the largest coin value that is less than or equal to the amount to be changed. In this case, the largest coin less than
is36.20- Subtract the largest coin value from the amount to be changed, and add the coin to the solution. In this case, subtracting
from20gives36, and we add a16coin to the solution.20- Repeat steps 1 and 2 until the amount to be changed becomes 0.
So, using the greedy algorithm, the solution for making change for 36 would be one 20 coins, one 10 coin, one 5 coins and one 1 coin needed.

** Note:** This is just one example, and other greedy choices could have been made at each step. However, in this case, the greedy approach leads to the optimal solution.

The greedy algorithm is not always the optimal solution for every optimization problem, as shown in the example below.

- One such example where the Greedy Approach fails is to find the Maximum weighted path of nodes in the given graph.

- In the above graph starting from the root node
if we greedily select the next node to obtain the most weighted path the next selected node will be10that will take the total sum to5and the path will end as there is no child of15but the path5is not the maximum weight path.10 -> 5

- In order to find the most weighted path all possible path sum must be computed and their path sum must be compared to get the desired result, it is visible that the most weighted path in the above graph is
that gives the path sum10 -> 1 -> 30.Â41

- In such cases Greedy approach wouldn’t work instead complete paths from
toroothas to be considered to get the correct answer i.e. the most weighted path, This can be achieved by recursively checking all the paths and calculating their weight.Âleaf node

## Greedy Algorithm Vs Dynamic Programming

Below are the comparison of ** Greedy Algorithm** and

**based on various criteria:**

**Dynamic Programming**Criteria | Greedy Algorithm | Dynamic Programming |
---|---|---|

Basic Idea | Makes the locally optimal choice at each stage | Solves subproblems and builds up to the optimal solution |

Optimal Solution | Not always guaranteed to provide the globally optimal solution | Guarantees the globally optimal solution |

Time Complexity | Typically faster; often linear or polynomial time | Usually slower due to solving overlapping subproblems |

Space Complexity | Requires less memory; often constant or linear space | Requires more memory due to storing intermediate results |

Subproblems Overlapping | Does not handle overlapping subproblems | Handles overlapping subproblems efficiently |

Examples | Finding minimum spanning tree, Huffman coding | Matrix chain multiplication, shortest path problems |

Applications | Used when a greedy choice at each step leads to the globally optimal solution | Applied when the problem can be broken down into overlapping subproblems |

## Applications of Greedy Algorithms:

Finds the shortest path between two nodes in a graph.**Dijkstra’s shortest path algorithm:**Finds the minimum spanning tree for a weighted graph.**Kruskal’s minimum spanning tree algorithm:**Creates an optimal prefix code for a set of symbols based on their frequencies.**Huffman coding:**Determines the most valuable items to carry in a knapsack with a limited weight capacity.**Fractional knapsack problem:**Chooses the maximum number of non-overlapping activities from a set of activities.**Activity selection problem:**

## Advantages of Greedy Algorithms:

Greedy algorithms are often straightforward to implement and reason about.**Simple and easy to understand:**They can provide optimal solutions for specific problems, like finding the shortest path in a graph with non-negative edge weights.**Efficient for certain problems:**Greedy algorithms generally have lower time complexity compared to other algorithms for certain problems.**Fast execution time:**: The decision-making process in a greedy algorithm is often easy to understand and justify.**Intuitive and easy to explain**Greedy algorithms can be combined with other techniques to design more sophisticated algorithms for challenging problems.**Can be used as building blocks for more complex algorithms:**

## Disadvantages of the Greedy Approach:

Greedy algorithms prioritize local optima over global optima, leading to suboptimal solutions in some cases.**Not always optimal:**Proving the optimality of a greedy algorithm can be challenging, requiring careful analysis.**Difficult to prove optimality:**The order of input data can affect the solution generated by a greedy algorithm.**Sensitive to input order:**Greedy algorithms are not suitable for all problems and may not be applicable to problems with complex constraints.**Limited applicability:**

## Greedy Algorithm Most Asked Interview Problems:

Some of the popular problems on the Greedy Approach that are widely asked in interviews are:

Problems |
---|

Minimize Cash Flow among a given set of friends who have borrowed money from each other |

Minimum Number of Platforms Required for a Railway/Bus Station |

## Frequently Asked Questions on Greedy Algorithm:

### 1. What is a greedy algorithm?

A

is an algorithm that makes the best local choice at each step in the hope of finding the global optimum solution. It is a heuristic approach, meaning it does not guarantee finding the optimal solution but often provides a good approximation.greedy algorithm

### 2. When should I use a greedy algorithm?

are best suited for problems whereGreedy algorithmsexists. This means that the optimal solution to the problem can be constructed from the optimal solutions to its subproblems. Examples of problems where greedy algorithms are effective includeoptimal substructurepath algorithm,Dijkstra’s shortesttree algorithm, andKruskal’s minimum spanning.Huffman coding

### 3. What are the advantages and disadvantages of greedy algorithms?

Advantages of greedy algorithms:

- Easy to understand and implement.
- Often computationally efficient.
- Can provide good approximate solutions even when the optimal solution is difficult to find.

Disadvantages of greedy algorithms:

- Do not always guarantee finding the optimal solution.
- May not be applicable to all problems.

### 4. What are some examples of greedy algorithms?

Below are some example of greedy algorithms:

- Dijkstra’s shortest path algorithm
- Kruskal’s minimum spanning tree algorithm
- Huffman coding
- Fractional knapsack problem
- Activity selection problem

### 5. Where can I learn more about greedy algorithms?

There are many resources available online and in textbooks to learn more about greedy algorithms. Some good resource to start learning Greedy algorithms are:

- GeeksforGeeks
- MIT OpenCourseware:

**Related Articles:**

- Greedy Algorithms (General Structure and Applications)
- Top 20 Greedy Algorithms Interview Questions
- Most recent published articles on Greedy Algorithm
- Practice problems on Greedy Algorithms