Unit-III

Greedy Method
• Greedy algorithm obtains an optimal solution by
making a sequence of decisions.

• Decisions are made one by one in some order.

• Each decision is made using a greedy-choice

property or greedy criterion.

• A decision, once made, is (usually) not changed

later.
• It gives an optimal solution when applied to
problems with the greedy-choice property.

• A feasible solution is a solution that

satisfies the constraints.

• An optimal solution is a feasible solution

that optimizes the objective function.
Greedy method control abstraction/ general
method
Algorithm Greedy(a,n)
// a[1:n] contains the n inputs
{
solution= //Initialize solution
for i=1 to n do
{
x:=Select(a);
if Feasible(solution,x) then
solution=Union(solution,x)
}
return solution;
}
Example: Largest k-out-of-n Sum
• Problem
– Pick k numbers out of n numbers such that the
sum of these k numbers is the largest.
• Exhaustive solution
– There are C n choices.
k
– Choose the one with subset sum being the
largest
• Greedy Solution Is the greedy solution always optimal
For i = 1 to k
pick out the largest
number and
delete this number from
the input.
ENDFOR
Example:
Shortest Path on a Special Graph
• Problem
– Find a shortest path from v0 to v3

• Greedy Solution
Example:
Shortest Paths on a Special Graph

• Problem
– Find a shortest path from v0 to v3
Is the solution optimal?
• Greedy Solution
Example:
Shortest Paths on a Multi-stage Graph
Is the greedy solution optimal?
• Problem
– Find a shortest path from v0 to v3
Example:
Shortest Paths on a Multi-stage Graph


Is the greedy solution optimal?
• Problem
– Find a shortest path from v0 to v3

The
Theoptimal
optimalpath
path
Example:
Shortest Paths on a Multi-stage Graph

Is the greedy solution optimal?

m??
e optimuum
• Problem m can bbee uusseedd ttoo ffiinndd tthhe optim 
Whhaatt aallggoorriitthhm can
W – Find a shortest path from v0 to v3

The
Theoptimal
optimalpath
path
The Fractional Knapsack
Problem
• Given: A set S of n items, with each item i having
– pi - a positive profit
– wi - a positive weight
• Goal: Choose items, allowing fractional amounts(xi),
to maximize total profit but with weight at most
m.
maximize ∑ pix i
1≤i≤n
subjected to ∑ wixi ≤ m
1≤i≤n
and 0 ≤ xi ≤ 1, 1≤i≤n
The Fractional Knapsack Problem
Greedy decision property:-
Select items in decreasing order of profit/weight.

“knapsack”

Solution:
Items: 1 ml of i5
1 2 3 4 5
•
wi : 4 ml 8 ml 2 ml 6 ml 1 ml • 2 ml of i3
• 6 ml of i4
pi : $12 $32 $40 $30 $50
• 1 ml of i2
10 ml
Value: 3 4 20 5 50
($ per ml)
• Solution vector
(x1,x2,x3,x4,x5)= (0,1/8,1,1,1)
• Profit =12*0 + 32*1/8 + 40*1 + 30*1 + 50*1
= 0+4+40+30+50
=124.
Greedy algorithm for the fractional Knapsack problem
Algorithm GreedyKnapsack(m,n)
//P[1:n] and w[1:n] contain the profits and weights
// respectively of the n objects ordered such that
//p[i]/w[i]>=p[i+1]/w[i+1].
//m is the knapsack size and x[1:n] is the solution
// Vector.
{
for i := 1 to n do x[i] := 0; // Initialize x.
U := m;
for i :=1 to n do
{
if ( w[i] > U ) then break;

x[i] := 1; U := U-w[i];
}
if ( i <= n) then x[i] := U/w[i];
}
If you do not consider the time to sort the items, then the time taken by the
above algorithm is O(n).
0/1 Knapsack Problem
• An item is either included or not included
into the knapsack.
Formally the problem can be stated as

maximize ∑ pixi
1≤i≤n
subjected to ∑ wixi ≤ m
1≤i≤n
and xi=0 or 1, 1 ≤ i ≤ n
Which items should be chosen
to maximize the amount of
money while still keeping the
overall weight under m kg ?

m
na l k na pssaacckkaalgoorritithhm
lg m
f r a c
IIsstthhee fractionati o l k na p
aappppliliccaabbllee??
• The greedy method works for fractional knapsack problem,
but it does not for 0/1 knapsack problem.
• Ex:-

30
item3 $120

item2
20
item1 $100

30 20 $100
20 $60
10 10

$60 $100 $120 Knapsack =$160 =$220

