3
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
4
$\begingroup$

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. The 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 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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks @user33593..I am waiting for some more examples. Let us C! $\endgroup$
    – Goku
    May 21, 2021 at 13:04
2
$\begingroup$

Interval scheduling is a quite common example, with real world applications.

You could also consider graph coloring algorithms, like Welsh-Powell's or 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.

Improve this answer
$\endgroup$
1
$\begingroup$

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 . & 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 . Then the heuristic to 2 colors enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.