Chapter Three

Greedy Algorithm
 outline
 Greedy Algorithm

• Activity selection problem

• Job sequencing with deadlines

• Optimal merge pattern,

• Minimum spanning trees

• Single source shortest pattern.

 Greedy Algorithm
Many real-world problems are optimization problems in that they
attempt to find an optimal solution among many possible candidate
solutions.

• Suppose that a problem can be solved by a sequence of decisions.

• The greedy method has that each decision is locally optimal. These
locally optimal solutions will finally add up to a globally optimal
solution.

• Only a few optimization problems can be solved by the greedy method

 Being greedy for local optimization with the hope it will lead to a global
optimal solution, not always, but in many situations, it works.
 CONT…
• The choice that seems best at the moment is the one we go with.

Prove that when there is a choice to make, one of the optimal

choices is the greedy choice. Therefore, it’s always safe to make
the greedy choice.
Show that all but one of the sub problems resulting from the
greedy choice are empty.
 Greedy Algorithm
• Example: the purchase is worth 5.24 sent , how many coins and what
coins does a cash register return after paying a 6 birr bill?
 To make change for the amount x = 0.66 (cent).
 Compare x with each coin, if it is less than the coin leave it .
• Use q = x/50 = 1 -> (one 50 cent)
 The remainder x = 66 – 50q = 16,
• d = x/10 = 1 -> (one 10 cent)
Note: The above algorithm is
 The remainder x = 16 – 10d = 6,
optimal in that it uses the
• n = x/5 = 1 -> (one 5 cent)
 The remainder x = 6 – 5n = 1, fewest number of coins among
• p = x/1 = 1 -> (one 1 cent) all possible ways to make
 The total number of coins used = q + dchange
+ n + pfor
= 4.
a given amount
 Elements of Greedy strategy
Determine the optimal substructure

Develop the recursive solution

Prove one of the optimal choices is the greedy choice yet safe

Show that all but one of sub-problems are empty after greedy choice

Develop a recursive algorithm that implements the greedy strategy

Convert the recursive algorithm to an iterative one.

 Greedy Algorithm
Merge(A, p, q, r)
• A Generic Greedy Algorithm:
(1)Initialize C to be the set of candidate solutions
(2)Initialize a set S = the empty set  (the set is to be the optimal
solution we are constructing).
(3) While C   and S is (still) not a solution do
(3.1) select x from set C using a greedy strategy
(3.2) delete x from C
(3.3) if {x}  S is a feasible solution, then S = S  {x} (i.e., add x to
set S)(4) if S is a solution then return S
(5) else return failure
 Shortest paths on a special graph
• Problem: Find a shortest path from v0 to v3.
• The greedy method can solve this problem.
• The shortest path: 1 + 2 + 4 = 7.
 Activity selection problem
• Problem: n activities, S = {a1, a2, …, an},

• each activity ai has a start time si and

• A finish time fi, so si  fi. i.e. 0 si< fi<.

• Activity ai occupies time interval [si, fi].

• ai and aj are compatible if si  fj or sj  fi. do not overlap

• The problem is to select a maximum-size set of mutually compatible

activities
 Activity selection problem
• Input: Set S of n activities, a1, a2, …, an.
– si = start time of activity i.
– fi = finish time of activity i.
• Output: Subset A of maximum number of compatible
activities.
– Two activities are compatible, if their intervals don’t
overlap.

Example: Activities in each line

are compatible.
 Optimal substructure
• Assume activities are sorted by finishing times.

• f1  f2  …  fn.

• Suppose an optimal solution includes activity ak.

This generates two sub-problems.

Selecting from a1, …, ak-1, activities compatible with one another,

and that finish before ak starts (compatible with ak).

Selecting from ak+1, …, an, activities compatible with one

another, and that start after ak finishes.

The solutions to the two sub-problems must be optimal.

 Activity selection problem
Algorithm for selection problem:
Step 1: Sort fi into non-decreasing order. After sorting, f1  f2  f3  …
 fn.
Step 2: Add the next activity i to the solution set if i is compatible with
each in the solution set.
Step 3: Stop if all activities are examined. Otherwise, go to step 2.
Example:

i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 8 9 10 11 12 13 14
 The solution set = {1, 4, 8, 11}
 Time complexity: O(nlogn)
 Activity selection problem
 Solution of the example:
