Greedy Algorithms Notes | EduRev

: Greedy Algorithms Notes | EduRev

 Page 1


Greed
"Greed is good. Greed is right. Greed 
works. Greed cuts through, clarifies, 
and captures the essence of the 
evolutionary spirit."
Gordon Gecko
(Michael Douglas)
2
Greedy Algorithms
Some possibly familiar examples:
¦ Gale-Shapley stable matching algorithm.
¦ Dijkstra’s shortest path algorithm.
¦ Prim and Kruskal MST algorithms.
¦ Huffman codes.
¦ .   .   .
3
Selecting Breakpoints
Minimizing breakpoints.
¦ Truck driver going from Princeton to Palo Alto along 
predetermined route.
¦ Refueling stations at certain points along the way.
¦ Truck fuel capacity = C.
Greedy algorithm.
¦ Go as far as you can before refueling.
Princeton Palo Alto
1
C
C
2
C
3
C
4
C
5
C
6
C
7
4
Sort breakpoints by increasing value:
0 = b
0
< b
1
< b
2
< ... < b
n
.
S ‹ {0}
x = 0
while (x „ b
n
)
let p be largest integer such that b
p
£ x + C
if (b
p
= x)
return "no solution"
x ‹ b
p
S ‹ S ¨ {p}
return S
Greedy Breakpoint Selection Algorithm
Selecting Breakpoints:  Greedy Algorithm
S = breakpoints selected.
Page 2


Greed
"Greed is good. Greed is right. Greed 
works. Greed cuts through, clarifies, 
and captures the essence of the 
evolutionary spirit."
Gordon Gecko
(Michael Douglas)
2
Greedy Algorithms
Some possibly familiar examples:
¦ Gale-Shapley stable matching algorithm.
¦ Dijkstra’s shortest path algorithm.
¦ Prim and Kruskal MST algorithms.
¦ Huffman codes.
¦ .   .   .
3
Selecting Breakpoints
Minimizing breakpoints.
¦ Truck driver going from Princeton to Palo Alto along 
predetermined route.
¦ Refueling stations at certain points along the way.
¦ Truck fuel capacity = C.
Greedy algorithm.
¦ Go as far as you can before refueling.
Princeton Palo Alto
1
C
C
2
C
3
C
4
C
5
C
6
C
7
4
Sort breakpoints by increasing value:
0 = b
0
< b
1
< b
2
< ... < b
n
.
S ‹ {0}
x = 0
while (x „ b
n
)
let p be largest integer such that b
p
£ x + C
if (b
p
= x)
return "no solution"
x ‹ b
p
S ‹ S ¨ {p}
return S
Greedy Breakpoint Selection Algorithm
Selecting Breakpoints:  Greedy Algorithm
S = breakpoints selected.
5
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
=g
r
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
r = 4
Greedy:
OPT:
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
g
r
f
r
6
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
Greedy:
OPT:
5
5
5
r = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
r = 4
7
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
¦ Thus,  f
0
= g
0
, f
1
= g
1 
, . . . , f
q
= g
q 
1 2 3 4
1 2 3 4 6 7
Greedy:
OPT:
5
5
r = q = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
q
f
q
g
p
8
Activity Selection
Activity selection problem (CLR 17.1).
¦ Job requests 1, 2, … , n.
¦ Job j starts at s
j
and finishes at f
j
.
¦ Two jobs compatible if they don't overlap.
¦ Goal: find maximum subset of mutually compatible jobs.
Time
0
A
C
F
B
D
G
E
123456789 10 11
H
Page 3