Capacity 50 gms

(a) (b)
• There are 3 items, the knapsack can hold 50 gms.

• The value per gram of item 1 is 6, which is greater

than the value per gram of either item2 or item3.

• The greedy approach ( Decreasing order of

profit’s/weight’s), does not give an optimal solution.

• As we can see from the above fig (b), the optimal

solution takes item2 and item3.
Spanning Tree

• A tree is a connected undirected

graph that contains no cycles.

• A spanning tree of a graph G is a

subgraph of G that is a tree and
contains all the vertices of G.
Properties of a Spanning Tree
• The spanning tree of a n-vertex undirected
graph has exactly n – 1 edges.

• It connects all the vertices in the graph.

• A spanning tree has no cycles.

Ex:-

1 1
A B A B A B
5 2
4 2 4 4
6

D C D C D C
3 3 3

1 1

Undirected Graph A B A B
2 2
4

D C D C
3

…
Some Spanning Trees
Minimum Cost Spanning Tree / Minimum
Spanning Tree (MST)

• A minimum spanning tree is the one among all the

spanning trees with the smallest total cost.

1 1
A B A B
4
4 2 2
5

D C D C
3 3

Undirected Graph Minimum Spanning Tree

Applications of MSTs

• Computer Networks
– To find how to connect a set of
computers using the minimum amount of
wire.
MST-Prim’s Algorithm
• Start with minimum cost edge.
• Select next minimum cost edge (i,j) such that
i is a vertex already included in the tree, j is
a vertex not yet included.
• Continue this process until the tree has n - 1
edges.
Prim’s Algorithm
t [1:n-1,1:2]
8 7
2 3 4 1 2
1 9
2 1 1 2
1 11 9i 4 14 5 2 2 3
7 16
8 10
8 7 6 3 9
4 2
. 3 6
. 6 7
2 3 4 .
7 8
1 9 5 3 4
n-1 4 5
8 7 6
Pseudo code algorithm of Prim’s method
1. It starts with the min cost edge.
2. The next edge ( i, j ) to be added is such that i is
a vertex already in the tree and j is a vertex not
yet included, and the cost[i, j] is minimum.
3. To determine this edge efficiently, we associate
with each vertex j not yet included in the tree a
value near[j].
4. The value near[ j ] is a vertex in the tree such that
cost[ j, near[j] ] is minimum among all choices
for near[ j ].
Note: We define near[ j ] = 0 for all vertices j that are
already in the tree.
L
2 3
1 j cost[ j, near[j] ]
K
1 3 near[3]=2 cost[ 3,2 ]=8

4 near[4]=1 cost[ 4,1 ]= ∞

1 near[1]=0 cost[ 5,1 ]= ∞
5 near[5]=1
2 near[2]=0 cost[ 6,1 ]= ∞
near[6]=1
6
3 near[3]=0
7 near[7]=1 cost[ 7,1 ]= ∞

near[8]=1 cost[ 8,1 ]=8

8
near[9]=1 cost[ 9,1 ]= ∞
9

2. Select next min cost edge.

3. Next update near[j] for all vertices which are not yet included in the tree and
then go to step 2.
4. Continue this procedure until tree contains n-1 edges.
Prim’s Algorithm

1 Algorithm Prim(E, cost, n, t)