i si fi accept
1 1 4 Yes
2 3 5 No
3 0 6 No
4 5 7 Yes
5 3 8 No
7 6 10 No
8 8 11 Yes
9 8 12 No
10 2 13 No
11 12 14 Yes
 Solution = {1, 4, 8, 11}
 Job sequencing with deadline
• Given n jobs. Associated with job I is an integer deadline Di≧0.

• For any job I the profit Pi is earned; iff the job is completed by its
deadline.

• To complete a job, one has to process the job on a machine for one unit
of time.

• A feasible solution is a subset J of jobs such that each job in the subset
can be completed by its deadline.

• We want to maximize the

 iJ
Pi
 Job sequencing with deadline
Algorithm of job sequence with deadlines:

Step 1: Sort pi into non-increasing order. After sorting p1  p2  p3  …

 pn.

Step 2: Add the next job ai to the solution set if ai can be completed by
its deadline. Assign i to time slot [r-1, r], where r is the largest integer
such that 1  r  di and [r-1, r] is free.

Step 3: Stop if all jobs are examined. Otherwise, go to step 2.

Time complexity: O(n2)

 Job sequencing with deadline
 Problem: n jobs, S={a1, a2, …, n}, each job ai has a deadline di  0
and a profit pi  0.
 We need one unit of time to process each job and we can do at most
one job each time.
 We can earn the profit pi if job ai is completed by its deadline.

i 1 2 3 4 5
pi 20 15 10 5 1
di 2 2 1 3 3

 The optimal solution ={1, 2, 4}.

 The total profit = 20 + 15 + 5 = 40.
 Job sequencing with deadline
e.g.
i pi di
1 20 2 assign to [1, 2]
2 15 2 assign to [0, 1]
3 10 1 reject
4 5 3 assign to [2, 3]
5 1 3 reject

solution = {1, 2, 4}
total profit = 20 + 15 + 5 = 40
 The 2-way merging problem
# of comparisons required for the linear 2-way merge algorithm is m1+

m2 -1 where m1 and m2 are the lengths of the two sorted lists

respectively.
2-way merging example

 2 3 5 6
 1 4 7 8

The problem: There are n sorted lists, each of length mi. What is the
optimal sequence of merging process to merge these n lists into one
sorted list ?
 The 2-way merging problem
 An extended binary tree representing a 2-way
merge
 The 2-way merging problem
An example of 2-way merging

 Example: 6 sorted lists with lengths 2, 3, 5, 7, 11 and 13.

2 3 5 7 11 13
The 2-way merging problem

 Time complexity for

generating an optimal
extended binary tree: O(n log
n)
 Using min-heap
 The 2-way merging problem
Binary Merge Trees: We can depict the merge patterns using a binary tree, built
from the leaf nodes (the initial lists) towards the root in which each merge of
two nodes creates a parent node whose size is the sum of the sizes of the two
children. For example, the two previous merge patterns are depicted in the
following two figures:

Cost = 30*2 + 20*2 + 10*1

Cost = 30*1 +
60 60 20*2 + 10*2 =
= 110 90

50 10 30 30

30 20 20 10

Merge L1 and L2, then with L3 Merge L2 and L3, then with
merge cost = sum of all weightedL1
external path lengths
 Huffman codes
• Suppose we wish to save a text (ASCII) file on the disk or to transmit
it through a network using an encoding scheme that minimizes the
number of bits required.

• Without compression, characters are typically encoded by their ASCII

codes with 8 bits per character. We can do better if we have the
freedom to design our own encoding.

• Example:

• E-mail ,telegram , fax……

 Huffman code Algorithm
• HUFFMAN (C)
n =|C|
Q = |C|
for i = 1 to n-1
allocate a new node z
z.left = X = EXTRACT-MIN (Q)
z.right = y=EXTRACT-MIN (Q)
z.freq = x.freq + y.freq
INSERT (Q,Z)
return EXTRACT-MIN (Q) // return the root of the tree
 Example Huffman codes
• In telecommunication, how do we represent a set of messages, each
with an access frequency, by a sequence of 0’s and 1’s?

• To minimize the transmission and decoding costs, we may use short

strings to represent more frequently used messages.

• This problem can be solved by using an extended binary tree which is

used in the 2-way merging problem.
 The 2-way merging problem
An example of Huffman algorithm

