<p>Computing a maximum-weight basis in a matroid, which is a straight-forward generalization of Kruskal's algorithm. You may object that this is not &quot;every day life&quot;.  But well, that's pretty much the exhaustive answer to the question which problems can be solved using a greedy algorithm. :-) You can show them the proof that whenever the greedy algorithm is able to pick a set of maximum total element weight in a set system, then this set system is actually a matroid.</p>
<p>So that's as &quot;every day life&quot; as it gets...</p>

CC BY-SA 4.0
2021-05-21T13:04:01.300Z
thanks @user33593..I am waiting for some more examples. Let us C!
Free Palestine
CC BY-SA 4.0
2021-05-21T06:01:48.603Z
2021-05-21T06:01:48.603Z
user33593
<p><a href="https://en.wikipedia.org/wiki/Interval_scheduling" rel="nofollow noreferrer">Interval scheduling</a> is a quite common example, with real world applications.</p>
<p>You could also consider <a href="https://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring" rel="nofollow noreferrer">graph coloring algorithms</a>, like Welsh-Powell's or <a href="https://en.wikipedia.org/wiki/DSatur" rel="nofollow noreferrer">DSATUR</a>, since it can also illustrate that greedy algorithms are not always optimal. This example is a bit less &quot;real world-y&quot;, but it has also applications in scheduling.</p>

CC BY-SA 4.0
2021-05-21T13:11:15.663Z
2021-05-21T13:11:15.663Z
Nathaniel
<p>u may find this example about the use of Edmond Karo Max-Flow Algorithm in World-War-2 interesting
<a href="https://m.facebook.com/story.php?story_fbid=2969706433062743&amp;id=2567729029927154" rel="nofollow noreferrer">https://m.facebook.com/story.php?story_fbid=2969706433062743&amp;id=2567729029927154</a></p>
<p>.
<img src="https://i.sstatic.net/AY9V3.jpg" alt="enter image description here" />
.
&amp; I always find supermarket shopping a knapsack problem according to ur ability to carry goods!!!!
.
-If ur students r familiar with mining &amp; cryptocurrencies u may tell them that transactions get selected in a block by some sort of auction on fees they offer as bids ( a greedy approach), although it's a knapsack problem since transactions have different sizes  &amp; the block have a limited size
.
Also, in Tim Roughgarden Algorithmic Game Theory material u find TV advertisements selection of u assume fixed time interval, price depends on the type of ad.
-more important the USA spectrum auction viewed as a graph coloring problem, but maybe this is complicated for under-graduate students
.
This is the 3 colors
<img src="https://i.sstatic.net/oRFWM.jpg" alt="enter image description here" />
.
Then the heuristic to 2 colors
<img src="https://i.sstatic.net/1FGZG.jpg" alt="enter image description here" /></p>

CC BY-SA 4.0
2021-06-15T18:31:03.627Z
2021-06-15T18:31:03.627Z
ShAr
<p>One example which is actually relatively common in everyday life, especially for people who do a lot of traveling (e.g., backpackers and some business people), is the <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">knapsack problem</a>. The <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Applications" rel="nofollow noreferrer">applications</a> section gives several other fairly common situations where this problem is encountered. The Wikipedia article also lists a few methods that can be used to determine a solution, but especially for relatively simple cases, something like the <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm" rel="nofollow noreferrer">greedy approximation algorithm</a> can be implemented fairly easily, and often works relatively well.</p>
<p>Nonetheless, as that algorithm section states, a basic greedy algorithm may sometimes be far from optimal. I don't know of any examples offhand, but I suspect it should not be overly difficult to construct (or perhaps find online) a relatively simple one that would help to illustrate this point to your students.</p>

CC BY-SA 4.0
2021-05-22T00:54:54.570Z
2021-05-22T23:26:57.390Z
2021-05-22T23:26:57.390Z
John Omielan
<p>One of the popular algorithm design techniques is the Greedy Algorithm.</p>
<p>Do we have real-world examples of Greedy Algorithm which we can teach Undergraduate students?</p>
<p>I know the famous Djikstra's algorithm, Prim &amp; Kruskal, Minimum spanning trees, etc.</p>
<p>I want some examples which are very common in our day-to-day life.</p>

<undergraduate><algorithms>
Greedy Algorithm Approach
# Greedy Algorithm Approach

(Asked by: username_0 on 2021-05-21)

One of the popular algorithm design techniques is the Greedy Algorithm.

Do we have real-world examples of Greedy Algorithm which we can teach Undergraduate students?

I know the famous Djikstra's algorithm, Prim & Kruskal, Minimum spanning trees, etc.

I want some examples which are very common in our day-to-day life.

**Tags:** undergraduate, algorithms


---

## 4 answers

### Answer by username_4 on 2021-05-22. Score: 4

One example which is actually relatively common in everyday life, especially for people who do a lot of traveling (e.g., backpackers and some business people), is the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem). The [applications](https://en.wikipedia.org/wiki/Knapsack_problem#Applications) section gives several other fairly common situations where this problem is encountered. The Wikipedia article also lists a few methods that can be used to determine a solution, but especially for relatively simple cases, something like the [greedy approximation algorithm](https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm) can be implemented fairly easily, and often works relatively well.

Nonetheless, as that algorithm section states, a basic greedy algorithm may sometimes be far from optimal. I don't know of any examples offhand, but I suspect it should not be overly difficult to construct (or perhaps find online) a relatively simple one that would help to illustrate this point to your students.


---

### Answer by username_1 on 2021-05-21. Score: 2

Computing a maximum-weight basis in a matroid, which is a straight-forward generalization of Kruskal's algorithm. You may object that this is not "every day life". But well, that's pretty much the exhaustive answer to the question which problems can be solved using a greedy algorithm. :-) You can show them the proof that whenever the greedy algorithm is able to pick a set of maximum total element weight in a set system, then this set system is actually a matroid.

So that's as "every day life" as it gets...

> **Comments:**
> **username_0**: thanks @username_1..I am waiting for some more examples. Let us C!  

---

### Answer by username_2 on 2021-05-21. Score: 2

[Interval scheduling](https://en.wikipedia.org/wiki/Interval_scheduling) is a quite common example, with real world applications.

You could also consider [graph coloring algorithms](https://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring), like Welsh-Powell's or [DSATUR](https://en.wikipedia.org/wiki/DSatur), since it can also illustrate that greedy algorithms are not always optimal. This example is a bit less "real world-y", but it has also applications in scheduling.


---

### Answer by username_3 on 2021-06-15. Score: 1

u may find this example about the use of Edmond Karo Max-Flow Algorithm in World-War-2 interesting
<https://m.facebook.com/story.php?story_fbid=2969706433062743&id=2567729029927154>

.
![enter image description here](https://i.sstatic.net/AY9V3.jpg)
.
& I always find supermarket shopping a knapsack problem according to ur ability to carry goods!!!!
.
-If ur students r familiar with mining & cryptocurrencies u may tell them that transactions get selected in a block by some sort of auction on fees they offer as bids ( a greedy approach), although it's a knapsack problem since transactions have different sizes & the block have a limited size
.
Also, in Tim Roughgarden Algorithmic Game Theory material u find TV advertisements selection of u assume fixed time interval, price depends on the type of ad.
-more important the USA spectrum auction viewed as a graph coloring problem, but maybe this is complicated for under-graduate students
.
This is the 3 colors
![enter image description here](https://i.sstatic.net/oRFWM.jpg)
.
Then the heuristic to 2 colors
![enter image description here](https://i.sstatic.net/1FGZG.jpg)


---

