International Journal of Scientific and Research Publications, Volume 3, Issue 8, August 2013 1

ISSN 2250-3153

Greedy Algorithm
Annu Malik, Anju Sharma, Mr. Vinod Saroha (Guide)

CSE(Network Security), SES BPSMV University, Khanpur Kalan, Sonepat, Haryana

Abstract- This paper presents a survey on Greedy Algorithm. options within a search, or branch and bound algorithm. There
This discussion is centered on overview of Activity Selection are a few variations to the greedy algorithm:
Problem and Task Scheduling Problem . A greedy algorithm is  Pure greedy algorithms
an algorithm that follows the problem solving heuristic of  Orthogonal greedy algorithms
making the locally optimal choice at each stage with the hope of  Relaxed greedy algorithms
finding a global optimum. In many problems, a greedy strategy
does not in general produce an optimal solution, but nonetheless
a greedy heuristic may yield locally optimal solutions that III. AN ACTIVITY SELECTION PROBLEM
approximate a global optimal solution in a reasonable
time.Greedy algorithms determine the minimum number of coins Our first example is the problem of scheduling a resource
to give while making change. These are the steps a human would among several competing activities. We shall find that the greedy
take to emulate a greedy algorithm to represent 36 cents using algorithm provides a well-designed and simple method for
only coins with values {1, 5, 10, 20}. The coin of the highest selecting a maximum-size of mutually compatible activities.
value, less than the remaining change owed, is the local Suppose S={1,2,.....,n} is the set of proposed activities. The
optimum. (Note that in general the change-making problem activities share a resource, which can be used by only one
requires dynamic programming or integer programming to find activity at a time e.g., a Tennis Court, a Lecture Hall etc. Each
an optimal solution; However, most currency systems, including activity i has a start time si and a finish time fi, where si≤ fi. If
the Euro and US Dollar, are special cases where the greedy selected, activity i takes place during the half-open time
strategy does find an optimum solution.) interval[si, fi}. Activities i and j are compatible if the intervals [sj,
fj) and [si, fi) do not overlap (i.e, I and j are compatible if s i ≥ fj
Index Terms- Greedy, scheduling, activity, optimal, algorithm or sj ≥ fj ).
etc The activity selection problem selects the maximum-size set
of mutually compatible activities.
In this strategy we first select the activity with minimum
duration (fi-si) and schedule it. Then, we skip all activities that
I. INTRODUCTION
are not compatible to this one, which means we have to select

G reedy Algorithm solves problem by making the choice that

seems best at the particular moment. Many Optimization
problems can be solved using a greedy algorithm. Some
compatible activities having minimum duration and then we have
to schedule it. This process is repeated until all the activities are
considered. It can be observed that the process of selecting the
problems have no efficient solution, but a greedy algorithm may activity becomes faster if we assume that the input activities are
provide an efficient solution that is close to optimal. A greedy in order by increasing finishing time:
algorithm works if a problem exhibit the following two
properties: f1 ≤ f2 ≤ f3 ≤ ..... ≤ fn

1) Greedy Choice Property: A globally optimal solution The running time of an algorithm GREEDY-ACTIVITY-
can be arrived at by making a locally optimal solution. SELECTOR is Ө(nlogn), as sorting can be done in О(nlogn).
In other words, an optimal solution can be obtained by There are О(1) operations per activity, thus total time is
making “greedy” choices.
2) Optimal Substructure: Optimal solutions contains О(nlogn) + n.О(1) = О(nlogn)
optimal sub solutions. In other words, solutions to sub
problems of an optimal solution are optimal. The pseudo code of GREEDY-ACTIVITY-SELECTOR is
as follows:

II. TYPES OF GREEDY ALGORITHM GREEDY-ACTIVITY-SELECTOR(s, f)

