Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 48

Understanding the Difference Between Array and Linked List

Lesson - 49

The Best Article Out There to Understand the B+ Tree in Data Structure

Lesson - 50

A Comprehensive Look at Queue in Data Structure

Lesson - 51

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 52

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 53

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 54

The Best Tutorial You'll Ever Need for Queue Implementation Using Linked List

Lesson - 55
The Definitive Guide to Understanding Greedy Algorithm

Do you know, during Huffman data compression, greedy algorithm is utilized to build a Huffman tree that compresses a given image, spreadsheet, or video into a lossless compressed file? Also, this greedy coding paradigm encapsulates algorithmic problems where selecting the most obvious answer for the current subproblem leads to the solution of a more complex problem. So, in this article, we will discover a greedy algorithmic paradigm in detail.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

What Is Greedy Algorithm?

A Greedy algorithm is an approach to solving a problem that selects the most appropriate option based on the current situation. This algorithm ignores the fact that the current best result may not bring about the overall optimal result. Even if the initial decision was incorrect, the algorithm never reverses it.

This simple, intuitive algorithm can be applied to solve any optimization problem which requires the maximum or minimum optimum result. The best thing about this algorithm is that it is easy to understand and implement.

The runtime complexity associated with a greedy solution is pretty reasonable. However, you can implement a greedy solution only if the problem statement follows two properties mentioned below: 

  • Greedy Choice Property: Choosing the best option at each phase can lead to a global (overall) optimal solution.
  • Optimal Substructure: If an optimal solution to the complete problem contains the optimal solutions to the subproblems, the problem has an optimal substructure.

Moving forward, we will learn how to create a greedy solution for a problem that adheres to the principles listed above.

Steps for Creating a Greedy Algorithm

By following the steps given below, you will be able to formulate a greedy solution for the given problem statement:

  • Step 1: In a given problem, find the best substructure or subproblem.
  • Step 2: Determine what the solution will include (e.g., largest sum, shortest path).
  • Step 3: Create an iterative process for going over all subproblems and creating an optimum solution.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Let’s take up a real-world problem and formulate a greedy solution for it. 

Problem: Alex is a very busy person. He has set aside time T to accomplish some interesting tasks. He wants to do as many tasks as possible in this allotted time T. For that, he has created an array A of timestamps to complete a list of items on his itinerary. 

Now, here we need to figure out how many things Alex can complete in the T time he has.

Approach to Build a Solution: This given problem is a straightforward greedy problem. In each iteration, we will have to pick the items from array A that will take the least amount of time to accomplish a task while keeping two variables in mind: current_Time and number_Of_Things. To generate a solution, we will have to carry out the following steps.

  • Sort the array A in ascending order.
  • Select one timestamp at a time.
  • After picking up the timestamp, add the timestamp value to current_Time.
  • Increase number_Of_Things by one.
  • Repeat steps 2 to 4 until the current_Time value reaches T.

Example of Greedy Algorithm

Problem Statement:  Find the best route to reach the destination city from the given starting point using a greedy method.

Thumbnail_Greedy_Problem

Greedy Solution: In order to tackle this problem, we need to maintain a graph structure. And for that graph structure, we'll have to create a tree structure, which will serve as the answer to this problem. The steps to generate this solution are given below:

  • Start from the source vertex.
  • Pick one vertex at a time with a minimum edge weight (distance) from the source vertex.
  • Add the selected vertex to a tree structure if the connecting edge does not form a cycle.
  • Keep adding adjacent fringe vertices to the tree until you reach the destination vertex.

The animation given below explains how paths will be picked up in order to reach the destination city.

Source_to_Destination_Greedy_Algorithm_Solution.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Limitations of Greedy Algorithm

Factors listed below are the limitations of a greedy algorithm:

  1. The greedy algorithm makes judgments based on the information at each iteration without considering the broader problem; hence it does not produce the best answer for every problem.
  2. The problematic part for a greedy algorithm is analyzing its accuracy. Even with the proper solution, it is difficult to demonstrate why it is accurate. 
  3. Optimization problems (Dijkstra’s Algorithm) with negative graph edges cannot be solved using a greedy algorithm.

Moving forward, let’s look at some applications of a greedy algorithm.

Applications of Greedy Algorithm

Following are few applications of the greedy algorithm:

  • Used for Constructing Minimum Spanning Trees: Prim’s and Kruskal’s Algorithms used to construct minimum spanning trees are greedy algorithms.
  • Used to Implement Huffman Encoding: A greedy algorithm is utilized to build a Huffman tree that compresses a given image, spreadsheet, or video into a lossless compressed file.
  • Used to Solve Optimization Problems: Graph - Map Coloring, Graph - Vertex Cover, Knapsack Problem, Job Scheduling Problem, and activity selection problem are classic optimization problems solved using a greedy algorithmic paradigm.

Characteristics of a Greedy Method

The greedy method is a simple and straightforward way to solve optimization problems. It involves making the locally optimal choice at each stage with the hope of finding the global optimum. The main advantage of the greedy method is that it is easy to implement and understand. However, it is not always guaranteed to find the best solution and can be quite slow.

The greedy method works by making the locally optimal choice at each stage in the hope of finding the global optimum. This can be done by either minimizing or maximizing the objective function at each step. The main advantage of the greedy method is that it is relatively easy to implement and understand. However, there are some disadvantages to using this method. First, the greedy method is not guaranteed to find the best solution. Second, it can be quite slow. Finally, it is often difficult to prove that the greedy method will indeed find the global optimum.

