# The Greedy Algorithm, its Applications, Optimal Solutions & Cases of Failure

**The Greedy Algorithm, its Applications, Optimal Solutions & Cases of Failure**

**[What is the Greedy Algorithm?]**

The* Greedy algorithm is not necessarily one algorithm, but rather any algorithm that is used to get an Optimal Solution by taking the next most obvious and immediate benefit*. It can also be described by saying that* it takes the most optimal solution at every stage*. This is its strength that can sometimes become its weakness.

**[Application / Examples]**

The Greedy Algorithm has many applications, mostly in computations that have optimization problems, and thus need optimal solutions, for instance;

*1. Huffman Coding*

*2. Minimum Spanning Tree Problems in a Graph (Prim’s, Kruskal’s & Dijkstra’s Algorithms)*

*3. Knapsack Problem*

*4. Travelling Salesman Problem*

*5. Counting Coins Problem*

**[Optimal Solutions with the Greedy Algorithm]**

**Counting Coins Problem**

To demonstrate the use of a Greedy algorithm, take a Counting Coins Problem where;

*– there are denominations of currency coins as 7, 6, and 1 cents*

*– we need to count the number of coins that add-up to a certain value with the least possible coins*

*Optimal Solution::*

With coins of ** 7**,

**, and**

*6***cents, the greedy algorithm works by breaking (minus-ing) the largest required cents, 7 cents, then 6 cents and finally 1 cent, from “**

*1***” cents.**

*N*For instance, When ** N** is given as

**(**

*21**N = 21*), the algorithm takes the most beneficial option, 7 cents and subtracts it from 21. It does that two more times, breaking the 21 cents in only 3 steps, which is the optimal solution;

N = 21 cents Options = 7 cents, 6 cents, 1 cent 21 - (7) = 14 14 - (7) = 7 7 - (7) = 0 Total steps = 3

**[Unique Worst Possible Solution / Cases of Failure of the Greedy algorithm]**

The greedy algorithm does not always give the optimal solution. Its strength can sometimes become its weakness. We can say that the algorithm *works perfectly when all conditions for perfect computations are present, else it can be the worst algorithm for an optimal solution or rather can produce Unique Worst Possible Solutions*. To demonstrate Cases of Failure, the Counting Coins Problem is again used!

**Counting Coins Problem**

*[Case 1]*

*Unique Worst Possible Solution*::

When ** N = 18** cents, the solution is not optimal. The total steps taken to break N (using the 7 cents and 1 cent option), are more than what is actually necessary;

N = 18 cents Options = 7 cents, 6 cents, 1 cent 18 - (7) = 9 9 - (7) = 2 2 - (1) = 1 1 - (1) = 1 Total steps = 4

*Optimal Solution::*

The optimal solution here however, is using the 6 cents option to break N, 18 cents;

N = 18 cents Options = 7 cents, 6 cents, 1 cent 18 - (6) = 12 12 - (6) = 6 6 - (6) = 0 Total steps = 3

*[Case 2]*

*Unique Worst Possible Solution*::

When N = 12 cents, the solution (number of steps) is by far NOT optimal. The total steps taken to break N (using the 7 cents and one cent option), are 6 steps;

N = 12 cents Options = 7 cents, 6 cents, 1 cent 12 - (7) = 5 5 - (1) = 4 4 - (1) = 3 3 - (1) = 2 2 - (1) = 1 1 - (1) = 0 Total steps = 6

*Optimal Solution::*

The optimal solution however, is using the 6 cents option to break N, 12 cents, which results in a cost of only 2 (steps);

N = 12 cents Options = 7 cents, 6 cents, 1 cent 12 - (6) = 6 6 - (6) = 0 Total steps = 2

In this last case [Case 2],* the difference between the optimal solution and the Greedy Algorithm solution is “4” steps*. This amounts to *wastage of computational reseources/power*.

**The Greedy Algorithm, its Applications, Optimal Solutions & Cases of Failure**

**Data Structures and Algorithms | thetqweb**