2 // E is the set of edges in G.
3 //cost[1:n,1:n] is the cost matrix such that cost[i,j] is either
4 // positive real number or ∞ if no edge (i,j) exists. cost[i,j]=0, if i=j.
5 // A minimum spanning tree is computed and stored
6 // as a set of edges in the array t[1:n-1,1:2]
7 {
8 Let (k,l) be an edge of minimum cost in E

9 mincost=cost[k,l];
10 t[1,1]=k; t[1,2]=l;
11 near[k]=near[l]=0;

12 for i=1 to n do // initialize near

13 if( near[i] ≠0 ) then
14 if( cost[i,k]< cost[i, l] then near[i]=k;
else near[i]= l;
14 for i=2 to n-1 do
15 {
16 // Find n-2 additional edges for t.

17 Let j be an index such that near[j]≠0 and

18 cost[j,near[j]] is minimum;

19 t[i,1]=j; t[i,2]=near[j];
20 mincost=mincost+cost[j,near[j]];
21 near[j]=0;

22 for k=1 to n do // update near[]

23 if( ( near[k] ≠0 ) and (cost[k,near[k]>cost[k,j])) then
24 near[k]=j;
25 }
26 return mincost;
27 }
Time complexity of Prims algorithm
• Line 8 takes o(E).
• The for loop of line 12 takes o(n).
• 17 and 18 and the for loop of line 22 require o(n)
time.
• Each iteration of the for loop of line 14 takes o(n)
time.
• Therefore, the total time for the for loop of line
14 is o(n2).
• Hence, time complexity of Prim is o(n2).
Kruskal’s Method

• Start with a forest that has no edges.

• Add the next minimum cost edge to the
forest if it will not cause a cycle.
• Continue this process until the tree has n - 1
edges.
Kruskal’s Algorithm
8 7
2 3 4
1 9
2
1 11 9 4 14 5


8

7 16
10
8 7 2
6
4

2 3 4

1 9 5

8 7 6
9
4
5 5
3 8
4 9
3 6 8 6
2

1 2 2 4 4 7 7 8 8 9 14 16
10

1
9 7 7 3

3 8 2 1
Does not form cycle 4 6
6
7
3 4
2

9 5
1

8 7 6

Forms cycle
Disjoint Sets

 Two sets A and B are said to be disjoint if there

are no common elements i.e., A  B =  .
 Example:
1) S1={1,7,8,9}, S2={2,5,10}, and S3={3,4,6}.
are three disjoint sets.
• We identify a set by choosing a representative element
of the set. It doesn’t matter which element we choose,
but once chosen, it can’t be changed.

• Disjoint set operations:

– FIND-SET(x): Returns the representative of the set
containing x.

– UNION(i,j): Combines the two sets i and j into one new

set. A new representative is selected.
( Here i and j are the representatives of the sets )
Disjoint Sets Example
• Make-Set(1)
• Make-Set(2) 1 2
• Make-Set(3 )
3
• Make-Set(4)
4
• Union(1,2)
• Union(3,4)
• Find-Set(2) returns 1
• Find-Set(4) returns 3
• Union(1,3)
MST-Kruskal’s Algorithm
Algorithm kruskal(E,cost,n,t)
// E is the set of edges in G.
//cost[1:n,1:n] is the cost matrix such that cost[i,j] is either
// positive real number or ∞ if no edge (i,j) exists. cost[i,j]=0, if i=j.
// A minimum spanning tree is computed and stored
// as a set of edges in the array t[1:n-1,1:2].
{
for i:=1 to n do
Make-Set( i ); // each vertex is in a different set.
Sort the edges of E into increasing order by cost.
mincost:=0; i:=1;
for each edge (u,v) € E, taken in increasing order by cost do
{ j:= Find-Set(u); k:= Find-Set(v)
if( j≠k ) then
{
t[i,1]:=u; t[i,2]:=v;
mincost:=mincost+cost[u,v];
Union(j,k);
i:=i+1;
}
return mincost;
}
Time complexity of kruskal’s
algorithm

• With an efficient Find-set and union algorithms,

the running time of kruskal’s algorithm will be
dominated by the time needed for sorting the edge
costs of a given graph.
• Hence, with an efficient sorting algorithm( merge
sort ), the complexity of kruskal’s algorithm is
o( ElogE).
The Single-Source Shortest path
Problem ( SSSP)
• Given a positively weighted directed graph G with a
source vertex v, find the shortest paths from v to all
other vertices in the graph.
Ex :-

v V1 V2 V5
V1V3
V1V3V4
V1V3V4V2
V1V5
V3 V4 V6 5) V1V3V4V6 28
45 45

50
2
10
5
50
2
 10 5
1 1
15 15 
10 35 35

20 20 30 20 10 20 30

15 3 15 3
3 4 6 3 4 6
  
Iteration S Dist[2 Dist[3] Dist[4] Dist[5] Dist[6]
]
Initial {1} 50 10  ∞ 45 ∞
1 { 1,3 } 50 10 25
 45 ∞

2 { 1,3,4 } 45 10 25  45 28

3 { 1,3,4,6 } 45 10 25 45 28
 
4 { 1,3,4,5,6 } 45 10 25 45 28
 
SSSP-Dijkstra’s algorithm
• Dijkstra’s algorithm assumes that cost(e)0 for each e in the
graph.
• Maintains a set S of vertices whose Shortest Path from v ( source)
has been determined.
• a) Select the next minimum distance node u, which is not in S.
• b) for each node w adjacent to u do
if( dist[w]>dist[u]+cost[u,w]) ) then
dist[w]:=dist[u]+cost[u,w];

• Repeat step (a) and (b) until S=n (number of vertices).

