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:
Find decision criterion
Make best choice according to criterion
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:
No two intervals in S overlap.
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?
0
1
2
3
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 ← {}
ymax ← -∞
For J = [x,y] in C
If x > ymax
Add J to S
ymax ← 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, ith 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