M G E A D H

O L R E T I
R Y G

G Y
L
G R E E D Y
A L G O R I T H M
Module 8 Greedy
Algorithm
 INTRODUCTION
There is another technique that can be used in algorithmic design techniques, and that is what
we called “Greedy Algorithm”. In this module, the students will get familiar with the definition,
structure, and application of Greedy Algorithm. Examples on how Greedy Algorithm is also
included for better understanding.
LEARNING OBJECTIVES
After completing this module, the student should be able to;

• Define Greedy Algorithm

• Understand optimization problem
• Determine the structure of Greedy Algorithm
• Know and understand how Greedy Algorithm Works
• Know some of the Application of Greedy Algorithm
What is a Greedy Algorithm?
● A greedy algorithm is a simple, intuitive algorithm that is used in optimization
problems. The algorithm makes the optimal choice at each step as it attempts
to find the overall optimal way to solve the entire problem. Greedy algorithms
are quite successful in some problems, such as Huffman encoding which is
used to compress data, or Dijkstra's algorithm, which is used to find the
shortest path through a graph.

● However, in many problems, a greedy strategy does not produce an optimal

solution. For example, in the given problem below, the greedy algorithm seeks
to find the path with the largest sum. It does this by selecting the largest
available number at each step. The greedy algorithm fails to find the largest
sum, however, because it makes decisions based only on the information it
has at any one step, without regard to the overall problem.
The illustration demonstrates the nature of Greedy
Algorithm, we begin on the top node and from
there it will select the node with a higher value
(since it is greedy), thus it will proceed to node 12.
From node 12 there are two options, node 5 and
node 6, since node 6 is the larger than 5 the
greedy algorithm will select it. After the selection
the greedy algorithm will ends with the following
nodes whose values are 7, 12, and 6. Summing up
these values we will get 25 which is wrong as
compared to the correct solution, because the
actual largest sum or path is 109. You can get 109
in selecting 7 then 3 and then 99.
 Structure of Greedy
Algorithm
● Greedy algorithms take all of the data in a particular problem, and then set a
rule for which elements to add to the solution at each step of the algorithm. In
the illustration above, the set of data is all of the numbers in the graph, and
the rule was to select the largest number available at each level of the graph.
The solution that the algorithm builds is the sum of all of those choices.

If both of the properties below are true, a greedy algorithm can be used to solve the
problem.

• Greedy choice property: A global (overall) optimal solution can be reached by

choosing the optimal choice at each step.
• Optimal substructure: A problem has an optimal substructure if an optimal solution to
the entire problem contains the optimal solutions to the subproblems.

In other words, greedy algorithms work on problems for which it is true that, at every step,
there is a choice that is optimal for the problem up to that step, and
after the last step, the algorithm produces the optimal
solution of the complete problem. To make a greedy
algorithm, identify an optimal substructure or
subproblem in the problem. Then, determine what the
solution will include (for example, the largest sum, the
shortest path, etc.). Create some sort of iterative way to
go through all of the subproblems and build a solution.
Types of Greedy Algorithm

• Pure greedy algorithms

• Orthogonal greedy algorithms
• Relaxed greedy algorithms
 Application of Greedy
Algorithm
Key Insights:
• Greedy algorithms may not always find the global optimum:
• They do not explore all possible options.
• They may commit too early to suboptimal choices.
• Especially unreliable for:
• Graph coloring and other NP-complete problems.

When Greedy Works Well:

• If it can be proven to yield an optimal solution:
• It's faster than dynamic programming.
• Becomes the preferred method.
Common Effective Greedy Algorithms:
• Kruskal’s Algorithm – Minimum Spanning Tree
• Prim’s Algorithm – Minimum Spanning Tree
• Huffman Encoding – Optimal prefix codes
• Dijkstra’s Algorithm – Shortest path in weighted graphs

Network Routing Example:

• Greedy Routing: Message is sent to the nearest neighbor to the
destination.
• Based on physical/geographic location
• Or virtual structures (e.g., distributed hash tables, small-
world routing)

Other Problems Using Greedy:

• Travelling Salesman (approximation)
• Graph – Map Coloring
• Graph – Vertex Cover
• Knapsack Problem
• Job Scheduling Problem
 Scheduling Problem
