Announcements
Announcements
• HW 3 Due Today
• Exam Next Friday
– Basically the same rules as the last exam.
– Complete exam instructions assignment on
gradescope.
– If you cannot make the usual time (and could last
time), please email me by Wednesday.
– Review video on course webpage.
Exam Topics
• Chapters 4 and 2
– BFS
– Dijkstra
• Priority Queues
– Bellman-Ford
– Shortest Paths in DAGs
– Karatsuba
– Master Theorem
– Merge Sort
– Order Statistics
– Binary Search
– Closest Pair of Points
Greedy Algorithms (Ch 5)
• Basics
• Change making
• Interval scheduling
• Exchange arguments
• Optimal caching
• Huffman codes
• Minimal spanning trees
Greedy Algorithms
Often when trying to find the optimal solution
to some problem you need to consider all
your possible choices and how they might
interact with other choices down the line.
But sometimes you don’t. Sometimes you can
just take what looks like the best option for
now and repeat.
Greedy Algorithms
General Algorithmic Technique:
1. Find decision criterion
2. Make best choice according to criterion
3. Repeat until done
Surprisingly, this sometimes works.
Example: Making Change
Problem: How do you make exact change for
$12.83 using the fewest number of bills/coins?
Idea: Want to use biggest denominations
possible.
Amount Left: Bills used:
$12.83 $2.83 $10 $1.83 $1 $0.83 $1 $0.58 ¢25 $0.33 ¢25 $0.08
¢25
$0.03
¢5
$0.02
¢1
$0.01
¢1
$0.00
¢1
10 bills/coins
This is the best
possible!
Change Making
Note: This technique always works for making
change when using American currency.
Note: It does not always work when using other
currencies.
Example: Weirdtopia has $1, $5, $7 bills.
Problem: Make change for $10 in Weirdtopia.
Greedy: Optimal:
$7+$1+$1+$1 = $10 $5+$5 = $10
Things to Keep in Mind about Greedy
Algorithms
• Algorithms are very natural and easy to write
down.
• However, not all greedy algorithms work.
• Proving correctness is important.
Interval Scheduling
Imagine that you are trying to schedule as many
classes as possible without any conflicting
lectures.
Problem: Given a collection C of intervals, find a
subset S ⊆ C so that:
1. No two intervals in S overlap.
2. Subject to (1), |S| is as large as possible.
Question: Interval Scheduling
What is the greatest number of non-overlapping
intervals that can be picked from the below?
A) 0
B) 1
C) 2
D) 3
E) 4
First Interval
• Note: S must consist of intervals
J1 = [x1,y1], J2 = [x2,y2], …
where yi < xi+1.
• What is the best J1?
– Only way J1 matters is that y1 < x2.
– Want y1 as small as possible.
• Once, we’ve picked J1, have another interval
cover problem among the intervals that don’t
overlap J1.
• Algorithm: repeatedly pick non-overlapping
interval with smallest max.
Algorithm
IntervalScheduling(C)
S ← {}
While(some interval in C
doesn’t overlap any in S)
Let J be the non-overlapping
interval with smallest max
Add J to S
Return S
O(n)
iterations
O(n)
time
Runtime: O(n2)
Proof of Correctness
• Algorithm produces J1, J2,…,Js with Ji = [xi,yi].
• Consider some other solution
K1, K2,…,Kt with Ki = [wi,zi].
Claim: For each m ≤ t, ym ≤ zm.
In particular, s ≥ t.
Proof of Claim
Use Induction on m.
Base Case: m = 1.
J1 is the interval with smallest max, so y1 ≤ z1.
Inductive Step: Assume ym ≤ zm.
• Jm+1 has smallest y for any [x,y] with x > ym.
• Km+1 = [wm+1, zm+1] has
wm+1 > zm ≥ ym
• Therefore, ym+1 ≤ zm+1.
Optimization
• Original algorithm checks all intervals every
time.
• Only need to consider intervals in increasing
order of y.
• Sort once.
Optimized Algorithm
IntervalScheduling(C)
Sort C by y-value
S ← {}
y
max
← -∞
For J = [x,y] in C
If x > y
max
Add J to S
y
max
← y
Return S
O(n log(n))
O(n)
Runtime:
O(n log(n))
Question: Other Greedy Candidates
What are other possible candidate greedy
decision procedures for interval scheduling?
• Smallest max
• Shortest
• Fewest overlaps
• Largest min
• Smallest min
• Largest max
Only these work!
Smallest Min
Greedy Optimal
Shortest
Greedy Optimal
Fewest Overlaps
Greedy Optimal
Proofs
As it is very easy to write down plausible greedy
algorithms for problems, but more difficult to
find correct ones, it is very important to be
able to prove that your algorithm is correct.
Fortunately, there is a standard proof technique
for greedy algorithms.
Exchange Argument
• Greedy algorithm makes a sequence of decisions D1,
D2, D3,…,Dn eventually reaching solution G.
• Need to show that for arbitrary solutions A that G ≥
A.
• Find sequence of solutions
A=A0, A1, A2,…,An = G
so that:
– Ai ≤ Ai+1
– Ai agrees with D1,D2,…,Di
Exchange Argument
In particular, we need to show that given any Ai
consistent with D1,…,Di we can find an Ai+1 so
that:
• Ai+1 is consistent with D1,…,Di+1
• Ai+1 ≥ Ai
Then we inductively construct sequence
A=A0 ≤ A1 ≤ A2 ≤ … ≤ An = G
Thus, G ≥ A for any A. So G is optimal.
Exchange Argument for Interval
Packing
• What decisions does greedy algorithm make?
– Di, i
th interval equals Ji.
• Need to show that IF we have a solution that
agrees with first i decisions, can make it agree
with i+1 without making it worse.
• Have solution: J1,J2,…,Ji,Ki+1,…,Km
– Need to modify to use interval Ji+1.
Inductive Step
Greedy solution: J1,J2,…,Jn Ji = [xi,yi]
Current solution: J1,J2,…,Ji,Ki+1,…,Km Ki = [wi,zi]
Claim: J1,J2,…,Ji,Ji+1,Ki+2,…,Km is a valid solution.
Proof: Need to verify:
• xi+1 > yi: This is because Ji, Ji+1 don’t overlap.
• wi+2 > yi+1: This is because wi+2 > zi+1 ≥ yi+1.
Example
Greedy Solution Arbitrary Solution