• Symbols: A, B, C, D, E, F, G
freq. : 2, 3, 5, 8, 13, 15, 18
• Huffman codes:
A: 10100 B: 10101 C: 1011
D: 100 E: 00 F: 01
G: 11

A Huffman code Tree

 Graph
• Greedy Strategies Applied to Graph problems:
 A graph consists of vertices (nodes) and edges (arcs, links), in which each
edge “connects” two vertices (not necessarily distinct). More formally,
 a graph G = (V, E), where V and E denote the sets of vertices and edges,
respectively.
 A graph categorized in to two based on order
1. Directed graph 2. Undirected graph
 A graph categorized in to two based on their structure
1. Cyclic graph
2. Acyclic graph
 A graph categorized in to two based on their cost\weight
1. Weighted graph
2. Unweight graph
 Example Graphs

1 2 1 2 1 2

3 4 3 4 3 4
A directed graph B undirected graph C Cyclic graph

1 2 1 3
2
5
1 2
3 4 3 6
4 3 4
D Acyclic graph E weighted graph F unweight graph
 Graphs (review)
Definition. A directed graph (digraph)
G = (V, E) is an ordered pair consisting of
• a set V of vertices (singular: vertex),
• a set E ⊆ V × V of edges.
Definition. an undirected graph G = (V, E),
the edge set E consists of unordered pairs of
vertices.
 In either case, we have | E | = O(V 2).Moreover,
if G is connected, then | E | ≥ | V | – 1, which
implies that log | E | = Θ(log V).
 Minimum Spanning Trees

• Given: Connected, undirected, weighted graph, G = (V,

E)
• Find: Minimum - weight spanning tree, T
• Example: 5 b 7 c
Acyclic subset of edges(E) that
a
3
1 -3 connects all vertices of G.
11
d e f
0 2 b c
5

a 1
3 -3

d e f
0
 Minimum Spanning Trees
 Given a weighted (undirected) graph G = (V, E), where each edge e
has a positive weight w(e).
 A spanning tree of G is a tree (connected graph without cycles, or
circuits) which has V as its vertex set,
 i.e., the tree connects all vertices of the graph G. If |V| = n, then the
tree has n – 1 edges (this is a fact which can be proved by induction).
 A minimum spanning tree of G is a spanning tree that has the
minimum total edge weight. In MST weighted must be p+?
1 1 A minimum spanning
3 6 3 6
8 tree (of 4 edges),
2 3 2 3
5 weight = 3 + 2 + 4 + 6
4 4
7
5 4 5 4
2 2 = 15.
 A weighted graph of no parallel edges or self-loops
 Prim’s algorithm for finding MST
 Input A connected, undirected graph G = (V, E)
 with weight function w : E → R.
Step 1: x  V, Let A = {x}, B = V - {x}.
Step 2: Select (u, v)  E, u  A, v  B such that (u,
v) has the smallest weight between A and B.
Step 3: Put (u, v) in the tree. A = A  {v}, B = B - {v}
Step 4: If B = , stop; otherwise, go to Step 2.

 Time complexity : O(n2), n = |V|.

 Output: A spanning tree T — a tree that connects all
of minimum weight:
vertices
w(T ) = ∑ w(u, v) .
(u,v)∈T
 Prim’s Algorithm

QQ:=
:=V[G];
V[G];
for eachuuQQdo
foreach do Complexity:
key[u]
key[u]:= := Using binary heaps: O(E lg
do;
do; V).
key[r]
key[r]:=
:=0;0;
[r] := NIL;
Initialization – O(V).
[r] := NIL;
Building initial queue –
whileQQ
while dodo
uu:=
:=Extract
Extract--Min(Q);
Min(Q); O(V).
for eachvvAdj[u]
foreach Adj[u]dodo V Extract-Min’s – O(V
ififvvQQw(u,
w(u,v)
v)<<key[v]
key[v]then
then lgV).
[v]
[v]:=
:=u;u; E Decrease-Key’s –
key[v] := w(u, v)
key[v] := w(u, v)
ifif O(E lg operation
 decrease-key V).
do
do
do
do Using Fibonacci heaps:
= O(E + V lg V).
Note: A = {(v, [v]) : v  v - {r} - Q}.
 Prim’s MST Algorithm