Greedy algorithms can be characterized as being 'short [1] n ← length[s]
sighted', and as 'non-recoverable'. They are ideal only for [2] A ← {1}
problems which have 'optimal substructure'. Despite this, greedy [3] j ← 1
algorithms are best suited for simple problems (e.g. giving [4] for I ← 2 to n
change). It is important, however, to note that the greedy [5] do if si ≥ fj
algorithm can be used as a selection algorithm to prioritize [6] then A ← a Union {1}
[7] j ← i

www.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 8, August 2013 2
ISSN 2250-3153

[8] return A Si = (1, 2, 3, 4, 7, 8, 9, 9, 11, 12)

Fi = (3, 5, 4, 7, 10, 9, 11, 13, 12, 14)
The GREEDY-ACTIVITY-SELECTOR algorithm gives an
optimal solution to the activity selection problem. Compute a schedule where the largest number of activities
takes place.
Example. Given 10 activities along with their start and Solution. The solution for the above activity scheduling
finish time as problem using greedy strategy is illustrated below.
S = (A1, A2, A3, A4, A5, A6, A7, A8, A9, A10) Arranging the activities in increasing order of finish time.

Activity A1 A2 A3 A4 A5 A6 A7 A8 A9 A10
Start 1 3 2 4 8 7 9 11 9 12
Finish 3 4 5 7 9 10 11 12 13 14

www.ijsrp.org
 International Journal of Scientific and Research Publications, Volume 3, Issue 8, August 2013 3
ISSN 2250-3153

A10

A8

A9

A7

A
C A5
T
I
V
I A6
T
Y
A4

A2

A3

A1

1 2 3 4 5 6 7 8 9 10 11 12 13 14

TIME

www.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 8, August 2013 4
ISSN 2250-3153

Next schedule A3 , as A1and A3 are non-interferimg.Next ,

schedule A4 as A1, A3 and A4 are non-interfering, then next, Here we find a schedule for S that minimizes the total
schedule A6 as A1, A3, A4 and A6 and are not interfering. penalty incurred for missed dead lines.
Skip A5 as it is interfering. A task is late in this schedule if it is finished after its dead
Next, schedule A7 as A1, A3, A4 , A6 and A7 are non- line. Otherwise, the task is early in the schedule. An arbitrary
interfering. schedule can always be put into early-first form, in which the
Next, schedule A9 as A1, A3, A4 , A6, A7 and A9 are non- early tasks precede the late tasks, i.e., if some early task x
interfering. follows some late task y, then we can switch the positions of x
Skip A8, as it is interfering. and y without effecting x being early or y being late.
Next, schedule A10 as A1, A3, A4 , A6, A7, A9 and A10 are non- An arbitrary schedule can always be put into canonical
interfering. form, in which the early tasks precede the late tasks and the early
Thus, the final activity schedule is tasks are scheduled in order of non-decreasing dead lines.
(A1, A3, A4 , A6, A7, A9, A10) The search for an optimal schedule reduces to finding a set
A of tasks that are to be early in the optimal schedule. Once A
determined, we can create the actual schedule by listing the
IV. ACTIVITY OR TASK SCHEDULING PROBLEM elements of A in order of non-decreasing dead line, then listing
This is the problem of optimally scheduling unit-time tasks the late tasks(i.e., S-A) in any order, producing a canonical
on a single processor, where each task has a dead line and a ordering of the optimal schedule.
penalty that must be paid if the dead line is missed.
A unit time task is a job such as a program to be run on a A set A of the tasks is independent if there exists a schedule
computer that requires exactly one unit of time to complete. for these tasks such that no tasks are late. So, the set of early
Given a finite set S of unit-time tasks, a schedule for S is a tasks for a schedule forms an independent set of tasks 'l' denote
permutation of S specifying the order in which these tasks are to the set of all independent sets of tasks.
be performed. The first task in the schedule begins at time 0 and
finishes at time 1, the second task begins at time 1 and finishes at For any set of tasks A, A is independent if for t = 0, 1, 2, …,
time 2 and so on. n we have
The problem of scheduling unit time tasks with dead lines Nt (A) ≤ t
and penalties for a single processor has the following inputs: where Nt(A) denote the number of tasks in A whose dead
line is t or earlier , i.e., if the tasks in A are scheduled in order of
monotonically increasing dead lines, then no task is late.
 a set S = {1, 2, 3, …..., n} of n-unit-time tasks.
