Greedy Algorithms

  • Last Updated : 26 Sep, 2023

DSA for Beginners
Learn more about Greedy Algorithms in DSA Self Paced Course
Practice Problems on Greedy Algorithms
Top Quizzes on Greedy Algorithms

What is Greedy Algorithm?

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are the best fit for Greedy.

For example consider the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item.

greedy-algorithms
Topics:

Introduction:

  1. Introduction to Greedy Algorithm – Data Structures and Algorithm Tutorials
  2. Greedy Algorithms (General Structure and Applications)
  3. Difference between Greedy Algorithm and Divide and Conquer Algorithm
  4. Greedy approach vs Dynamic programming
  5. Comparison among Greedy, Divide and Conquer and Dynamic Programming algorithm

Standard Greedy Algorithms:

  1. Activity Selection Problem
  2. Job Sequencing Problem
  3. Huffman Coding
  4. Huffman Decoding
  5. Water Connection Problem
  6. Minimum Swaps for Bracket Balancing
  7. Egyptian Fraction
  8. Policemen catch thieves
  9. Fitting Shelves Problem
  10. Assign Mice to Holes

Greedy Problems on Array:

  1. Minimum product subset of an array
  2. Maximize array sum after K negations using Sorting
  3. Minimum sum of product of two arrays
  4. Minimum sum of absolute difference of pairs of two arrays
  5. Minimum increment/decrement to make array non-Increasing
  6. Sorting array with reverse around middle
  7. Sum of Areas of Rectangles possible for an array
  8. Largest lexicographic array with at-most K consecutive swaps
  9. Partition into two subarrays of lengths k and (N – k) such that the difference of sums is maximum

Greedy Problems on Operating System:

  1. First Fit algorithm in Memory Management
  2. Best Fit algorithm in Memory Management
  3. Worst Fit algorithm in Memory Management
  4. Shortest Job First Scheduling
  5. Job Scheduling with two jobs allowed at a time
  6. Program for Optimal Page Replacement Algorithm

Greedy Problems on Graph:

  1. Kruskal’s Minimum Spanning Tree
  2. Prim’s Minimum Spanning Tree
  3. Boruvka’s Minimum Spanning Tree
  4. Dijkastra’s Shortest Path Algorithm
  5. Dial’s Algorithm
  6. Minimum cost to connect all cities
  7. Max Flow Problem Introduction
  8. Number of single cycle components in an undirected graph

Approximate Greedy Algorithm for NP Complete:

  1. Set cover problem
  2. Bin Packing Problem
  3. Graph Coloring
  4. K-centers problem
  5. Shortest superstring problem
  6. Approximate solution for Travelling Salesman Problem using MST

Greedy for Special cases of DP:

  1. Fractional Knapsack Problem
  2. Minimum number of coins required

Some practice problems on Greedy:

Quick Links :

  1. Learn Data Structure and Algorithms | DSA Tutorial
  2. Top 20 Greedy Algorithms Interview Questions
  3. ‘Practice Problems’ on Greedy Algorithms
  4. ‘Quiz’ on Greedy Algorithms

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.