Example .
Step Next edge selected Partial tree
1
3 Initially
6 1
8
2 3 3 1
5 4 1 (1,5), weight=3
7 5
5
4
2 1
2 (5,4), weight=2
5 4
A weighted graph 2
1
3 (4,2), weight=4 5 2
4
4
1
6
5 2
4 (1,3), weight=6 3
4
Example Prim’s Algorithm

6 12
5 9

14 7
8 15

3 10
Kruskal’s algorithm for finding MST
 Input: A connected, undirected graph G = (V, E)
 with weight function w : E
Step→ R. all edges into non-decreasing order.
1: Sort
Step 2: Add the next smallest weight edge to the forest if it will
not cause a cycle.
Step 3: Stop if n-1 edges. Otherwise, go to Step2.

• Time complexity : O(n2), n = |V|.

 Output: A spanning tree T — a tree that connects

all vertices — of minimum weight:

w(T ) = ∑
w(u, v) .
(u,v)∈T
An example of Kruskal’s algorithm
 Single source shortest path problem
 Given a directed graph, and a single node called the source.

 For each of the remaining nodes, find a shortest path connected from the source
(assuming the direction of the edges along the paths are respected).

• A Greedy algorithm due to Dijkstra which finds these shortest paths in

sequence can be described as follows:

1. find the shortest among all shortest paths (from the source), then find the
second shortest, etc.,

2. breaking ties arbitrarily, until all shortest paths are found. During the process,
the collection of all the shortest paths determined so far form a tree;

3. the next shortest path is selected by finding a node that is one edge away from
the current tree and has the shortest distance measured from the source.
 Single source shortest path problem

• shortest paths from v0 to all destinations

 Dijkstra’s algorithm:
Input: W[1..n][1..n] with W[i, j] = weight of edge (i, j); set W[i, j] =  if no edge
Output: an array D[2..n] of distances of shortest paths to each node in [2..n]
Algorithm:
(1) C = {2,3,…,n} // the set of remaining nodes
(2) for i = 2 to n do D[i] = W[1,i] // initialize distance from node 1 to node i
(3) repeat the following n – 2 times // determine the shortest distances
(3.1) select node v of set C that has the minimum value in array D
(3.2) C = C – {v} // delete node v from set C
(3.3) for each node w in C do
if (D[v] + W[v, w] < D[w]) then
D[w] = D[v] + W[v, w] // update D[w] if found shorter path to w

The algorithm’s time

complexity is O(n2) because
Steps (1) and (2) each take 1
O(n) time; Step (3) runs in D[w]
O(n) iterations in which each D[v] w

iteration runs in O(n) time. Tree of v W[v,w]

shortest paths
Example (Dijkstra’s shortest paths
algorithm):
Remaining nodes
and the distances
1 step tree of shortest paths from the source
10 50

5 30 2 Initially 1 C = [ 2, 3, 4, 5]
100
20 D = [50,30,100,10]
10 5 Choose 1 [ 2, 3, 4] Changed
4 3
50
node 5 5 [50,30, 20] from 100

A weighted directed 1 Changed

Choose [ 2, 3]
graph, source node = 1 5 from 50
node 4 [40,30]
4
Shortest paths: 1
To Path Distance Choose [ 2] [35] Changed
5 3 from 40
node 3
4 1 2
5 (1,5) 10
Choose 
4 (1,5,4) 20 5 3
node 2 4
3 (1,3) 30
2 (1,3,2) 35
 Dijkstra’s algorithm

Cost adjacency matrix.

All entries not shown
are +.
1 2 3 4 5 6 7 8
1 0
2 300 0

3 1000 800 0
4 1200 0
5 1500 0 250
6 1000 0 900 1400
7 0 1000
8 1700 0 4 -42
 Vertex
Iteration S Selected (1) (2) (3) (4) (5) (6) (7) (8)
Initial ----
1 5 6 + + + 1500 0 250 + +
2 5,6 7 + + + 1250 0 250 1150 1650
3 5,6,7 4 + + + 1250 0 250 1150 1650
4 5,6,7,4 8 + + 2450 1250 0 250 1150 1650
5 5,6,7,4,8 3 3350 + 2450 1250 0 250 1150 1650
6 5,6,7,4,8,3 2 3350 3250 2450 1250 0 250 1150 1650
5,6,7,4,8,3,2 3350 3250 2450 1250 0 250 1150 1650

4 -43
• Time complexity : O(n ) 2