Greedy Algorithm in Data Structures

Greedy Algorithm in Data Structures: An Overview

A greedy algorithm in Data Structures is a powerful method to quickly identify an optimal solution by making the best decision at any given step and always choosing the most suitable option without reconsidering previously selected choices. This DSA tutorial delves into the distinctive features of a greedy algorithm, its operational mechanics, etc. Consider enrolling in the Data Structures Certification, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Greedy Algorithm in Data Structures?

A Greedy algorithm is a problem-solving approach that involves making decisions based solely on the information available at each step of the process. The idea behind a Greedy algorithm is to optimize each step by choosing the best option at that moment, hoping that the entire process will lead to the optimal result in the end. The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top-down approach.

While it may not always provide the best solution, it's widely referred to as one of the most intuitive and straightforward algorithms available. Overall, a Greedy algorithm can be an incredibly useful tool for problem-solving, especially when time and resources are limited.

We can determine if the algorithm can be used with any optimization problem if the problem satisfies the following two properties:

1. Greedy Choice Property

If an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps once chosen, the problem can be solved using a greedy approach.

2. Optimal Substructure

If the optimal overall solution to the problem corresponds to the optimal solution to its subproblems, then the problem can be solved using a greedy approach.

Greedy Algorithm Properties

1. Any greedy algorithm consists of a sequence of choices/ decisions (for the problem we're solving) and each choice made should be the best possible one at the moment.
2. The choice made at any point cannot be altered later.
3. The greedy algorithm may not always yield the globally optimal solution and may even result in the worst global solution (such as in the Travelling Salesman Problem).
4. Greedy algorithms are very fast compared to their alternatives, such as dynamic programming. This is because dynamic programming has to consider all possible cases locally at all times, while the greedy approach goes ahead with only one optimal choice.
5. Greedy algorithms are very intuitive, but it is very hard to prove mathematically the correctness of the algorithm.
6. The greedy algorithm may lead to a solution that is very close to the optimal solution in problems where there is no efficient solution. It is to be noted that the obtained solution in such cases is not an exact one, but rather an approximate one.

Read More - Data Structure Interview Questions for Experienced

Architecture Of The Greedy Algorithm

Input to Algorithm: Function = F, Set of Inputs = C

Output: Solution Set which maximizes or minimizes function

1. Initialize an empty solution set, S = {}
2. While (C is not empty):
    # step 1: choose an item from C
    current_choice = Select(C)
    
    # step 2: if current_choice is feasable, add to S
    if(isFeasable(current_choice)):
        S.add(C)
    
    # step 3: remove the current_choice from C
    C.remove(current_choice)
3. Return S 

Here, the Select() function makes a greedy choice from the input set C. isFeasable() function checks whether the choice made by the Select() function leads to an optimal value of F

As per the algorithm,

1. Initially, the solution set (containing answers) is empty.
2. At each step, an item is added to the solution set until a solution is reached.
3. If the solution set is feasible, the current item is kept.
4. Otherwise, the item is rejected and never considered again.

Example of Problem-Solving Using a Greedy Algorithm

Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $22

Available coins are
  $5 coin
  $2 coin
  $2 coin
There is no limit to the number of each coin you can use.

Solution:

1. Create an empty solution-set = { }. Available coins are {5, 2, 2}.
2. We are supposed to find the sum = 20. Let's start with sum = 0.
3. Always select the coin with the largest value (i.e. 5) until the sum > 20. (When we select the largest value at each step, we hope to reach the destination faster. This concept is called greedy choice property.)
4. In the first iteration, solution-set = {5} and sum = 5.
5. In the second iteration, solution-set = {5, 5} and sum = 10.
6. In the third iteration, solution-set = {5, 5, 5} and sum = 15.
7. In the fourth iteration, solution-set = {5, 5, 5, 5} and sum = 20. (We cannot select 5 here because if we do so, sum = 20 which is greater than 18. So, we select the 2nd largest item which is 2).
8. In the fifth iteration, select 2. Now sum = 22 and solution-set = {5, 5, 5, 5, 2}. (We cannot select 5 here because if we do so, sum = 25 which is greater than 20. So, we select the 2nd largest item which is 2).

Advantages of Greedy Algorithm

1. Simplicity: Greedy algorithms are usually straightforward to understand and implement. They follow a step-by-step approach where the best possible decision is made at each stage based on the current information. This simplicity makes them easier to design and analyze compared to more complex algorithms.
2. Efficiency: Greedy algorithms often have low time complexity and can run efficiently even for large input sizes. The greedy approach typically involves making local optimal choices, which can lead to faster execution times compared to exhaustive search or dynamic programming techniques.
3. Memory efficiency: Greedy algorithms often require minimal memory usage. They usually don't need to store the entire problem space or maintain an extensive set of intermediate solutions. Instead, they only need to store the current best solution and update it as they progress.

Disadvantages of Greedy Algorithm

1. Lack of global optimization: Greedy algorithms make locally optimal choices at each step without considering the overall solution. As a result, they may not always lead to the globally optimal solution. The greedy approach may overlook future consequences and make choices that seem optimal at the moment but turn out to be suboptimal in the long run.
2. Lack of backtracking: Greedy algorithms do not backtrack or reconsider decisions made earlier. Once a choice is made, it is not revisited, even if better options become available later. This can lead to suboptimal solutions or even incorrect results.
3. Dependency on problem structure: Greedy algorithms heavily rely on the problem's structure and the specific criteria used to make greedy choices. Different problem structures may require different criteria for selecting the next step, and the same greedy algorithm may not work well for all problem instances.

Types of Greedy Algorithms

• Selection Sort
• Knapsack Problem
• Minimum Spanning Tree
• Single-Source Shortest Path Problem
• Job Scheduling Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Huffman Coding
• Ford-Fulkerson Algorithm

Summary

Hence, we have covered all the concepts of greedy algorithms, their characteristics, advantages, disadvantages, types, and examples. A greedy algorithm does not always lead to the global optimal solution. All problems that can be solved using a greedy approach exhibit greedy choice and optimal substructure properties. To test your understanding of the concepts of the greedy approach, enroll in our Best Dsa Course.