One of the most famous examples of the greedy method is the knapsack problem. In this problem, we are given a set of items, each with a weight and a value. We want to find the subset of items that maximizes the value while minimizing the weight. The greedy method would simply take the item with the highest value at each step. However, this might not be the best solution. For example, consider the following set of items:

Item 1: Weight = 2, Value = 6

Item 2: Weight = 2, Value = 3

Item 3: Weight = 4, Value = 5

The greedy method would take Item 1 and Item 3, for a total value of 11. However, the optimal solution would be to take Item 2 and Item 3, for a total value of 8. Thus, the greedy method does not always find the best solution.

There are many other examples of the greedy method. The most famous one is probably the Huffman coding algorithm, which is used to compress data. In this algorithm, we are given a set of symbols, each with a weight. We want to find the subset of symbols that minimizes the average length of the code. The greedy method would simply take the symbol with the lowest weight at each step. However, this might not be the best solution. For example, consider the following set of symbols:

Symbol 1: Weight = 2, Code = 00

Symbol 2: Weight = 3, Code = 010

Symbol 3: Weight = 4, Code =011

The greedy method would take Symbol 1 and Symbol 3, for a total weight of 6. However, the optimal solution would be to take Symbol 2 and Symbol 3, for a total weight of 7. Thus, the greedy method does not always find the best solution.

The greedy method is a simple and straightforward way to solve optimization problems. However, it is not always guaranteed to find the best solution and can be quite slow. When using the greedy method, it is important to keep these disadvantages in mind.

Components of a Greedy Algorithm

There are four key components to any greedy algorithm:

  1. A set of candidate solutions (typically represented as a graph)
  2. A way of ranking the candidates according to some criteria
  3. A selection function that picks the best candidate from the set, according to the ranking
  4. A way of "pruning" the set of candidates, so that it doesn't contain any solutions that are worse than the one already chosen.

The first two components are straightforward - the candidate solutions can be anything, and the ranking criteria can be anything as well. The selection function is usually just a matter of picking the candidate with the highest ranking.

The pruning step is important, because it ensures that the algorithm doesn't waste time considering candidates that are already known to be worse than the best one found so far. Without this step, the algorithm would essentially be doing a brute-force search of the entire solution space, which would be very inefficient.

Full Stack Java Developer Course

In Partnership with HIRIST and HackerEarthEXPLORE COURSE
Full Stack Java Developer Course

Pseudo Code of Greedy Algorithms

One example of pseudo code for a greedy algorithm is given below:

function GreedyAlgorithm(problem) {

// currentState = initial state of problem while (currentState != goalState) { nextState = chooseNextState(currentState); currentState = nextState; } return currentState; }

The above pseudo code shows the basic structure of a greedy algorithm. The first step is to set the current state to the initial state of the problem. Next, we keep looping until the current state is equal to the goal state. Inside the loop, we choose the next state that we want to move to. This is done by using a function called chooseNextState(). Finally, we set the current state to be equal to the next state that we have just chosen and return to the goal state.

The pseudo code for the chooseNextState() function is given below:

function chooseNextState(currentState) { // find all possible next states nextStates = findAllPossibleNextStates(currentState); // choose the next state that is closest to the goal state bestState = null; for (state in nextStates) { if (isCloserToGoal(state, bestState)) { bestState = state; } } return bestState; }

The pseudo code for the chooseNextState() function shows how we can choose the next state that is closest to the goal state. First, we find all of the possible next states that we could move to from the current state. Next, we loop through all of the possible next states and compare each one to see if it is closer to the goal state than the best state that we have found so far. If it is, then we set the best state to be equal to the new state. Finally, we return the best state that we have found.

The above pseudo code shows how a greedy algorithm works in general. However, it is important to note that not all problems can be solved using a greedy algorithm. In some cases, it may be necessary to use a different type of algorithm altogether.

Disadvantages of Using Greedy Algorithms

The main disadvantage of using a greedy algorithm is that it may not find the optimal solution to a problem. In other words, it may not produce the best possible outcome. Additionally, greedy algorithms can be very sensitive to changes in input data — even a small change can cause the algorithm to produce a completely different result. Finally, greedy algorithms can be difficult to implement and understand.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Conclusion

In this greedy algorithm article, you learned what a greedy programming paradigm is and discovered properties and steps to build a greedy solution. The article also discusses applications and mentions the limitations of greedy algorithm. You also saw an example of this algorithm which will help grasp the concept.  If you want a quick and easy way to understand the greedy algorithmic paradigm, we advise you to watch this video: https://youtu.be/ilYwrsP7zzk.

Every day, new products, tools, and apps are being introduced and launched into the market. And there are hundreds of programming languages and frameworks being utilized every day in the realm of software development. Hence, it is crucial for you to go beyond data structure concepts and cover the foundations of interactive application development. Simplilearn's Software Development Courses provide the right platform for you to master the art of software development. The courses in this catalog can help you improve your odds of becoming a software developer. So, go ahead and start exploring!

If you have any queries concerning this article on Greedy Algorithm, please leave them in the comments box at the bottom of this page; we will revert with the answers at the earliest.

About the Author

Amber ButchAmber Butch

Amber Butch is the founder of OneVisibility and has been working as a freelance writer and digital marketer since 2005. As a seasoned digital marketer, she stands behind the fact that content is king when it comes to increasing brand awareness and loyalty.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.