2ILC0: Algorithms
Lecture 2:
Greedy algorithms
Bart M. P. Jansen
Optimization problems
• For each instance there are (possibly) multiple valid solutions
• Goal is to find an optimal solution
• minimization problem:
associate cost to every solution, find min-cost solution
• maximization problem:
associate profit to every solution, find max-profit solution
2
Techniques for optimization
Optimization problems typically involve making choices
Backtracking algorithms: just try all solutions
• can be applied to almost all problems, but gives very slow algorithms
• try all options for first choice,
for each option, recursively make other choices
Greedy algorithms: construct solution iteratively, make choice that seems best
• can be applied to few problems, but gives fast algorithms
• only try option that seems best for first choice (greedy choice)
recursively make other choices
Dynamic programming algorithms
• in between: not as fast as greedy, but works for more problems
3
Algorithms for optimization: how to improve on backtracking
1. try to discover structure of optimal solutions:
what properties do optimal solutions have ?
– what are the choices that need to be made ?
– do we have optimal substructure ?
optimal solution = first choice + optimal solution for subproblem
– do we have greedy-choice property for the first choice ?
2. prove that optimal solutions indeed have these properties
– prove optimal substructure and greedy-choice property
3. use these properties to design an algorithm and prove correctness
– proof by induction (possible because optimal substructure)
4
Today: Two examples of greedy algorithms
“bla bla …”
8:00 10:00 12:00 14:00 16:00 18:00 0100110000010000010011000001 …
Activity Optimal text
selection encoding
5
Activity selection problem
8:00 10:00 12:00 14:00 16:00 18:00
Input: set of activities
for each activity : start time , finishing time
Valid solution: any subset of non-overlapping activities
Optimal solution: valid solution with maximum number of activities
6
Activity selection problem
8:00 10:00 12:00 14:00 16:00 18:00
What are the choices ? What properties does optimal solution have?
for each activity, do we select it or not?
• gives a lot of redundancy:
overlapping activities are not allowed to be selected simultaneously
better to look at it differently …
7
Activity selection problem
8:00 10:00 12:00 14:00 16:00 18:00
what is first activity in optimal solution, what is second activity, etc.
do we have optimal substructure?
optimal solution = first choice + optimal solution for subproblem ?
yes!
optimal solution = optimal first activity + optimal selection from
activities that do not overlap first activity
8
Proof of optimal substructure
OPT
8:00 10:00 12:00 14:00 16:00 18:00
Lemma: Let be the first activity in an optimal solution for .
Let be the set of activities in A that do not overlap .
Let be an optimal solution for the set .
Then is an optimal solution for .
Proof. (i) Note that is a valid solution for .
(ii) is a subset of non-overlapping activities from .
So by definition of : .
(iii) The set is a valid solution with activities
and is therefore an optimal solution for .
9
Activity selection problem
8:00 10:00 12:00 14:00 16:00 18:00
What are the choices ? What properties does optimal solution have?
do we have greedy-choice property:
can we select first activity “greedily” and still get optimal solution?
yes! how? “greedy choice”
first activity = activity that ends first
10
Proof of greedy choice property
Let be a set of activities
Lemma: Let be an activity in that ends first. Then there is an optimal
solution to the Activity-Selection Problem for that includes .
Proof. General structure of all proofs for greedy-choice property:
take an arbitrary optimal solution
if contains greedy choice, then done
otherwise modify so that it contains greedy choice,
without decreasing the quality of the solution
or derive a contradiction
11
Proof of greedy choice property
Let be a set of activities
Lemma: Let be an activity in that ends first. Then there is an optimal
solution to the Activity-Selection Problem for that includes .
Proof. Let be an optimal solution for . If includes then the lemma obviously holds.
So it suffices to handle the case that does not include .
We will show how to modify into a solution such that:
(i) is a valid solution standard text you can basically
(ii) includes use in proof for any greedy-
(iii) choice property
quality ≥ quality
Thus is an optimal solution including , and so the lemma holds.
To modify we proceed as follows ...
here comes the modification, which is problem-specific
12
How to modify ?
greedy choice
OPT
8:00 10:00 12:00 14:00 16:00 18:00
replace first activity in OPT by greedy choice
13
Proof of greedy choice property
Let be a set of activities
Lemma: Let be an activity in that ends first. Then there is an optimal
solution to the Activity-Selection Problem for that includes .
Proof. (...) We will show how to modify into a solution such that:
(i) is a valid solution
(ii) includes
(iii)
(...) To modify we proceed as follows.
Let be the activity in ending first, let .
Then includes and .
We have by definition of , so cannot overlap any activities in .
Hence, is a valid solution.
14
Algorithm for Activity Selection
Algorithm Greedy-Activity-Selection
1. if is empty
2. then return the empty set
3. else an activity from that ends first
4. all activities from that do not overlap
5. return Greedy-Activity-Selection
Correctness:
• by induction on , using optimal substructure and greedy-choice property
Running time:
• if implemented naively
• after sorting on finishing time, if implemented more cleverly
15
Intermezzo: More greedy algorithms
Lecture hall assignment
Input: set of activities, each activity has:
start time start , finishing time end
Valid solution: assignment of activities to lecture halls
such that activities in the same hall do not overlap
Optimal solution: assignment using a minimum number of lecture halls
8:00 10:00 12:00 14:00 16:00 18:00
Greedy strategy: pick the activity that ends first, recursively compute
an optimal assignment for , assign the
lowest-numbered hall not used by overlapping activities
16
Intermezzo: More greedy algorithms
Minimum Spanning Tree
Input: undirected graph with edge weights
Valid solution: a spanning tree of
Optimal solution: spanning tree of minimum total edge weight
Greedy strategy: starting from the subgraph containing all vertices but no edges,
repeatedly add an edge of minimum weight connecting two distinct
trees
17
Intermezzo: More greedy algorithms
Disjoint paths between vertices on the exterior of a drawing
Input: a crossing-free drawing of an undirected graph ,
two vertices which lie on the exterior
Valid solution: set of internally vertex-disjoint paths in
Optimal solution: set of maximum cardinality
Greedy strategy: pick a path along the exterior, remove its vertices,
repeat
18
Intermezzo: More greedy algorithms
1-dimensional clustering
Input: set of numbers, in sorted order, integer
Valid solution: a partition of into clusters
Optimal solution: a clustering that minimizes the sum of the costs of the clusters,
where the cost of a cluster is the sum of the points in to
cluster 1 cluster 2 cluster 3
1,3,4,6: average = 3.5, cost = 6
Greedy strategy:
o r re c t!
find the points for which the distance to the next point is largest
c
, but in
make these points the ending points of clusters
g
Temptin
19
Intermezzo: More greedy algorithms
1-dimensional clustering
Input: set of numbers, in sorted order, integer
Valid solution: a partition of into clusters
Optimal solution: a clustering that minimizes the sum of the costs of the clusters,
where the cost of a cluster is the sum of the points in to
1 1 +𝜖
𝑘= 2
Greedy strategy:
o r re c t!
find the points for which the distance to the next point is largest
c
, but in
make these points the ending points of clusters
g
Temptin
20
Intermezzo: More greedy algorithms
1-dimensional clustering
Input: set of numbers, in sorted order, integer
Valid solution: a partition of into clusters
Optimal solution: a clustering that minimizes the sum of the costs of the clusters,
where the cost of a cluster is the sum of the points in to
1 1 +𝜖
𝑘= 2
Greedy strategy:
o r re c t!
find the points for which the distance to the next point is largest
c
, but in
make these points the ending points of clusters
g
Temptin
21
Today: Two examples of greedy algorithms
“bla bla …”
8:00 10:00 12:00 14:00 16:00 18:00 0100110000010000010011000001 …
Activity Optimal text
selection encoding
22
Optimal text encoding
“bla□bla …”
0100110000010000010011000001 …
Standard text encoding schemes: fixed number of bits per character
ASCII: 7 bits (extended versions 8 bits)
UCS-2 (Unicode): 16 bits
Can we do better using variable-length encoding?
Idea: give characters that occur frequently a short code and
give characters that do not occur frequently a longer code
23
The encoding problem
Input: set of characters with for each character its frequency
Output: binary code for each character
code() = 01001, code() = 010, … not a prefix-code
Variable length encoding: how do we know where characters end?
text = 0100101100 …
Does it start with = 01001 or = 010 or … ?
Use prefix-code: no character code is prefix of another character code
24
Does a variable-length prefix encoding help?
Text: “een□voordeel”
Frequencies:
fixed-length code:
e=000 n=001 v=010 o=011 r=100 d=101 l =110 □=111
length of encoded text: bits
possible prefix code:
e=00 n=0110 v=0111 o=010 r=100 d=101 l=110 □=111
length of encoded text: bits
25
Representing prefix codes
Text: “een□voordeel”
code: e=00 n=0110 v=0111 o=010 r =100 d=101 l=110 □=111
which choices have to be made to construct a solution?
• what is the 1st bit of the code for e?
• what is the 2nd bit of the code for e?
• …?
26
Representing prefix codes
Text: “een□voordeel”
code: e=00 n=0110 v=0111 o=010 r =100 d=101 l=110 □=111
0 1
representation is binary tree T:
0 1 0 1 one leaf for each character
e internal nodes always have two outgoing edges,
0 1 0 1 0 1 labeled 0 and 1
o r d l □ code of character: follow path to leaf and list bits
0 1
n v
binary trees that are not full represent
redundant prefix codes
27
Representing prefix codes
What is the cost of encoding the text “never” with this prefix code?
bits
0 1
0 1 0 1
e cost of encoding represented by :
0 1 0 1 0 1
4
o r d l □
2 0 1 1 1 1 1
n v
1 1
frequencies
28
Designing greedy algorithms
1. try to discover structure of optimal solutions:
what properties do optimal solutions have ?
– what are the choices that need to be made ?
– do we have optimal substructure ?
optimal solution = first choice + optimal solution for subproblem
– do we have greedy-choice property for the first choice ?
2. prove that optimal solutions indeed have these properties
– prove optimal substructure and greedy-choice property
3. use these properties to design an algorithm and prove correctness
– proof by induction (possible because optimal substructure)
29
David A. Huffman: how to make choices that determine a tree
which choices determine a prefix code?
define a tree top-to-bottom, or bottom-to-top
David found optimal prefix codes in 1951 to avoid an exam at MIT!
30
Bottom-up construction of the tree
start with separate leaves, and then “merge” n-1 times until we have the tree
choices: which subtrees to merge at every step
c1 c2 c3 c4 c5 c6 c7 c8
4 2 1 1 1 1 1 1
31
Bottom-up construction of the tree
start with separate leaves, and then “merge” n-1 times until we have the tree
choices: which subtrees to merge at every step
c1 c2 c3 c4 c5 c6 c7 c8
4 2 1 1 1 1 1 1
Do we have a greedy-choice property?
Which leaves should we merge first?
Greedy choice: first merge two leaves with smallest character frequency
32
Lemma: Let be two characters with the lowest frequency in .
Then there is an optimal tree for where are siblings.
Proof. Let be an optimal tree for . If are siblings in then
the lemma obviously holds, so assume this is not the case.
We will show how to modify into a tree such that
(i) is a valid tree
(ii) are siblings in standard text you can basically
(iii) use in proof for any greedy-
choice property
Thus is an optimal tree in which are siblings, and so the lemma holds.
To modify we proceed as follows.
now we have to do the modification
33
How to modify ?
𝑇 𝑂𝑃𝑇
𝑐𝑘 𝑐𝑚
𝑓
(𝑐
𝑐𝑖 depth = d1 cs
𝑖
)
≤
v
𝑓
𝑘)
(𝑐
(𝑐
𝑐𝑖 𝑐 𝑘
𝑠
𝑐 𝑠 𝑐𝑚
)
depth = d2
𝑓
)≥
𝑚
(𝑐 cost decrease due to swapping and
take a deepest internal node
𝑓
make children of by swapping
them with current children (if
necessary)
(product of non-negative terms)
34
How to modify ?
𝑇 𝑂𝑃𝑇
𝑐𝑘 𝑐𝑚 depth =
𝑓
(𝑐
𝑐𝑖 cs
𝑖
)
≤
v
𝑓
𝑘)
(𝑐
(𝑐
𝑐 𝑖 𝑐 𝑘 depth =
𝑠
𝑐 𝑠 𝑐𝑚
)
𝑓
)≥
𝑚
(𝑐 cost decrease due to swapping and
take a deepest internal node
𝑓
make children of by swapping
them with current children (if
necessary)
35 Conclusion: is valid tree where are siblings and .
Bottom-up construction of the tree
start with separate leaves, and then “merge” n-1 times until we have the tree
choices: which subtrees to merge at every step
c1 c2 c3 c4 c5 c6 c7 c8 b
4 2 1 1 1 1 1 1 2
Do we have optimal substructure?
Do we even have a problem of the same type?
Yes, we have a subproblem of the same type: after merging, replace merged
leaves by a single leaf with 𝑓 (𝑐 𝑖)+ 𝑓 (𝑐 𝑘)
(other way of looking at it: problem is about merging weighted subtrees)
36
Lemma: Let and be siblings in some optimal tree for set of characters.
Let , where .
Let be an optimal tree for .
Then replacing the leaf for in by an internal node with as
children results in an optimal tree for .
Proof. Based on two claims:
(i)
(ii) is a valid tree for with cost
𝑇𝐵 𝑇𝐶
𝑏 𝑣
(See Lemma 15.3.) 𝑐𝑖𝑐 𝑘
37
The algorithm
Algorithm Construct-Huffman-Tree (: set of characters)
1. if
2. then return a tree consisting of single leaf, storing the character in
3. else two characters from with lowest frequency
4. Remove from , and replace them by a new character
with . Let denote the new set of characters.
5. Construct-Huffman-Tree()
6. Replace leaf for in with internal node with as children.
7. Let be the new tree.
8. return
Correctness:
• by induction, using optimal substructure and greedy-choice property
Running time:
• by straight-forwardly following the code above
38
A faster version of the algorithm
Algorithm Faster-Huffman-Tree (: set of characters)
1.
2. build a priority queue storing , using frequency values as keys
3. for to
4. create an internal node
5. -
6. -
7.
8. insert into
9. return - (pointer to the root of the tree)
Correctness:
• resulting tree is the same as for Construct-Huffman-Tree
Running time:
• if implemented smartly (use heap)
• Sorting if implemented even smarter (hint: 2 queues)
39
Summary
• greedy algorithm solves optimization problem by:
– trying only one option for first choice (the greedy choice),
– then solving subproblem recursively
• needed: optimal substructure + greedy choice property
• proof of greedy-choice property:
– show that optimal solution can be modified such that it uses greedy choice
40
