A step by step approach to learn Greedy Algorithm - Data Structure and Algorithms

Definition

A greedy algorithm is an approach for solving problems by making a sequence of choices, each of which looks best at the moment. In other words, a greedy algorithm always chooses the best immediate or local solution while aiming for a global optimum. Greedy algorithms are typically used for optimization problems.

Key Characteristics

• Local Optimization: Greedy algorithms make decisions based on the best choice at each step without considering the overall problem.
• Irrevocable Decisions: Once a choice is made, it cannot be undone.
• Efficiency: Greedy algorithms are often more efficient in terms of time and space compared to other approaches like dynamic programming or backtracking.

Example

One of the classic examples of a greedy algorithm is the Coin Change Problem.

Problem Statement

Given a set of coin denominations and a total amount, find the minimum number of coins needed to make the amount.

Greedy Approach

1. Start with the highest denomination.
2. Use as many coins of this denomination as possible without exceeding the amount.
3. Move to the next highest denomination and repeat until the amount is made.

Example

• Denominations: 1, 5, 10, 25 (standard US coins)
• Amount: 63

Steps:

1. Choose the highest denomination ≤ 63, which is 25.
   • Use 2 coins of 25. Remaining amount = 63 - 50 = 13.
2. Choose the highest denomination ≤ 13, which is 10.
   • Use 1 coin of 10. Remaining amount = 13 - 10 = 3.
3. Choose the highest denomination ≤ 3, which is 1.
   • Use 3 coins of 1. Remaining amount = 3 - 3 = 0.

Result:

• Total coins used: 2 (25) + 1 (10) + 3 (1) = 6 coins.

Types of Greedy Algorithms

Greedy algorithms can be classified based on their applications and structures:

Greedy Choice Property:

• An optimal solution can be reached by selecting the locally optimal choice at each step.
• Example: Activity Selection Problem - selecting the maximum number of non-overlapping activities.

Fractional Knapsack Problem:

• Items can be divided into fractions, and the goal is to maximize the total value within the given weight limit.
• Approach: Select items based on the highest value-to-weight ratio.
• Example: If you have items with weights and values, you choose the item with the highest value per unit weight until the knapsack is full.

Huffman Coding:

• Used for data compression.
• Approach: Build a binary tree with the least frequent characters having the longest codes.
• Example: Compressing text by assigning shorter codes to more frequent characters.

Prim's Algorithm for Minimum Spanning Tree (MST):

• Used to find the minimum spanning tree in a graph.
• Approach: Start from an arbitrary vertex and grow the MST by adding the smallest edge that connects a vertex in the tree to a vertex outside the tree.
• Example: Connecting all the nodes (cities) with the minimum total cable length.

Dijkstra's Algorithm:

• Used to find the shortest path from a source node to all other nodes in a graph with non-negative weights.
• Approach: Select the vertex with the smallest tentative distance, update the distances to its neighbors, and repeat until all vertices are processed.
• Example: Finding the shortest route on a map.

Limitations

Greedy algorithms do not always guarantee an optimal solution for all problems. They are suitable for problems where the greedy choice property holds. For some problems, other methods like dynamic programming or backtracking might be necessary to find the optimal solution.

In summary, greedy algorithms are a powerful tool in computer science for solving optimization problems, where the best local choice at each step leads to a globally optimal solution. However, their applicability depends on the specific problem and the nature of the optimal solution.

Problems with Greedy Algorithms

1. Not Always Optimal: Greedy algorithms do not always guarantee the optimal solution for every problem. They work well only for problems where the local optimum leads to a global optimum.
2. Local Perspective: Greedy algorithms make decisions based on the current situation without considering the larger context, which can sometimes lead to suboptimal solutions.
3. Irrevocable Decisions: Once a choice is made, it cannot be changed. If a mistake is made, it cannot be corrected.
4. Problem-Specific: The success of a greedy algorithm is highly dependent on the specific problem. There are many problems where greedy approaches fail to provide correct or efficient solutions.

Main Idea Behind Greedy Algorithms

The main idea behind greedy algorithms is to solve problems by making a series of choices, each of which looks the best at the moment. Greedy algorithms work by:

1. Greedy Choice Property: Making a locally optimal choice at each step with the hope that these local optimizations will lead to a globally optimal solution.
2. Optimal Substructure: Ensuring that the problem can be broken down into smaller subproblems that can be solved independently and that the optimal solution to the problem contains the optimal solutions to the subproblems.

Real-Life Example of a Greedy Algorithm

One real-life example of a greedy algorithm is the process of making change using the least number of coins. When you go to a store and the cashier gives you change, they often use a greedy algorithm to minimize the number of coins or bills they give you.