Let us consider this kind of problem and apply the
“greedy algorithm” approach to solve it. This is an
interesting problem that you can encounter in almost any
industry or any walk of life. Some instances of the
problem are as follows:
You are given a set of N schedules of lectures for a single day at a university. The
schedule for a specific lecture is of the form (s time, f time) where s time
represents the start time for that lecture and similarly the f time represents the
finishing time. Given a list of N lecture schedules, we need to select maximum set
of lectures to be held out during the day such that none of the lectures overlap
with one another i.e. if lecture Li and Lj are included in our selection then the start
time of j >= finish time of i or vice versa .

• Your friend is working as a camp counselor, and he is in charge of organizing

activities for a set of campers. One of his plans is the following mini-triathlon
exercise: each contestant must swim 20 laps of a pool, then bike 10 miles, then
run 3 miles.
• The plan is to send the contestants out in a staggered fashion, via the
following rule: the contestants must use the pool one at a time. In other
words, first one contestant swims the 20 laps, gets out, and starts
biking.

• As soon as this first person is out of the pool, a second contestant

begins swimming the 20 laps; as soon as he or she is out and starts
biking, a third contestant begins swimming, and so on.
• Each contestant has a projected swimming time, a projected biking
time, and a projected running time. Your friend wants to decide on a
schedule for the triathlon: an order in which to sequence the starts of
the contestants.

• Let's say that the completion time of a schedule is the earliest time at
which all contestants will be finished with all three legs of the triathlon,
assuming the time projections are accurate. What is the best order for
sending people out, if one wants the whole competition to be over as soon as
possible? More precisely, give an efficient
 How to Resolve the
Scheduling Problem?
Earliest Start Time First i.e. select the interval that has the
earliest start time. Take a look at the following example that
breaks this solution. This solution failed because there could be
an interval that starts very early but that is very long. This
means the next strategy that we could try would be where we
look at smaller intervals first.
Smallest Interval First i.e. you end up selecting the lectures in order
of their overall interval which is nothing but their finish time - start
time . Again, this solution is not correct. Look at the following case;

You can clearly see that the shortest interval lecture is the one in the
middle, but that is not the optimal solution here. Let's look at yet
another solution for this problem deriving insights from this solution.
Least Conflicting Interval First i.e. you should look at intervals that
cause the least number of conflicts. Yet again we have an example
where this approach fails to find an optimal solution.

The diagram shows us that the least confliciting interval is the one in
the middle with just 2 conflicts. After that we can only pick the two
intervals at the very ends with conflicts 3 each. But the optimal solution
is to pick the 4 intervals on the topmost level.
Earliest Finishing time first. This is the approach that always
gives us the most optimal solution to this problem. We derived
a lot of insights from previous approaches and finally came
upon this approach. We sort the intervals according to
increasing order of their finishing times and then we start
selecting intervals from the very beginning. Look at the
following pseudo code for more clarity.
 When Do We Use Greedy
Greedy Algorithms canAlgorithm?
help you find solutions to a lot of seemingly
tough problems. The only problem with them is that you might come up
with the correct solution but you might not be able to verify if its the
correct one. All the greedy problems share a common property that a
local optima can eventually lead to a global minima without
reconsidering the set of choices already considered.

Greedy Algorithms help us solve a lot of different kinds of problems,

like:

• Shortest Path Problem

• Minimum Spanning Tree Problem in a Graph
• Huffman Encoding Problem
• K Centers Problem
 Limitations of Greedy
Algorithm
Sometimes greedy algorithms fail to find the globally optimal solution because
they do not consider all the data. The choice made by a greedy algorithm may
depend on choices it has made so far, but it is not aware of future choices it could
make.
The correct solution for the longest path through the graph is 7, 3, 1,
99. This is clear to us because we can see that no other combination of
nodes will come close to a sum of 99, so whatever path we choose, we
know it should have 99 in the path. There is only one option that
includes 99: 7, 3, 1, 99.

The greedy algorithm fails to solve this problem because it makes

decisions purely based on what the best answer at the time is: at each
step it did choose the largest number. However, since there could be
some huge number that the algorithm hasn't seen yet, it could end up
selecting a path that does not include the huge number. The solutions
to the subproblems for finding the largest sum or longest path do not
necessarily appear in the solution to the total problem. The optimal
substructure and greedy choice properties don't hold in this type of
problem.
THANK YOU