Comp 122, Spring 2004

Greedy Algorithms
greedy - 2
Lin / Devi
Comp 122, Fall 2003
Overview
Like dynamic programming, used to solve optimization
problems.
Problems exhibit optimal substructure (like DP).
Problems also exhibit the greedy-choice property.
When we have a choice to make, make the one that looks
best right now.
Make a locally optimal choice in hope of getting a globally
optimal solution.


greedy - 3
Lin / Devi
Comp 122, Fall 2003
Greedy Strategy
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, its always safe to
make the greedy choice.
Show that all but one of the subproblems resulting from the
greedy choice are empty.
greedy - 4
Lin / Devi
Comp 122, Fall 2003
Activity-selection Problem
Input: Set S of n activities, a
1
, a
2
, , a
n
.
s
i
= start time of activity i.
f
i
= finish time of activity i.
Output: Subset A of maximum number of compatible
activities.
Two activities are compatible, if their intervals dont overlap.

Example:
Activities in each line
are compatible.
greedy - 5
Lin / Devi
Comp 122, Fall 2003
Optimal Substructure
Assume activities are sorted by finishing times.
f
1
s f
2
s s f
n
.
Suppose an optimal solution includes activity a
k
.
This generates two subproblems.
Selecting from a
1
, , a
k-1
, activities compatible with one
another, and that finish before a
k
starts (compatible with a
k
).
Selecting from a
k+1
, , a
n
, activities compatible with one
another, and that start after a
k
finishes.
The solutions to the two subproblems must be optimal.
Prove using the cut-and-paste approach.

greedy - 6
Lin / Devi
Comp 122, Fall 2003
Recursive Solution
Let S
ij
= subset of activities in S that start after a
i

finishes and finish before a
j
starts.
Subproblems: Selecting maximum number of mutually
compatible activities from S
ij
.
Let c[i, j] = size of maximum-size subset of mutually
compatible activities in S
ij
.