1 Algorithm ShortestPaths(v,cost,dist,n)
2 //dist[j], 1≤ j≤ n, is the length of the shortest path
3 //from vertex v to vertex j in a digraph G with n vertices.
4 // dist[v] is set to zero. G is represented by its cost adjacency
5 // matrix cost[1:n, 1;n].
6{
7 for i:= 1 to n do
8 { // Initialize S.
9 s[i]:=false; dist[i]:=cost[v,i];
10 }
11 s[v]:=true; // put v in S.
12 for num:=2 to n do
13 {
14 Determine n-1 paths from v.
15 Choose u from among those vertices not in S such that
dist[u] is minimum;

17 s[u]:=true; // Put u in S.
18 for ( each w adjacent to u with s[w]= false) do
19 // Uupdate distance
20 if( dist[w]>dist[u]+cost[u,w]) ) then
21 dist[w]:=dist[u]+cost[u,w];
22 }
23 }
Time complexity of Dijkstra’s Algorithm
• The for loop of line 7 takes o(n).
• The for loop of line 12 takes o(n).
– Each execution of this loop requires o(n) time at lines
15 and 18.
– So the total time for this loop is o(n2).
• Therefore, total time taken by this algorithm is o(n2).
Job sequencing with deadlines
 We are given a set of n jobs.
 Deadline di>=0 and a profit pi>0 are associated with each job i.
 For any job profit is earned if and only if the job is completed by
its deadline.
 To complete a job, a job has to be processed by a machine for one
unit of time.
 Only one machine is available for processing jobs.
 A feasible solution of this problem is a subset of jobs such that
each job in this subset can be completed by its deadline
 The optimal solution is a feasible solution which will maximize
the total profit.
 The objective is to find an order of processing of jobs which will
maximize the total profit.
Ex:-n=4, ( p1,p2,p3,p4 )= ( 100,10,15,27 )
( d1,d2,d3,d4 )= ( 2,1,2,1 )
day1 day2 day3 day4 day5

0 1 2 3 4 5

time
Ex:-n=4, ( p1,p2,p3,p4 )=( 100,10,15,27 )
( d1,d2,d3,d4 )=( 2,1,2,1 )
The maximum deadline is 2 units, hence the feasible solution set
must have <=2 jobs.
feasible processing
solution sequence value

1. (1,2) 2,1 110

2. (1,3) 1,3 or 3,1 115
3. (1,4) 4,1 127
4. (2,3) 2,3 25
5. (3,4) 4,3 42
6. (1) 1 100
7. (2) 2 10
8. (3) 3 15
9. (4) 4 27

Solution 3 is optimal.
Greedy Algorithm for job sequencing with
deadlines
1. Sort pi into decreasing order. After sorting
p1  p2  p3  …  pi.
2. Add the next job i to the solution set if i can be
completed by its deadline.
3. Stop if all jobs are examined. Otherwise, go to step 2.
Ex:- 1) n=5, ( p1,…….,p5) = ( 20,15,10,5,1 ) and
( d1,…….d5) = ( 2,2,1,3,3 )
The optimal solution is {p1,p2,p4} with a profit of
40.

Ex:- 2) n=7, ( p1,…….,p7) = ( 3,5,20,18,1,6,30 ) and

( d1,……..d7) = ( 1,3,4,3,2,1,2 )
Find out an optimal solution.
The optimal solution is { p6, p7, p4, p3) with a profit of 74
Algorithm JS(d,j,n)
//d[i]≥1, 1 ≤ i ≤ n are the deadlines.
//The jobs are ordered such that p[1] ≥p[2] …… ≥p[n]
// j[i] is the ith job in the optimal solution, 1≤ i ≤ k
{
d[0]=j[0]=0; // Initialize
j[1]=1; // Include job 1
k=1;
for i=2 to n do
{ //Consider jobs in Descending order of p[i].
// Find position for i and check feasibility of
// insertion.
r=k;
while( ( d[ j[r] ] > d[ i ] ) and ( d[ j[ r ] ] > r ) ) do
r = r-1;

if( d[ i ] > r )) then

{
// Insert i into j[ ].
for q=k to (r+1) step -1 do j[q+1] = j[q];

j[r+1] :=i;
k:=k+1;
}
}
return k;

}
Worst -case time taken by this algorithm is o(n2)
Time complexity analysis
• The while loop is iterated at most k times.
• If the conditional statement if is true, then the
inside for loop will be iterated k-r times.
• Therefore, while loop and inside for loop time
complexity is O(k).
• Hence, the total time for each iteration of outer
for loop is O(k). This loop is iterated n-1 times.
• If s is the final value of k, that is , s is the number
of jobs in the final solution, then the total time
needed by algorithm is O(sn). Since s <= n, the
worst – case time complexity of this algorithm is
O(n2).