Algorithm

Greedy Algorithm

Hyoungshick Kim
Department of Software
College of Software
Sungkyunkwan University
 Greedy Algorithms
• A greedy algorithm is a simple, intuitive algorithm
strategy that is used in optimization problems
• The algorithm always makes the choice that looks
best at each step
– Greedy algorithms have only one shot to compute the
optimal solution so that they never go back and reverse
the decision.
– Greedy algorithms do not always yield optimal solutions,
but for many problems they do
• The greedy method is quite powerful and works well for
a wide range of problems.
– Activity selection problem
– Minimum spanning tree
– Fractional knapsack problem
– Huffman codes
– Dijkstra’s algorithm for shortest paths from a single source
– Set-cover heuristic

It is very straightforward to design greedy algorithms!

 Activity-Selection Problem
• Problem: get your money’s worth out of a
carnival
– Buy a free pass ticket that lets you onto any ride
– Lots of rides, each starting and ending at different
times
– Your goal: ride as many rides as possible
 Activity-Selection
• Formally:
– Given a set S of n activities
si = start time of activity i
fi = finish time of activity i
– Two activities are compatible if they don't overlap.
– Find a max-size subset A of compatible activities
3
4 6
2
1 5

Assume that f1  f2  …  fn
 Greedy Approach for Activity-
Selection

Intuition suggests that we should choose an activity that leaves

the resource available for as many other activities as possible.

“Choose the activity with the earliest finishing time.”

An algorithm to solve the activity-selection problem does not
need to work bottom-up, like a table-based dynamic-
programming algorithm.

Instead, it can work top-down, choosing an activity to put into

the optimal solution and then solving the subproblem of
choosing activities from those that are compatible with those
already chosen.

Greedy algorithms typically have this top-down design: make a

choice and then solve a subproblem, rather than the bottom-up
technique of solving subproblems before making a choice.
 Activity Selection:
Optimal Substructure
• Let k be the minimum activity in A (i.e., the
one with the earliest finish time). Then A - {k}
is an optimal solution to S’ = {i  S: si  fk}
– Once activity #1 is selected, the problem reduces
to finding an optimal solution for activity-selection
over activities in S compatible with #1
– Proof: if we could find an optimal solution B to S’
where |B| > |A - {k}|,
• Then B U {k} is compatible
• Thus, |B U {k}| > |A| Proof by contradiction
 Greedy Choice Property
• Activity selection problem also exhibits the
greedy choice property:
– Locally optimal choice  globally optimal solution
– If S is an activity selection problem sorted by finish time,
then  optimal solution A  S such that {1}  A
• Sketch of proof: if  optimal solution B does not
contain {1}, we can always replace the first activity in B
with {1} so that the optimal solution contains {1}.
 Activity Selection:
A Greedy Algorithm
• So actual algorithm is simple:
1. Sort the activities by finish time
2. Schedule the first activity
3. Schedule the next activity in the sorted list which
starts after previous activity finishes
4. Repeat until no more activities
• Intuition is even more simple:
– Always pick the shortest ride available at the time
 Elements of the greedy strategy

A greedy algorithm obtains an optimal solution to a

problem by making a sequence of choices when the
problem has the optimal substructure.

At each decision point, the algorithm makes a choice

that seems best at the moment.

Heuristic strategies do not always produce an optimal

solution, but as we saw in the activity-selection problem,
sometimes it does.
 Greedy Steps
1. Determine the optimal substructure of the problem.

2. Prove that it is always safe to make the greedy choice.

3. Develop a recursive algorithm that implements the greedy

strategy.
 Huffman Code
• Approach
– Variable length encoding of symbols
– Exploit statistical frequency of symbols
– Efficient when symbol probabilities vary widely
• Principle
– Use fewer bits to represent frequent symbols
– Use more bits to represent infrequent symbols

A A B A

A A B A
 Huffman Code Example
Symbol A B C D
Frequency 12.5% 25% 50% 12.5%
Original 00 01 10 11
Encoding 2 bits 2 bits 2 bits 2 bits
Huffman 110 10 0 111
Encoding 3 bits 2 bits 1 bit 3 bits

• Expected size
– Original  1/82 + 1/42 + 1/22 + 1/82 = 2 bits / symbol
– Huffman  1/83 + 1/42 + 1/21 + 1/83 = 1.75 bits / symbol
 Huffman Code Data Structures
• Binary (Huffman) tree D A
– Represents Huffman code
– Edge  code (0 or 1)
B
– Leaf  symbol 1 0
– Path to leaf  encoding
– Example C
1 0
• A = “110”, B = “10”, C = “0”
• Priority queue 1 0
– To efficiently build a binary tree
Huffman Code Algorithm Overview
• Encoding
– Calculate frequencies of symbols in file
– Create a binary tree representing “best” encoding
– Use the binary tree to encode a compressed file
• For each symbol, output each path from the root to a
leaf
• Size of encoding = length of the path
– Save the binary tree
 Huffman Code – Creating Tree