= + +
=
=
< <
|
|
ij
j k i
ij
S j k c k i c
S
j i c
if } 1 ] , [ ] , [ max{
if 0
] , [
Recursive
Solution:
greedy - 7
Lin / Devi
Comp 122, Fall 2003
Greedy-choice Property
The problem also exhibits the greedy-choice property.
There is an optimal solution to the subproblem S
ij
, that
includes the activity with the smallest finish time in set S
ij
.
Can be proved easily.
Hence, there is an optimal solution to S that includes
a
1
.
Therefore, make this greedy choice without solving
subproblems first and evaluating them.
Solve the subproblem that ensues as a result of making
this greedy choice.
Combine the greedy choice and the solution to the
subproblem.
greedy - 8
Lin / Devi
Comp 122, Fall 2003
Recursive Algorithm
Recursive-Activity-Selector (s, f, i, j)
1. m i+1
2. while m < j and s
m
< f
i
3. do m m+1
4. if m < j
5. then return {a
m
}
Recursive-Activity-Selector(s, f, m, j)
6. else return |
Initial Call: Recursive-Activity-Selector (s, f, 0, n+1)
Complexity: O(n)
Straightforward to convert the algorithm to an iterative one.
See the text.
greedy - 9
Lin / Devi
Comp 122, Fall 2003
Typical Steps
Cast the optimization problem as one in which we
make a choice and are left with one subproblem to
solve.
Prove that theres always an optimal solution that
makes the greedy choice, so that the greedy choice is
always safe.
Show that greedy choice and optimal solution to
subproblem optimal solution to the problem.
Make the greedy choice and solve top-down.
May have to preprocess input to put it into greedy
order.
Example: Sorting activities by finish time.

greedy - 10
Lin / Devi
Comp 122, Fall 2003
Elements of Greedy Algorithms
Greedy-choice Property.
A globally optimal solution can be arrived at by making a
locally optimal (greedy) choice.
Optimal Substructure.
Comp 122, Spring 2004
Minimum Spanning Trees
greedy - 12
Lin / Devi
Comp 122, Fall 2003
Carolina Challenge
greedy - 13
Lin / Devi
Comp 122, Fall 2003
Minimum Spanning Trees
Given: Connected, undirected, weighted graph, G
Find: Minimum - weight spanning tree, T
Example:
b c
a
d e f
5
11
0
3
1
7
-3
2
a
b c
f e d
5
3
-3
1
0
Acyclic subset of edges(E) that connects
all vertices of G.
greedy - 14
Lin / Devi
Comp 122, Fall 2003
Generic Algorithm
Grows a set A.

A is subset of some MST.

Edge is safe if it can be added to A without destroying this
invariant.
A := C;
while A not complete tree do
find a safe edge (u, v);
A := A {(u, v)}
od
greedy - 15
Lin / Devi
Comp 122, Fall 2003
:cut partitions vertices into
disjoint sets, S and V S.
b c a
d e f
5
11
0
3
1
7
-3
2
this edge crosses the cut
a light edge crossing cut
(could be more than one)
Definitions
cut respects the edge set {(a, b), (b, c)}
one endpoint is in S and the other is in V S.
no edge in the set crosses the cut
greedy - 16
Lin / Devi
Comp 122, Fall 2003
Proof:
Let T be a MST that includes A.
Case: (u, v) in T. Were done.
Case: (u, v) not in T. We have the following:
u
y
x
v
edge in A
cut
shows edges
in T
Theorem 23.1
Theorem 23.1: Let (S, V-S) be any cut that respects A, and let (u, v)
be a light edge crossing (S, V-S). Then, (u, v) is safe for A.
(x, y) crosses cut.
Let T = T - {(x, y)} {(u, v)}.

Because (u, v) is light for cut,
w(u, v) s w(x, y). Thus,
w(T) = w(T) - w(x, y) + w(u, v) s w(T).

Hence, T is also a MST.
So, (u, v) is safe for A.
greedy - 17
Lin / Devi
Comp 122, Fall 2003
In general, A will consist of several connected components.
Corollary
Corollary: If (u, v) is a light edge connecting one CC in (V, A)
to another CC in (V, A), then (u, v) is safe for A.
greedy - 18
Lin / Devi
Comp 122, Fall 2003
Kruskals Algorithm
Starts with each vertex in its own component.
Repeatedly merges two components into one by choosing a light
edge that connects them (i.e., a light edge crossing the cut
between them).
Scans the set of edges in monotonically increasing order by
weight.
Uses a disjoint-set data structure to determine whether an edge
connects vertices in different components.

greedy - 19
Lin / Devi
Comp 122, Fall 2003
Prims Algorithm
Builds one tree, so A is always a tree.
Starts from an arbitrary root r .
At each step, adds a light edge crossing cut (V
A
, V - V
A
) to A.
V
A
= vertices that A is incident on.

greedy - 20
Lin / Devi
Comp 122, Fall 2003
Prims Algorithm
Uses a priority queue Q to find a light edge quickly.
Each object in Q is a vertex in V - V
A
.
Key of v is minimum weight of any edge (u, v), where u e V
A
.
Then the vertex returned by Extract-Min is v such that there exists
u e V
A
and (u, v) is light edge crossing (V
A
, V - V
A
).
Key of v is if v is not adjacent to any vertex in V
A
.

greedy - 21
Lin / Devi
Comp 122, Fall 2003
Q := V[G];
for each u e Q do
key[u] :=
od;
key[r] := 0;
t[r] := NIL;
while Q = C do
u := Extract - Min(Q);
for each v e Adj[u] do
if v e Q . w(u, v) < key[v] then
t[v] := u;
key[v] := w(u, v)
fi
od
od
Complexity:
Using binary heaps: O(E lg V).
Initialization O(V).
Building initial queue O(V).
V Extract-Mins O(V lgV).
E Decrease-Keys O(E lg V).

Using Fibonacci heaps: O(E + V lg V).
(see book)
Prims Algorithm
Note: A = {(v, t[v]) : v e v - {r} - Q}.
decrease-key operation
greedy - 22
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/ c/ a/0
d/ e/ f/
5
11
0
3
1
7
-3
2
Q = a b c d e f
0
Not in tree
greedy - 23
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/5 c/ a/0
d/11 e/ f/
5
11
0
3
1
7
-3
2
Q = b d c e f
5 11
greedy - 24
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/5 c/7 a/0
d/11 e/3 f/
5
11
0
3
1
7
-3
2
Q = e c d f
3 7 11
greedy - 25
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/5 c/1 a/0
d/0 e/3 f/2
5
11
0
3
1
7
-3
2
Q = d c f
0 1 2
greedy - 26
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/5 c/1 a/0
d/0 e/3 f/2
5
11
0
3
1
7
-3
2
Q = c f
1 2
greedy - 27
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/5 c/1 a/0
d/0 e/3 f/-3
5
11
0
3
1
7
-3
2
Q = f
-3
greedy - 28
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
b/5 c/1 a/0
d/0 e/3 f/-3
5
11
0
3
1
7
-3
2
Q = C
greedy - 29
Lin / Devi
Comp 122, Fall 2003
Example of Prims Algorithm
0
b/5 c/1 a/0
d/0 e/3 f/-3
5
3
1
-3