Greedy Algorithms
Divide and Conquer (Recap)
Big problem
sub-problem sub-problem
sub-sub- sub-sub- sub-sub- sub-sub- sub-sub-
problem problem problem problem problem
Dynamic Programming (Recap)
Big problem
sub-problem sub-problem sub-problem
sub-sub- sub-sub- sub-sub- sub-sub-
problem problem problem problem
Greedy Algorithms
• Make greedy choices one-at-a-time.
• Never look back.
• Hope (prove) that the greedy choice leads to optimal solution.
Activity Selection Problem
• Activities are competing for an exclusive access to a common
resource, i.e., conference room
• A set 𝑆 = {𝑎1 , 𝑎2 , … , 𝑎𝑛 } of n activities requires the same resource
• The resource can serve only one activity at a time
• Each activity 𝑎𝑖 has a start time 𝑠𝑖 and a finish time 𝑓𝑖
• 𝑎𝑖 and 𝑎𝑗 are compatible if 𝑠𝑖 ≥ 𝑓𝑗 or 𝑠𝑗 ≥ 𝑓𝑖
• Starts after the other finishes
Activity Selection Problem
• Activities are competing for an exclusive access to a common
resource, i.e., conference room
• A set 𝑆 = {𝑎1 , 𝑎2 , … , 𝑎𝑛 } of n activities requires the same resource
• The resource can serve only one activity at a time
• Each activity 𝑎𝑖 has a start time 𝑠𝑖 and a finish time 𝑓𝑖
• Goal:
• Schedule maximum-size subset of mutually compatible activities
Activity Selection Problem
• Assumption: The activities are sorted by their finish times
𝑓1 ≤ 𝑓2 ≤ 𝑓3 ≤ … ≤ 𝑓𝑛
• If not, sort with O(𝑛 𝑙𝑔𝑛)
Activity Selection Problem
• Does this have optimal substructure property?
• Let 𝑆𝑖𝑗 be the set of activities that
• Start after activity 𝑎𝑖 finishes and that finish before activity 𝑎𝑗 starts.
• If 𝑎𝑘 ∈ 𝑆𝑖𝑗 is included in the optimal solution,
• Solve activity selection problem on 𝑆𝑖𝑘 and 𝑆𝑘𝑗
Activity Selection Problem
• Does this have optimal substructure property?
• If 𝐴𝑖𝑗 is the maximum-size compatible subset of activities in 𝑆𝑖𝑗
𝐴𝑖𝑗 = 𝐴𝑖𝑘 ∪ 𝑎𝑘 ∪ 𝐴𝑘𝑗
|𝐴𝑖𝑗 = |𝐴𝑖𝑘 + 1 + |𝐴𝑘𝑗 |
• Let, 𝑐 𝑖, 𝑗 denote the size of an optimal solution for the set 𝑆𝑖𝑗
Activity Selection Problem
• Does this have optimal substructure property?
• Yes!!!
• Can also use cut-and-paste argument for proof
• DP??
Activity Selection Problem
• Let’s make a greedy choice
• Choose the activity that leaves the resource available for as many
other activities as possible
• Any optimal solution has an activity that finishes first
• Here, choose the activity in S with the earliest finish time,
• Leave the resource available for maximum number of other activities
Activity Selection Problem
• Let’s make a greedy choice
• Choose the activity with earliest finish time
• Once a greedy choice is made,
• There is only one remaining subproblem to solve
• Solve for the activities that starts after the first-choice finishes
Activity Selection Problem
• Let 𝑆𝑘 = {𝑎𝑖 ∈ 𝑆; 𝑠𝑖 ≥ 𝑓𝑘 }
• Once we have picked 𝑎𝑘 , all we need to solve is 𝑆𝑘
• Optimal Substructure Property
Activity Selection Problem
• The greedy choice
• Choose the activity with earliest finish time
• Is it optimal?
Activity Selection Problem
Activity Selection Problem
Activity Selection Problem
Activity Selection Problem
Activity Selection Problem
Elements of Greedy Strategy
• Optimal Substructure property
• Greedy Choice Property
• Assemble a globally optimal solution by making locally optimal (greedy)
choices.
• Make the choice that looks best in the current problem, without
considering results from subproblems.
Elements of Greedy Strategy
Big problem
sub-problem
sub-sub-
problem
Knapsack Problems
• 0-1 Knapsack Problem
• Choice at each step
• The choice usually depends on the solutions to subproblems.
• Fractional Knapsack Problem
• Pick the item with maximum vi /𝑤𝑖 ratio
• Repeat as long as
• The supply is not exhausted
• The thief can still carry more,
Knapsack Problems
• W = 50
• w = [10, 20, 30], v = [60, 100, 120]
• 0-1 Knapsack Problem
• Pick item 2 and 3
• Fractional Knapsack Problem
• Pick item 1, 2 and portion of 3
Single Source Shortest Path
• Given
• A weighted and directed graph, G = (V, E) What about unweighted graphs?
• A source, s
• Goal: Find out the shortest path weight from the source to a given
node / other nodes.
Single Source Shortest Path
• Subpaths of shortest paths are shortest paths
• Proof:
• Decompose the shortest path into smaller sub-paths
p = 𝑣1 ∼ 𝑣𝑖 ∼ 𝑣𝑗 ∼ 𝑣𝑘
• The subpaths are 𝑝0𝑖 , 𝑝𝑖𝑗 , 𝑝𝑗𝑘
• Assume there exists 𝑝𝑖𝑗 ′ such that 𝑤(𝑝𝑖𝑗 ′) < 𝑤(𝑝𝑖𝑗 )
• Then replacing 𝑝𝑖𝑗 with 𝑝𝑖𝑗 ′ gives a shorter path
• Optimal Substructure Property
Single Source Shortest Path
• Negative-weight Edges
• Graph may contain negative weight cycles reachable from source s
• Shortest path problem is not well-defined
• Cycle
• Shortest path cannot contain cycle
• Just dropping the cycle gives a lower cost path
Dijkstra’s Algorithm
• Given
• A weighted and directed graph, 𝐺 = (𝑉, 𝐸)
• A source, 𝑠
• Non-negative weights on edges, 𝑤 𝑢, 𝑣 ≥ 0
• Goal: Find out the shortest path weight from the source to a given
node / other nodes.
Dijkstra’s Algorithm
• A path weight of a, 𝑝 = < 𝑣1 , 𝑣2 , … , 𝑣𝑘 >, is
• Shortest path weight is defined as,
Dijkstra’s Algorithm
• Relaxation
• 𝑥. 𝑑 best known estimate of the shortest distance from s to x
v.d = min(v.d , u.d + w(u,v))
Dijkstra’s Algorithm
• Relaxation
• 𝑥. 𝑑 best known estimate of the shortest distance from s to x
v.d = min(v.d , u.d + w(u,v))
• Also keep track of the predecessor
• The node immediately before v on the shortest path from s to v
Dijkstra’s Algorithm
• Initialization
Dijkstra’s Algorithm
• Remember BFS?
• At each step, pick the next node from discovered nodes in the queue
• Dijkstra’s Algorithm The greedy choice!!!!
• Similar to BFS
• Except that at each step, pick the next node with the minimum estimated
shortest-path weight
• Replace the FIFO queue of BFS with a minimum priority-queue
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
• Correctness of Dijkstra’s Algorithm
• S is the set of visited nodes
• The algorithm terminates when 𝑆 = 𝑉
• Inductive Hypothesis:
• At the start of each iteration, 𝑣 = 𝛿(𝑠, 𝑣) for all 𝑣 ∈ 𝑆
Dijkstra’s Algorithm
• Correctness of Dijkstra’s Algorithm
• At some iteration, v is extracted from the priority queue
• y first node not in S on the shortest path P to u
• x predecessor of y on P
𝑦. 𝑑 ≥ 𝑣. 𝑑
𝛿 𝑠, 𝑥 + 𝑤 𝑥, 𝑦 ≥ 𝛿 𝑠, 𝑢 + 𝑤(𝑢, 𝑣)
𝑤 𝑃 ≥ 𝑤(𝑠 ∼ 𝑣)
Minimum Spanning Tree
• A spanning tree is a tree that connects all of the vertices.
• The cost of a spanning tree is the sum of the weights on the edges.
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
Minimum Spanning Tree
• A spanning tree is a tree that connects all of the vertices.
• The cost of a spanning tree is the sum of the weights on the edges.
8 7
B C D
It has cost 67
4 9
2
11 4
A I 14 E
7 6
8 10
A tree is a
1 2 connected graph
H G F
with no cycles!
Minimum Spanning Tree
• A minimum spanning tree is a tree with minimum cost that connects
all of the vertices.
8 7
B C D
It has cost 37
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
Some Definitions
• An (𝑆, 𝑉 − 𝑆) partition is a cut of 𝑉 of an undirected graph 𝐺 =
(𝑉, 𝐸)
• Edge (𝑢, 𝑣) crosses a cut if 𝑢 ∈ 𝑆 and v ∈ 𝑉 − 𝑆
• An edge is a light edge crossing a cut if its weight is the minimum of
any edge crossing the cut.
Minimum Spanning Tree
• The strategy:
• Make a series of greedy choices, adding edges to the tree.
• Show that each edge we add is safe to add:
• we do not rule out the possibility of success
• Keep going until we have an MST.
Minimum Spanning Tree
• Greedy strategy 1 (Prim’s Algorithm):
• Start from an empty tree (a cut)
• At each step, grow the tree (a cut) with a node that can be connected with
minimum cost (i.e., grow the tree by adding the node on the other end of the
light edge)
• Terminate when all nodes are included in the tree
Prim’s Algorithm
8 7
Root Node B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
44
Prim’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
45
Prim’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
46
Prim’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
47
Prim’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
48
Prim’s Algorithm
Prim’s Algorithm
• Proof of correctness?
• Later
Minimum Spanning Tree
• Greedy Strategy 2 (Kruskal’s Algorithm):
• Start with each node as a separate tree
• Consider the edges in ascending order of their weights
• Include the minimum weight edge between two disjoint trees to connect
them into a single tree
• Discard the edge if it creates a cycle
• Terminate when all the nodes are included
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
52
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
53
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
54
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
55
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
56
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
57
Kruskal’s Algorithm
Causing a cycle
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
58
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
59
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
60
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
61
Kruskal’s Algorithm
8 7
B C D
4 9
2
11 4
A I 14 E
7 6
8 10
1 2
H G F
62
Kruskal’s Algorithm
Kruskal’s Algorithm
Proof of Correctness?
• Later
Cut Property
• Assume that all edge costs are distinct.
• Let S be any subset of nodes that is neither empty nor equal to all of
V, and let edge e =(v, w) be the minimum cost edge with one end in S
and the other in V −S.
• Then every minimum spanning tree contains the edge e
Correctness
• Kruskal’s Algorithm
• Apply cut property
• Prim’s Algorithm
• Apply cut property
Reference
• Greedy Algorithms
• CLRS 4th ed. Sections 15.1, 15.2
• Dijkstra’s Algorithm
• CLRS 4th ed. Sections 22 (intro), 22.3
• Minimum Spanning Tree
• CLRS 4th ed. Sections 21.1, 21.2
• KT Section 4.5 (Correctness)
