Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
Module 8: Greedy Algorithm
I. 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.
II. 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
III. TOPICS AND KEY CONCEPTS
On our previous module, we discussed “Divide-and-Conquer”, which is a good
approach of simplifying the problem by breaking it into smaller problems and
solving these small problems one at a time. After these we combine the solved
problems and evaluate whether the whole problem was being solved.
As we also remembered, Divide-and-Conquer includes three steps; divide which
breaks the problem into sub-problems of same type, conquer which recursively
solve the sub-problems, and then combine which merge the solutions we made to
each sub-problem.
On this module we will first discuss the term optimization problem and the proceed
to Greedy Algorithm. For better understanding we will discuss the structure of
Greedy Algorithm and explore some applications it.
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.
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 1 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
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.
B. 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 sub-
problems.
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
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 2 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
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.
Other references consider that there are five components on a greedy algorithm;
• A candidate set, from which a solution is created
• A selection function, which chooses the best candidate to be added to the
solution
• A feasibility function, that is used to determine if a candidate can be used to
contribute to a solution
• An objective function, which assigns a value to a solution, or a partial
solution, and
• A solution function, which will indicate when we have discovered a complete
solution
C. Types of Greedy Algorithm
Greedy algorithms can be characterized as being 'short sighted', and also as 'non-
recoverable'. They are ideal only for problems which have 'optimal substructure'.
Despite this, for many simple problems, the best suited algorithms are greedy
algorithms. It is important, however, to note that the greedy algorithm can be used
as a selection algorithm to prioritize options within a search, or branch-and-bound
algorithm. There are a few variations to the greedy algorithm:
• Pure greedy algorithms
• Orthogonal greedy algorithms
• Relaxed greedy algorithms
D. Application of Greedy Algorithm
Greedy algorithms mostly (but not always) fail to find the globally optimal solution
because they usually do not operate exhaustively on all the data. They can make
commitments to certain choices too early which prevent them from finding the best
overall solution later. For example, all known greedy coloring algorithms for the
graph coloring problem and all other NP-complete problems do not consistently find
optimum solutions. Nevertheless, they are useful because they are quick to think up
and often give good approximations to the optimum.
If a greedy algorithm can be proven to yield the global optimum for a given problem
class, it typically becomes the method of choice because it is faster than other
optimization methods like dynamic programming. Examples of such greedy
algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum
spanning trees, and the algorithm for finding optimum Huffman trees.
Greedy algorithms appear in network routing as well. Using greedy routing, a
message is forwarded to the neighboring node which is "closest" to the destination.
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 3 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
The notion of a node's location (and hence "closeness") may be determined by its
physical location, as in geographic routing used by ad hoc networks. Location may
also be an entirely artificial construct as in small world routing and distributed
hash table.
Most networking algorithms use the greedy approach, here is the list of a few of
them;
• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• 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
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 4 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
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 algorithm that produces a schedule whose
completion time is as small as possible.
How to Resolve the Scheduling Problem?
Let's look at the various approaches for solving this problem which can be
considered as “greedy”;
• 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
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 5 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
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.
E. When Do We Use Greedy Algorithm?
Greedy Algorithms can 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
You can understand the explanation of the implementation of greedy algorithm
approach to the abovementioned problems by watching the attached video
materials with this module.
F. 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
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 6 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
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.
G. Video Presentations
Attached to this module are four videos that discuss Greedy Algorithm and some of
its applications;
• Greedy Method – Introduction
Link: https://www.youtube.com/watch?v=ARvQcqJ_-NY
Author: Abdul Bari
• Dijkstra's Shortest Path Algorithm
Link: https://www.youtube.com/watch?v=gdmfOwyQlcI&feature=emb_logo
Author: Nathaniel Fan
• Prims and Kruskals Algorithms - Greedy Method (Minimum Spanning
Tree)
Link: https://www.youtube.com/watch?v=4ZlRH0eK-qQ
Author: Abdul Bari
• Huffman Encoding
Link: https://www.youtube.com/watch?v=dM6us854Jk0
Author: CSBreakdown
• K Center Problem
Link: https://www.youtube.com/watch?v=dpYZojRuJEI
Author: CSBreakdown
IV. TEACHING AND LEARNING MATERIALS RESOURCE
Several teaching and learning materials are also provided aside from this module
that are in different formats;
• Module
• Video Tutorials/Presentations
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 7 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
V. LEARNING TASK
Instruction: Answer the following questions briefly, your answer
will be evaluated using the following rubric.
Holistic Rubric
Exceeding Meeting Approaching Below None
(10) (8) (6) (2) (0)
Substantial,
Content Clarity
specific, and/or
The presence of ideas Sufficient
illustrative
developed through developed Limited content Superficial
content No content
facts, examples, content with with inadequate and/or
demonstrating or answer
illustrations, details, adequate elaboration or minimal
strong provided.
opinions, statistics, elaboration or explanation content
development and
reasons, and/or explanation.
sophisticated
explanations.
ideas.
1. Given N white dots and N black dots, how would you connect them using
the least amount of wires with the implementation of Greedy Algorithm?
Assume that the wire connecting two adjacent dots is 1.
1.1. Given this;
No. of wire(s) used: ____________
1.2. Given this;
No. of wire(s) used: ____________
2. This is the given scenario, a checker board
has a number of coins on it and there is a
robot that will start on tile (0,0). The robot
can only move only two direction (L →R or
T →B) or combination of the two until it
reaches the last tile on the bottom right
side. It will collect the coins, as it finds it
on its way. After reaching the last tile of
the board, you can reset the robot to (0,0)
again to repeat the movement.
Is Greedy Algorithm applicable on this
situation? If yes what type of approach will
you used? How many movements did the
robot takes before it collects all the coins
in the board, using your approach? If no,
defend your answer.
3. Give three (3) problems that cannot be solve by the Greedy Algorithm?
Explain why did you say that this approach is impossible for the said
problems.
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 8 of 9
Republic of the Philippines
City of Olongapo
-o0o-
GORDON COLLEGE
Olongapo City Sports Complex, Donor St., East Tapinac, Olongapo City 2200
www.gordoncollege.edu.ph
Score Sheet
Question 1 Question 2 Question 3 Total Score
VI. REFERENCES
E-Books
• Cormen, Thomas, etal. Introduction to Algorithms Third Edition,
Massachusetts Institute of Technology, 2009
Online Resources:
• https://en.wikipedia.org/wiki/Greedy_algorithm
• https://www.freecodecamp.org/news/what-is-a-greedy-algorithm/
• https://www.tutorialspoint.com/data_structures_algorithms/greedy_algorit
hms.htm
• https://brilliant.org/wiki/greedy-algorithm/
• https://www.youtube.com/watch?v=ARvQcqJ_-NY
• https://www.youtube.com/watch?v=gdmfOwyQlcI
• https://www.youtube.com/watch?v=4ZlRH0eK-qQ
• https://www.youtube.com/watch?v=dpYZojRuJEI
Algorithm and Complexity I NOT FOR SALE, Exclusive for Gordon College Only!
Neil Marc R. Biron, Instructor (1st Semester, AY 2020-2021) | 9 of 9