Example: Coin Change Problem

• Suppose you need to give 63 cents in change using coins of denominations 1, 5, 10, and 25 cents.
• The cashier would:
  • Start with the highest denomination (25 cents) and use as many of those as possible.
  • Move to the next highest denomination (10 cents) and use as many of those as possible.
  • Continue this process until the total amount is made up.

How to Solve Questions on a Greedy Algorithm

Understand the Problem:

• Carefully read and understand the problem statement.
• Identify if the problem has the greedy choice property and optimal substructure.

Develop a Greedy Strategy:

• Determine the criterion for the greedy choice (e.g., smallest, largest, highest ratio).
• Consider different possible choices and their immediate outcomes.

Prove Greedy Choice Property:

• Ensure that the locally optimal choices lead to a globally optimal solution.
• Prove that once a choice is made, the problem reduces to a similar subproblem.

Design the Algorithm:

• Implement the greedy strategy step-by-step.
• Make the best local choice at each step until the problem is solved.

Analyze and Test:

• Analyze the algorithm for correctness and efficiency.
• Test the algorithm on different cases, including edge cases and large inputs.

Example: Activity Selection Problem

• Problem: Given a set of activities with start and end times, select the maximum number of activities that don't overlap.
• Greedy Strategy: Select the activity that finishes the earliest and then select the next activity that starts after the current one finishes.
• Algorithm Steps:
  1. Sort the activities by their finish times.
  2. Initialize the list of selected activities with the first activity.
  3. Iterate through the remaining activities, and for each activity, if its start time is greater than or equal to the finish time of the last selected activity, add it to the list of selected activities.

Greedy algorithms are powerful for certain types of optimization problems but are not universally applicable. Here are some classes of problems that typically cannot be solved optimally using greedy algorithms:

1. Problems Lacking the Greedy Choice Property

Greedy algorithms rely on making locally optimal choices with the hope that they lead to a global optimum. If the problem doesn't exhibit the greedy choice property, greedy algorithms will not guarantee an optimal solution.

2. Problems Without Optimal Substructure

Optimal substructure means that the solution to a problem can be constructed efficiently from solutions to its subproblems. If a problem does not have this property, greedy approaches often fail.

Examples of Problems Greedy Algorithms Cannot Solve

Knapsack Problem (0/1 Knapsack)

• Problem: Given a set of items, each with a weight and value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit, and the total value is as large as possible.
• Reason: Greedy algorithms (like choosing the item with the highest value-to-weight ratio) do not always yield the optimal solution because they do not consider the cumulative weight effectively. Dynamic programming is typically used to solve this problem optimally.

Shortest Path Problem (Graphs with Negative Weights)

• Problem: Find the shortest path from a source node to a target node in a graph.
• Reason: While Dijkstra's algorithm (a greedy algorithm) works for graphs with non-negative weights, it fails when negative weights are present. Bellman-Ford algorithm, which is not greedy, is used to handle such cases.

Travelling Salesman Problem (TSP)

• Problem: Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city.
• Reason: Greedy algorithms, like nearest neighbor, do not guarantee an optimal solution. The TSP requires more complex methods like dynamic programming or heuristic algorithms to find the best solution.

Job Sequencing with Deadlines

• Problem: Given a set of jobs, each with a deadline and a profit, schedule the jobs to maximize total profit while ensuring no two jobs overlap.
• Reason: Greedy algorithms may fail to find the optimal solution because they might prioritize short-term profit over long-term gain. A more comprehensive approach, like dynamic programming or backtracking, may be needed.

Set Cover Problem

• Problem: Given a universe of elements and a collection of sets that cover the universe, find the smallest sub-collection of sets that covers all elements.
• Reason: Greedy algorithms can produce approximations but do not always yield the smallest set cover. This problem is NP-hard, and exact solutions require more sophisticated algorithms.

Reasons Why Greedy Algorithms Fail

Local vs. Global Optimum:

• Greedy algorithms make decisions based on immediate benefits, which can lead to missing the best overall solution.

Complex Dependencies:

• Problems with complex dependencies between choices often require looking ahead and considering the cumulative effect of choices, which greedy algorithms do not do.

Combinatorial Explosion:

• For problems with a large number of possible combinations, greedy choices can lead to suboptimal solutions because they do not explore enough possibilities.

Conclusion

While greedy algorithms are efficient and useful for many problems, they are not a one-size-fits-all solution. Problems lacking the greedy choice property and optimal substructure typically require more advanced methods like dynamic programming, backtracking, or exact algorithms to find the optimal solution. Understanding the nature of the problem and the properties required for a greedy solution is crucial in deciding whether a greedy approach is appropriate.