Example. Let n = 4(P1, P2, P3, P4) = (100, 10, 15, 27) and
 A set of n integer dead lines d1, d2, d3, …..dn such that
(d1, d2, d3, d4) = (2, 1, 2, 1)
di satisfies 1 ≤ di ≤ n and task I is supposed to finish by
where Pi are profits on processes or job and di are dead line
time di and
of completion. Find the optimal schedule.
 a set of n non-negative weights or penalties w1, w2, w3, Solution. Max. dead line is 2 so max. number of processes
…..., wn such that a penalty wi, is incurred if task I is not that are scheduled is 2.
finished by time di and no penalty is incurred if a task i
is not finished by time di and no penalty is incurred if a
task finishes by its dead lines.

Feasible Solution Processing Sequence Value

(1, 2) (2, 1) 10 + 100 = 110
(1, 3) (1, 3) or (3, 1) 100 + 15 = 115
(1, 4) (4, 1) 27 + 100 = 127
(2, 3) (2, 3) 25
(3, 4) (4, 3) 42
(1) 1 100
(2) 2 10
(3) 3 15
(4) 4 27

Thus, the optimal schedule is (4, 1) and profit 127.

www.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 8, August 2013 5
ISSN 2250-3153

V. APPLICATIONS but the hidden part may backfire on you when you least expect.
Greedy algorithms mostly (but not always) fail to find the While there are some standardized problems, most of the
globally optimal solution, because they usually do not operate problems solvable by this method call for heuristics. There is no
exhaustively on all the data. They can make commitments to general template on how to apply the greedy method to a given
certain choices too early which prevent them from finding the problem, however the problem specification might give you a
best overall solution later. For example, all known greedy good insight. In some cases there are a lot of greedy assumptions
coloring algorithms for the graph coloring problem and all other one can make, but only few of them are correct. They can
NP-complete problems do not consistently find optimum provide excellent challenge opportunities.
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 REFERENCES
optimum for a given problem class, it typically becomes the [1] Wikipedia
method of choice because it is faster than other optimization [2] Google
methods like dynamic programming. Examples of such greedy [3] Algorithms Design and Analysis by Udit Agarwal
algorithms are Kruskal's algorithm and Prim's algorithm for
finding minimum spanning trees, Dijkstra's algorithm for finding
single-source shortest paths, and the algorithm for finding AUTHORS
optimum Huffman trees.
First Author – Annu Malik, M.Tech (Persuing), CSE(Network
Security), SES BPSMV Uniersity, Khanpur Kalan, Sonepat,
Haryana and annu1990malik@gmailcom.
VI. CONCLUSION Second Author – Anju Sharma, M.Tech (Persuing),
Greedy algorithms are usually easy to think of, easy to CSE(Network Security), SES BPSMV Uniersity, Khanpur
implement and run fast. Proving their correctness may require Kalan, Sonepat, Haryana and anjusharma264@gmailcom.
rigorous mathematical proofs and is sometimes insidious hard. In Third Author – Mr. Vinod Saroha (Guide), M.Tech(Assistant
addition, greedy algorithms are infamous for being tricky. Professor in CSE and IT Department), SES BPSMV Uniersity,
Missing even a very small detail can be fatal. But when you have Khanpur Kalan, Sonepat, Haryana) and vnd.saroha@gmailcom.
nothing else at your disposal, they may be the only salvation.
With backtracking or dynamic programming you are on a Correspondence Author – Annu Malik,
relatively safe ground. With greedy instead, it is more like annu1990malik@gmail.com, sbit.cse08408@gmail.com),
walking on a mined field. Everything looks fine on the surface, 08813034437.

www.ijsrp.org