Greed
"Greed is good. Greed is right. Greed 
works. Greed cuts through, clarifies, 
and captures the essence of the 
evolutionary spirit."
Gordon Gecko
(Michael Douglas)
2
Greedy Algorithms
Some possibly familiar examples:
¦ Gale-Shapley stable matching algorithm.
¦ Dijkstra’s shortest path algorithm.
¦ Prim and Kruskal MST algorithms.
¦ Huffman codes.
¦ .   .   .
3
Selecting Breakpoints
Minimizing breakpoints.
¦ Truck driver going from Princeton to Palo Alto along 
predetermined route.
¦ Refueling stations at certain points along the way.
¦ Truck fuel capacity = C.
Greedy algorithm.
¦ Go as far as you can before refueling.
Princeton Palo Alto
1
C
C
2
C
3
C
4
C
5
C
6
C
7
4
Sort breakpoints by increasing value:
0 = b
0
< b
1
< b
2
< ... < b
n
.
S ‹ {0}
x = 0
while (x „ b
n
)
let p be largest integer such that b
p
£ x + C
if (b
p
= x)
return "no solution"
x ‹ b
p
S ‹ S ¨ {p}
return S
Greedy Breakpoint Selection Algorithm
Selecting Breakpoints:  Greedy Algorithm
S = breakpoints selected.
5
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
=g
r
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
r = 4
Greedy:
OPT:
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
g
r
f
r
6
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
Greedy:
OPT:
5
5
5
r = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
r = 4
7
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
¦ Thus,  f
0
= g
0
, f
1
= g
1 
, . . . , f
q
= g
q 
1 2 3 4
1 2 3 4 6 7
Greedy:
OPT:
5
5
r = q = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
q
f
q
g
p
8
Activity Selection
Activity selection problem (CLR 17.1).
¦ Job requests 1, 2, … , n.
¦ Job j starts at s
j
and finishes at f
j
.
¦ Two jobs compatible if they don't overlap.
¦ Goal: find maximum subset of mutually compatible jobs.
Time
0
A
C
F
B
D
G
E
123456789 10 11
H
9
Activity Selection:  Greedy Algorithm
Sort jobs by increasing finish times so that
f
1
£ f
2
£ ... £ f
n
.
S = f for j = 1 to n
if (job j compatible with A)
S ‹ S ¨ {j}
return S  
Greedy Activity Selection Algorithm
S = jobs selected.
10
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
11
11
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8 11
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
Replace 11 with 9
12
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
Replace 11 with 9
Page 4


Greed
"Greed is good. Greed is right. Greed 
works. Greed cuts through, clarifies, 
and captures the essence of the 
evolutionary spirit."
Gordon Gecko
(Michael Douglas)
2
Greedy Algorithms
Some possibly familiar examples:
¦ Gale-Shapley stable matching algorithm.
¦ Dijkstra’s shortest path algorithm.
¦ Prim and Kruskal MST algorithms.
¦ Huffman codes.
¦ .   .   .
3
Selecting Breakpoints
Minimizing breakpoints.
¦ Truck driver going from Princeton to Palo Alto along 
predetermined route.
¦ Refueling stations at certain points along the way.
¦ Truck fuel capacity = C.
Greedy algorithm.
¦ Go as far as you can before refueling.
Princeton Palo Alto
1
C
C
2
C
3
C
4
C
5
C
6
C
7
4
Sort breakpoints by increasing value:
0 = b
0
< b
1
< b
2
< ... < b
n
.
S ‹ {0}
x = 0
while (x „ b
n
)
let p be largest integer such that b
p
£ x + C
if (b
p
= x)
return "no solution"
x ‹ b
p
S ‹ S ¨ {p}
return S
Greedy Breakpoint Selection Algorithm
Selecting Breakpoints:  Greedy Algorithm
S = breakpoints selected.
5
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
=g
r
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
r = 4
Greedy:
OPT:
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
g
r
f
r
6
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
Greedy:
OPT:
5
5
5
r = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
r = 4
7
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
¦ Thus,  f
0
= g
0
, f
1
= g
1 
, . . . , f
q
= g
q 
1 2 3 4
1 2 3 4 6 7
Greedy:
OPT:
5
5
r = q = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
q
f
q
g
p
8
Activity Selection
Activity selection problem (CLR 17.1).
¦ Job requests 1, 2, … , n.
¦ Job j starts at s
j
and finishes at f
j
.
¦ Two jobs compatible if they don't overlap.
¦ Goal: find maximum subset of mutually compatible jobs.
Time
0
A
C
F
B
D
G
E
123456789 10 11
H
9
Activity Selection:  Greedy Algorithm
Sort jobs by increasing finish times so that
f
1
£ f
2
£ ... £ f
n
.
S = f for j = 1 to n
if (job j compatible with A)
S ‹ S ¨ {j}
return S  
Greedy Activity Selection Algorithm
S = jobs selected.
10
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
11
11
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8 11
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
Replace 11 with 9
12
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
Replace 11 with 9
13
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
r = 4
9
9
14
Making Change
Given currency denominations: 1, 5, 10, 25, 100, devise a method to 
pay amount to customer using fewest number of coins.
¦ Ex. 34¢.
Greedy algorithm.
¦ At each iteration, add coin of the largest value that does not take 
us past the amount to be paid.
¦ Ex. $2.89.
15
Coin-Changing:  Greedy Algorithm
Sort coins denominations by increasing value:
c
1
< c
2
< ... < c
n
.
S ‹f
while (x „ 0)
let p be largest integer such that c
p
£ x
if (p = 0)
return "no solution found"
x ‹ x - c
p
S ‹ S ¨ {p}
return S
Greedy Coin-Changing Algorithm
S = coins selected.
16
Is Greedy Optimal for Coin-Changing Problem?
Yes, for U.S. coinage:  {c
1
, c
2
, c
3
, c
4
, c
5
} = {1, 5, 10, 25, 100}.
Ad hoc proof.
¦ Consider optimal way to change amount c
k 
£ x < c
k+1
.
¦ Greedy takes coin k.
¦ Suppose optimal solution does not take coin k.
– it must take enough coins of type c
1
, c
2
, . . . , c
k-1  
to add up to x.
1
c
k
10
25
100
4
Max # taken by
optimal solution
2
3
5 1
no limit
k
1
3
4
5
2
4
Max value of coins
1, 2, . . . , k in any OPT
20 + 4 = 24
75 + 24 = 99
4 + 5 = 9
no limit
2 dimes   no nickels
Page 5


