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
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?

Greedy algorithm is a problem-solving strategy that makes locally optimal decisions at each stage in the hopes of achieving a globally optimum solution. 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.
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

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

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