• Algorithm
– Place each symbol in a leaf
• Weight of leaf = symbol frequency
– Select two trees L and R (initially leaves)
• Such that L and R have lowest frequencies in tree
– Create a new (internal) node
• Left child  L
• Right child  R
• New frequency  frequency( L ) + frequency( R )
– Repeat until all nodes merged into one tree
Huffman Tree Construction 1
A C E H I
3 5 8 2 7
Huffman Tree Construction 2
A H C E I
3 2 5 8 7

5
Huffman Tree Construction 3
A E I
H
8 7
3 2
C

5 5

10
Huffman Tree Construction 4
E I
A H
8 7
3 2
C
15
5 5

10
 Huffman Tree Construction 5
A H
I = 00
3 2 E = 01
C E I C = 10
1 0
5 5 8 7 H = 110
1 0 1 0 A = 111
10 15

1 0
25
 Huffman Coding Example
I = 00
• Huffman code E = 01
C = 10
H = 110
A = 111
• Input
– ACE
• Output
– (111)(10)(01) = 1111001
Huffman Code Algorithm Overview
• Decoding
– Read a compressed file & binary tree
– Use the binary tree to the decode file
• Follow a path from the root to leaf
 Huffman Decoding 1
A H
1111001
3 2
C E I
1 0
5 5 8 7

1 0 1 0
10 15

1 0
25
 Huffman Decoding 2
A H
1111001
3 2
C E I
1 0
5 5 8 7

1 0 1 0
10 15

1 0
25
 Huffman Decoding 3
A H
1111001
3 2
C E I
1 0
5 5 8 7 A
1 0 1 0
10 15

1 0
25
 Huffman Decoding 4
A H
1111001
3 2
C E I
1 0
5 5 8 7 A
1 0 1 0
10 15

1 0
25
 Huffman Decoding 5
A H
1111001
3 2
C E I
1 0
5 5 8 7 AC
1 0 1 0
10 15

1 0
25
 Huffman Decoding 6
A H
1111001
3 2
C E I
1 0
5 5 8 7 AC
1 0 1 0
10 15

1 0
25
 Huffman Decoding 7
A H
1111001
3 2
C E I
1 0
5 5 8 7 ACE
1 0 1 0
10 15

1 0
25
 Huffman Code Properties
• Prefix code
– No code is a prefix of another code
– Example
• Huffman(“I”)  00
• Huffman(“X”)  001 // not legal prefix code
– We can stop as soon as the complete code is found
– No need for an end-of-code marker

• Nondeterministic
– Multiple Huffman codes can be generated for the same input
– There can exist more than two trees with the same minimal weight
 Huffman Code Properties
• Greedy algorithm
– Chooses the best local solution at each step
– Combines 2 trees with the lowest frequencies

• Greedy algorithm yields the best solution

– Optimal prefix code
– Based on statistical frequency

• Better compression possible (depending on data)

– Using other approaches (e.g., pattern dictionary)
 Knapsack Problem
• 0-1 knapsack problem
- Each item must be either taken or left
behind.

• Fractional knapsack problem

- We can take fractions of items.
 Knapsack Problem

n = 4,
W = 50

45 50
30
20
10
$60 $100 $120 $135 knapsack
($6/pound) ($5/pound) ($4/pound) ($3/pound)
 Knapsack Problem:
Greedy Vs. Dynamic
• The fractional problem can be solved greedily
– Greedy strategy: take in the order of
dollars/pound

• The 0-1 problem cannot be solved with a

greedy approach
– As you have seen, however, it can be solved with
dynamic programming
 Fractional Knapsack Problem

Greedy algorithm: $240

greatest value per pound
20
30
45
30 50 50
20
20
$120 10 10
$135 ($4/pound) $100
($3/pound) ($5/pound)
$60
($6/pound) knapsack
 0-1 Knapsack Problem

$220
10 $135
$60 $160 30
($6/pound) 30
45 50 50 50 50
20 45
20 $120
($4/pound) 20
10
$100 $135
($5/pound) ($3/pound) value value optimal
per unit
 0-1 Knapsack Problem

$220
$135
Difficult to get the
optimal solution with a
greedy strategy. $160 30
50 50 50 50
Dynamic 20 45
Programming :
20
10
value value optimal
per unit
 Greedy Algorithm vs
Dynamic Programming

Dynamic Programming Greedy Algorithm

Computes all subproblems Find a local optimum

Always finds the optimal May not be able to find the

solution optimal solution
Less efficient More efficient
Questions?