Greed
"Greed is good. Greed is right. Greed 
works. Greed cuts through, clarifies, 
and captures the essence of the 
evolutionary spirit."
Gordon Gecko
(Michael Douglas)
2
Greedy Algorithms
Some possibly familiar examples:
¦ Gale-Shapley stable matching algorithm.
¦ Dijkstra’s shortest path algorithm.
¦ Prim and Kruskal MST algorithms.
¦ Huffman codes.
¦ .   .   .
3
Selecting Breakpoints
Minimizing breakpoints.
¦ Truck driver going from Princeton to Palo Alto along 
predetermined route.
¦ Refueling stations at certain points along the way.
¦ Truck fuel capacity = C.
Greedy algorithm.
¦ Go as far as you can before refueling.
Princeton Palo Alto
1
C
C
2
C
3
C
4
C
5
C
6
C
7
4
Sort breakpoints by increasing value:
0 = b
0
< b
1
< b
2
< ... < b
n
.
S ‹ {0}
x = 0
while (x „ b
n
)
let p be largest integer such that b
p
£ x + C
if (b
p
= x)
return "no solution"
x ‹ b
p
S ‹ S ¨ {p}
return S
Greedy Breakpoint Selection Algorithm
Selecting Breakpoints:  Greedy Algorithm
S = breakpoints selected.
5
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
=g
r
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
r = 4
Greedy:
OPT:
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
g
r
f
r
6
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
1 2 3 4 5 6 7
1 2 3 4 5 6 7 9 8
Greedy:
OPT:
5
5
5
r = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
p
f
q
r = 4
7
Selecting Breakpoints
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let 0 = g
0 
< g
1 
<  . . . < g
p 
= L denote set of breakpoints chosen by 
greedy and assume it is not optimal.
¦ Let 0 = f
0 
< f
1 
<  . . . < f
q 
= L denote set of breakpoints in optimal 
solution with  f
0
= g
0
, f
1
= g
1 
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: q < p.
¦ Thus,  f
0
= g
0
, f
1
= g
1 
, . . . , f
q
= g
q 
1 2 3 4
1 2 3 4 6 7
Greedy:
OPT:
5
5
r = q = 5
g
0
g
1
g
2
f
0
f
1
f
2
g
q
f
q
g
p
8
Activity Selection
Activity selection problem (CLR 17.1).
¦ Job requests 1, 2, … , n.
¦ Job j starts at s
j
and finishes at f
j
.
¦ Two jobs compatible if they don't overlap.
¦ Goal: find maximum subset of mutually compatible jobs.
Time
0
A
C
F
B
D
G
E
123456789 10 11
H
9
Activity Selection:  Greedy Algorithm
Sort jobs by increasing finish times so that
f
1
£ f
2
£ ... £ f
n
.
S = f for j = 1 to n
if (job j compatible with A)
S ‹ S ¨ {j}
return S  
Greedy Activity Selection Algorithm
S = jobs selected.
10
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
11
11
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8 11
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
Replace 11 with 9
12
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
Replace 11 with 9
13
9
Activity Selection
Theorem:  greedy algorithm is optimal.
Proof (by contradiction):
¦ Let g
1
, g
2
, . . . g
p
denote set of jobs selected by greedy and assume 
it is not optimal.
¦ Let f
1
, f
2
, . . . f
q  
denote set of jobs selected by optimal solution with
f
1
= g
1
, f
2
= g
2
, . . . , f
r
= g
r 
for largest possible value of r.
¦ Note: r < q.
1 5 8
1 5 8 9 13
15 21 17
r = 3
p = 6
q = 7
Greedy:
OPT:
f
1 
= g
1
21
f
2 
= g
2
f
3 
= g
3
r = 4
9
9
14
Making Change
Given currency denominations: 1, 5, 10, 25, 100, devise a method to 
pay amount to customer using fewest number of coins.
¦ Ex. 34¢.
Greedy algorithm.
¦ At each iteration, add coin of the largest value that does not take 
us past the amount to be paid.
¦ Ex. $2.89.
15
Coin-Changing:  Greedy Algorithm
Sort coins denominations by increasing value:
c
1
< c
2
< ... < c
n
.
S ‹f
while (x „ 0)
let p be largest integer such that c
p
£ x
if (p = 0)
return "no solution found"
x ‹ x - c
p
S ‹ S ¨ {p}
return S
Greedy Coin-Changing Algorithm
S = coins selected.
16
Is Greedy Optimal for Coin-Changing Problem?
Yes, for U.S. coinage:  {c
1
, c
2
, c
3
, c
4
, c
5
} = {1, 5, 10, 25, 100}.
Ad hoc proof.
¦ Consider optimal way to change amount c
k 
£ x < c
k+1
.
¦ Greedy takes coin k.
¦ Suppose optimal solution does not take coin k.
– it must take enough coins of type c
1
, c
2
, . . . , c
k-1  
to add up to x.
1
c
k
10
25
100
4
Max # taken by
optimal solution
2
3
5 1
no limit
k
1
3
4
5
2
4
Max value of coins
1, 2, . . . , k in any OPT
20 + 4 = 24
75 + 24 = 99
4 + 5 = 9
no limit
2 dimes   no nickels
17
Does Greedy Always Work?
US postal denominations: 1, 10, 21, 34, 70, 100, 350, 1225, 1500.
¦ Ex. 140¢.
¦ Greedy: 100, 34, 1, 1, 1, 1, 1, 1.
¦ Optimal: 70, 70.
18
Characteristics of Greedy Algorithms
Greedy choice property.
¦ Globally optimal solution can be arrived at by making locally 
optimal (greedy) choice.
¦ At each step, choose most "promising" candidate, without 
worrying whether it will prove to be a sound decision in long run.
Optimal substructure property.
¦ Optimal solution to the problem contains optimal solutions to sub-
problems.
– if best way to change 34¢ is {25, 5, 1, 1, 1, 1} then best way to 
change 29¢ is {25, 1, 1, 1, 1}.
Objective function does not explicitly appear in greedy algorithm!
Hard, if not impossible, to precisely define "greedy algorithm."
¦ See matroids (CLR 17.4), greedoids for very general frameworks.
19
Minimizing Lateness
Minimizing lateness problem.
¦ Single resource can process one job at a time.
¦ n jobs to be processed.
– job j requires p
j
units of processing time.
– job j has due date d
j
.
¦ If we assign job j to start at time s
j
, it finishes at time f
j
= s
j
+ p
j
. 
¦ Lateness: l
j
= max { 0,  f
j
-d
j
}.
¦ Goal:  schedule all jobs to minimize maximum lateness L = max l
j
.
0 123456789 10 11 12 13 14 15
d = 11
d = 8
d = 15
d = 6 d = 9
d = 9
d = 11 d = 8 d = 2 d = 6 d = 9 d = 9
Lateness = 3
20
Minimizing Lateness:  Greedy Algorithm
Sort jobs by increasing deadline so that
d
1
£ d
2
£ … £ d
n
.
t = 0
for j = 1 to n
Assign job j to interval [t, t + p
j
]
s
j
‹ t, f
j
‹ t + p
j
t ‹ t + p
j
output intervals [s
j
,f
j
]
Greedy Activity Selection Algorithm
max lateness = 2
0 123456789 10 11 12 13 14 15
d
5
= 11 d
2
= 8 d
6
= 15 d
1
= 6 d
4
= 9 d
3
= 9
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!