math
Greedy Algorithms
Jeff Edmonds York University
COSC 3101
Lecture 6
Thinking about Algorithms Abstractly
Greedy Algorithm for Optimization Problems
Proving with Loop Invariants
Three Players making Change
Maintaining the Loop Invariant
Event Scheduling
Review and Don’ts
Minimum Spanning Tree
Adaptive Greedy
Interval Point Cover
Communication and Entropy
Forced Horn Clauses
‹#›
1
Greedy Algorithms
Surprisingly, many important and practical computational problems can be solved this way.
Every two year old knows the greedy algorithm.
Then he grabs the objects in the input
in the order of what looks best.
Without knowing or worrying about the future,
he assigns a value to each potential object.
‹#›
2
An Algorithm As
A Sequence of Decisions
“Which edge should we take first?”
I ask a question about the solution.
How do I decide?
The greedy choice?
Does not work!
Taking the best first edge.
‹#›
3
Ingredients:
Instances: The possible inputs to the problem.
Solutions for Instance: Each instance has an exponentially large set of solutions.
Cost of Solution: Each solution has an easy to compute cost or value.
Specification
Optimization Problems
‹#›
4
Optimization Problems
with a Greedy Algorithm
Instances: A set of objects
and a relationship between them.
Solutions for Instance: A subset of the objects.
Or some other choice about each object.
Some subsets are not allowed
because some objects conflict
‹#›
5
Optimization Problems
with a Greedy Algorithm
Instances: A set of objects
and a relationship between them.
Solutions for Instance: A subset of the objects.
Or some other choice about each object.
Cost of Solution: The number of objects in solution or the sum of the costs of objects
‹#›
6
Optimization Problems
with a Greedy Algorithm
Instances: A set of objects
and a relationship between them.
Goal: Find an optimal non-conflicting solution.
‹#›
7
The Brute Force Algorithm
Exponential Time,
because exponentially many
Try every solution!
‹#›
8
The Greedy Choice
Commit to the object that looks the “best”
Must prove that this locally greedy choice
does not have negative global consequences.
‹#›
9
The Game Show Example
Problem: Choose the best m prizes.
‹#›
10
The Game Show Example
Problem: Choose the best m prizes.
Greedy: Start by grabbing the best.
Consequences: If you take the lion,
you can’t take the elephant.
But greedy algorithms do not try
to predict the future and do not back track.
‹#›
11
The Game Show Example
Iterative Greedy Algorithm:
Loop: grabbing the best, then second best, …
if it conflicts with committed objects
or fulfills no new requirements.
Reject this next best object
else
Commit to it.
Problem: Choose the best m prizes.
‹#›
12
The Game Show Example
Makes a greedy first choice and then recurses (See Recursive Backtracking Algorithms)
Recursive Greedy Algorithm:
Problem: Choose the best m prizes.
‹#›
13
Greedy Criteria:
The algorithm does not know the objects in the input.
But for every possible object
it assigns a real value priority.
The algorithm receives the objects from the input
in this order.
Decision Criteria:
When the algorithm receives the next object,
it knows the past but not the future objects.
It must make an irrivokable decision about this object.
Why so restrictive?
To ensure the
algorithm is fast.
Greedy Algorithms
‹#›
14
Making Change Example
Problem: Find the minimum # of quarters, dimes,
nickels, and pennies that total to a given amount.
‹#›
15
Instances: A set of objects
and a relationship between them.
Some subsets are not allowed
because some objects conflict
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Solutions for Instance:
A subset of the coins that total the amount.
Making Change Example
‹#›
16
Instances: A set of objects
and a relationship between them.
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Solutions for Instance:
A subset of the coins that total the amount.
Cost of Solution: The number of coins = 14
Making Change Example
Goal: Find an optimal non-conflicting solution.
‹#›
17
Instances: A set of objects
and a relationship between them.
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Making Change Example
Greedy Choice:
Does this lead to an optimal # of coins?
Start by grabbing quarters until exceeds amount,
then dimes, then nickels, then pennies.
Cost of Solution: 7
25¢
50¢
75¢
85¢
100¢
95¢
90¢
91¢
92¢
95¢
‹#›
18
Hard Making Change Example
Greedy Choice: Start by grabbing a 4 coin.
Problem: Find the minimum # of
4, 3, and 1 cent coins to make up 6 cents.
Consequences:
4+1+1 = 6 mistake
3+3=6 better
Greedy Algorithm does not work!
‹#›
19
When Does It Work?
Greedy Algorithms: Easy to understand and to code, but do they work?
For most optimization problems,
all greedy algorithms tried do not work.
A few have greedy algorithms.
The proof that they work, however, is subtle.
As with all iterative algorithms,
we use loop invariants.
‹#›
20
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
to school
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
21
The algorithm chooses the “best” object
from amongst those not considered so far
and either commits to it or rejects it.
Define Step
Another object considered
Make Progress
79 km
75 km
Exit
When all objects have been considered
Exit
Exit Condition
‹#›
22
Loop Invariant
Recall that a loop invariant makes a statement
each time the algorithm is at the top of the loop
about what it has accomplished.
After the algorithm has committed to one object,
what statement do we want to make about this action?
‹#›
23
Loop Invariant
The algorithm has only committed to one object
and this does not constitute a valid solution.
“The algorithm’s solution is optimal.”
‹#›
24
Loop Invariant
Being “optimal” is a property of full solutions.
“What the algorithm has done
so far is optimal.”
‹#›
25
More of the Input
Loop Invariant
The input consists of an array of objects
We have read in the first t-1 objects.
We will pretend that this prefix
is the entire input.
We have a solution for this prefix
Solution
‹#›
26
More of the Input
Loop Invariant
The input consists of an array of objects
We have read in the first t-1 objects.
We will pretend that this prefix
is the entire input.
We have a solution for this prefix
Yes: If there is only a lion
take the lion
‹#›
27
More of the Input
Loop Invariant
The input consists of an array of objects
We have read in the first t-1 objects.
We will pretend that this prefix
is the entire input.
We have a solution for this prefix
It is hard to extend this
to knowing that the lion
is in the solution
for the full instance!
‹#›
28
“The” optimal solution contains the best object:
There may be more than one optimal solution
and all might not contain the chosen object.
At least one optimal solution contains the best object:
It is ok to burn a few of your bridges as long
as you do not burn all of them.
We do not go “wrong” by committing
to the best object.
Loop Invariant
‹#›
29
“The” optimal solution contains the best object:
There may be more than one optimal solution
and all might not contain the chosen object.
At least one optimal solution contains the best object:
But this was only for the first iteration.
We do not go “wrong” by committing
to the best object.
Loop Invariant
‹#›
30
Now assume that the algorithm
is at the top of the loop.
Designing the Loop Invariant
‹#›
31
Designing the Loop Invariant
Based on its greedy criteria,
it chose to look first at objects 5, 7, 9, and 3
and to irrevocably commit to all except for Obj7.
At-1:
Let At-1 denote the decisions made by the algorithm
during the first t-1 time steps.
‹#›
32
Designing the Loop Invariant
At-1:
Let At-1 denote the decisions made by the algorithm
during the first t-1 time steps.
St-1:
A solution must make a decision for every object.
St-1 extends At-1:
If At-1 makes a decision about an object,
then St-1 makes the same decision.
i.e. ∀ Obj ∈ I, if At-1(Obj) is decided, then St-1(Obj) = At(Obj).
‹#›
33
Designing the Loop Invariant
At-1:
Let At-1 denote the decisions made by the algorithm
during the first t-1 time steps.
St-1:
A solution must make a decision for every object.
St-1 extends At-1:
What other decisions St-1 makes is
unknown to the algorithm and to the prover.
‹#›
34
Designing the Loop Invariant
At-1:
Let At-1 denote the decisions made by the algorithm
during the first t-1 time steps.
St-1:
A solution must make a decision for every object.
St-1 extends At-1:
These decisions were not made
in any particular order.
‹#›
35
Designing the Loop Invariant
At-1:
Let At-1 denote the decisions made by the algorithm
during the first t-1 time steps.
St-1:
A solution must make a decision for every object.
St-1 extends At-1:
Even though the Algorithm has committed to At-1,
it may still produce St-1.
‹#›
36
Designing the Loop Invariant
At-1:
Let At-1 denote the decisions made by the algorithm
during the first t-1 time steps.
St-1:
A solution must make a decision for every object.
We have not gone wrong.
There is at least one optimal solution St-1 that extends the choices At-1 made so far.
Loop Invariant
‹#›
37
Designing the Loop Invariant
At:
In the tth time steps, the algorithm decides
about the next “best” object.
St-1:
A solution must make a decision for every object.
St-1 extends At:
The Algorithm can no longer produce this solution.
This “bridge” has been burned.
‹#›
38
Designing the Loop Invariant
At:
In the tth time steps, the algorithm decides
about the next “best” object.
St-1:
A solution must make a decision for every object.
St extends At:
Made consistent with
Algorithm’s tth decision
Other decisions
may change
‹#›
39
Designing the Loop Invariant
At:
In the tth time steps, the algorithm decides
about the next “best” object.
St extends At:
We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
‹#›
40
Let these be the set
of optimal solutions St
that extends the
choices At made so far.
When the alg makes
the next commitment
some of these solutions
are no longer possible.
It is ok, as long as we don’t burn the last one.
Don’t Burn Your Last Bridge
‹#›
41
If there are no optimal
solutions that extends the
choices made so far.
We went wrong.
But there is nothing we can do about it.
Don’t Burn Your Last Bridge
‹#›
42
Don’t Burn Your Last Bridge
We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
‹#›
43
We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
Initially with A0, no choices have been made and hence all optimal solutions extend these choices.
Establishing Loop Invariant
‹#›
44
¬
codeB
Exit
Maintaining Loop Invariant
Let St-1 denote one.
$ optSol that extends At-1.
codeB
Commits or rejects the next best object.
Proof changes St-1 into St and proves it
is a valid solution
extends both previous and new choices At.
is optimal
$ optSol St that extends all choices.
?
‹#›
45
¬
codeB
Exit
Maintaining Loop Invariant
Proof changes St-1 into St
Sorry, in the book this is denoted optSours
Because its is the one that “we” the prover had the “fairy godmother” create.
but this made people think that we had it,
which we don’t.
St is a much better name because it is the thing we use to witness the fact that the loop invariant is true after we go around the loop again,
i.e.
‹#›
46
Don’t Burn Your Last Bridge
The prover must prove
that the algorithm’s
next decision does not
burns our last bridge.
Proof by the
change Method
Show how to change
a newly burning bridge into an unburned bridge.
Hence, if we are burning a bridge this iteration
there is another bridge that we are not burning.
Hence, there is a bridge we did not burn.
‹#›
47
Don’t Burn Your Last Bridge
We have not gone wrong.
There is at least
one optimal solution St
that extends the
choices At made so far.
Hence, there is a bridge we did not burn.
‹#›
48
Algorithm:
commits or rejects next best object
Prover:
Proves LI is maintained.
Three Players
Big brother
makes sure
he does not
get into trouble.
Little brother
does dumb
things.
‹#›
49
Algorithm:
commits or rejects next best object
Emphasizes his actions not part of algorithm
Emphasizes alg and Prover do not know St.
Prover:
Proves LI is maintained.
Three Players
Fairy God Mother:
Holds the hypothetical
optSol St.
St
She gives no feedback.
‹#›
50
Algorithm:
commits or rejects next best object
Emphasizes his actions not part of algorithm
Prover:
Proves LI is maintained.
Three Players
Fairy God Mother:
Does she exist?
St-1
The Prover would find his conversations equally supportive, even if she did not.
‹#›
51
Changing St-1 into St
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
I have committed to these coins.
I hold St-1 witnessing that there is an optSol that extends previous choices.
St-1
‹#›
52
Changing St-1 into St
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
I commit to keeping another 25¢
St-1
Different 25¢
are considered to be different.
I hold St-1 witnessing that there is an optSol that extends previous choices.
‹#›
53
Different 25¢
are considered to be different.
Changing St-1 into St
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
I instruct how to change St-1 into St so that it extends previous & new choice.
I commit to keeping another 25¢
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices.
I hold St witnessing that there is an optSol that extends previous & new choices At.
‹#›
54
If it happens to be the case that what you hold extends this new choice that was made, then we are done.
Changing St-1 into St
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
St-1
‹#›
55
The Algorithm has
92¢-50¢ = 42¢ un-chosen.
Changing St-1 into St
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
St-1
Fairy God Mother must also
have ³ 25¢ that I don’t know about.
There are different cases.
³ 25¢
‹#›
56
Changing St-1 into St
St-1
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Replace
A different 25¢
Alg’s 25¢
With
‹#›
57
Changing St-1 into St
St-1
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Replace
A different 25¢
Alg’s 25¢
With
3×10¢
Alg’s 25¢ + 5¢
Oops, this is not actually optimal,
But we must consider all cases.
‹#›
58
Changing St-1 into St
St-1
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Replace
A different 25¢
Alg’s 25¢
With
3×10¢
2×10¢ + 1×5¢
Alg’s 25¢ + 5¢
Alg’s 25¢
‹#›
59
Changing St-1 into St
St-1
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Replace
A different 25¢
Alg’s 25¢
With
3×10¢
2×10¢ + 1×5¢
Alg’s 25¢ + 5¢
1×10¢ + 3×5¢
Alg’s 25¢
Alg’s 25¢
‹#›
60
Changing St-1 into St
St-1
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
Replace
A different 25¢
Alg’s 25¢
With
?? + 5×1¢
3×10¢
2×10¢ + 1×5¢
Alg’s 25¢ + 5¢
1×10¢ + 3×5¢
Alg’s 25¢
Alg’s 25¢
Alg’s 25¢
‹#›
61
St-1
Done
St
Changing St-1 into St
She now has something.
We must prove that it is what we want.
‹#›
62
St
Proving St is valid
St-1 was valid and we introduced no new conflicts.
Changing St-1 into St
Total remains unchanged.
Replace
A different 25¢
Alg’s 25¢
With
?? + 5×1¢
3×10¢
2×10¢ + 1×5¢
Alg’s 25¢ + 5¢
1×10¢ + 3×5¢
Alg’s 25¢
Alg’s 25¢
So still adds up to 92¢
‹#›
63
Proving St extends At
Changing St-1 into St
St-1 extended previous choices At-1
and we made it extend the new
choices At.
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
St
‹#›
64
Proving St is optimal
We do not even know the
cost of an optimal solution.
Changing St-1 into St
St-1 was optimal and
St cost (# of coins) is not bigger.
Replace
A different 25¢
Alg’s 25¢
With
?? + 5×1¢
3×10¢
2×10¢ + 1×5¢
Alg’s 25¢ + 5¢
1×10¢ + 3×5¢
Alg’s 25¢
Alg’s 25¢
St
‹#›
65
St is valid
St extends At
St is optimal
Changing St-1 into St
Case 1
¬
codeB
Exit
Maintaining Loop Invariant
St
‹#›
66
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices At-1.
I must make sure that what the Fairy God Mother has extends this new choice.
Changing St-1 into St
Case 2
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
I reject the next 25¢
‹#›
67
The Algorithm has
92¢-75¢ = 17¢ < 25¢ un-chosen.
Changing St-1 into St
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
St-1
Fairy God Mother must also
have < 25¢ that I don’t know about.
St-1 does not contain the 25¢ either.
‹#›
68
Changing St-1 into St
¬
codeB
Exit
Maintaining Loop Invariant
St
‹#›
69
I instruct how to change St-1 into St so that it extends previous & new choice.
I commit to keeping another 25¢
I know that her St-1
extends these choices.
As Time Goes On
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
25¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
10¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
5¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 92¢
I keep making more choices.
I always hold an optSol St-1 but which one keeps changing.
St-1
Hence, I know more and more of St-1
In the end, I know it all.
‹#›
70
Exit Clean up loose ends
codeC
Alg commit to or reject each object.
Has given a “solution” Aexit=S.
$ optSol Sexit that extends Aexit. codeC ‹#› Making Change Example 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit Greedy Choice: Start by grabbing a 25 coin. ‹#› Hard Making Change Example ‹#› I will now instruct how to change St-1 into St so that it extends previous & new choice. I commit to keeping a 4¢ I hold St-1. ‹#› Running Time ‹#› Proof Greedy Algorithm Works ‹#› Do I take the first object? An Algorithm As Do I take the third? ‹#› When the algorithm makes An Algorithm As The fairy god mother wants what is best for the alg. St-1 At-1 ‹#› When the algorithm makes An Algorithm As The prover is babysitting his little brother. St-1 At-1 ‹#› When the algorithm makes An Algorithm As The fairy god mother really had in mind that he be a lawyer. St -1 At ‹#› An Algorithm As Alg Objt Next decision made. ‹#› An Algorithm As Alg A3 Alg A1 Alg A0 Alg A4 Alg A5 Alg Afinal Next decision made. ‹#› An Algorithm As Prover Alg Objt Decisions made At-1 ‹#› An Algorithm As Prover Alg Objt Decisions made At-1 ‹#› An Algorithm As Prover Alg Objt Decisions made At-1 Exit ‹#› An Algorithm As Prover Prover Prover Prover Prover Prover
Aexit=Sexit must be an optSol.
Alg returns Aexit.
71
Problem: Find the minimum # of quarters, dimes,
nickels, and pennies that total to a given amount.
Greedy Alg works
Ending
Initial Conditions
Make Progress
Maintain Loop Inv
Define Exit Condition
Define Step
Define Measure of Progress
Define Loop Invariants
Define Problem
to school
change
solutions
72
Greedy Choice: Start by grabbing a 4 coin.
Problem: Find the minimum # of
4, 3, and 1 cent coins to make up 6 cents.
Counter Example:
4+1+1 = 6 mistake
3+3=6 better
Greedy Algorithm does not work!
For fun, lets try to prove that it does work.
73
Changing St-1 into St
4¢
4¢
4¢
4¢
4¢
4¢
4¢
4¢
4¢
4¢
3¢
3¢
3¢
3¢
3¢
3¢
3¢
3¢
3¢
3¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
1¢
Amount = 6¢
St-1
Oops!
74
Greedy algorithms are very fast because they take only a small amount of time per object in the instance.
75
Looks hard,
but they all have the same structure.
Take my proof structure.
Change what the instances, solutions, & costs are.
Change what the greedy criteria is.
Change the “changing” step.
Change the proof that the changed solution St is
valid
extents At
optimal
The rest is the same.
76
Each leaf is a full solution.
Some of these are optimal
(i.e. have the same the same value)
Recursive backtracking algorithms (brute force)
are slow because they try all the possibilities.
Greedy algorithms are fast because they follow
one path down the tree.
Do I take the second?
A Sequence of Decisions
77
an irrevocable decision
some solutions are no longer possible.
A Sequence of Decisions
That his decisions have not prevented him from an optimal life.
That there is still an optimal solution St-1 consistent with the decisions At-1 that he has made so far.
78
an irrevocable decision
some solutions are no longer possible.
A Sequence of Decisions
His job is to make sure his mom stays happy.
79
an irrevocable decision
some solutions are no longer possible.
A Sequence of Decisions
But if he becomes a doctor is that really so bad?
As long as there is still an optimal solution St consistent with the decisions At that he has made.
-1
80
A Sequence of Decisions
At
At-1
Decisions made
by alg so far.
81
A Sequence of Decisions
A2
Obj1
Obj2
Obj3
Obj4
Obj5
Objfinal
Decisions made
by alg so far.
No decisions made yet.
The final
output.
A full
solution
82
A Sequence of Decisions
At
Objt
St-1
St
We have not gone wrong.
There is at least one optimal solution St-1 that extends the choices At-1 made so far.
Loop Invariant
by alg so far.
83
A Sequence of Decisions
At
Objt
St-1
St
The prover does not know St-1
He just gives a paragraph describing
to the Fairy Good mother
how to change St-1 into St.
by alg so far.
84
A Sequence of Decisions
At
Objt
St-1
St
Then prover proves that
If St-1 is valid, then St is valid.
If St-1 is optimal, then St is optimal.
If St-1 extends At-1, then St extends At.
by alg so far.
¬
codeB
85
A Sequence of Decisions
S2
S3
S1
S0
S4
S5
Sfinal
Initially with A0, no choices have been made and hence all optimal solutions extend these choices.
Establishing Loop Invariant
Alg
A3
A2
Alg
A1
Alg
A0
Alg
A4
Alg
A5
Alg
Afinal
Obj1
Obj2
Obj3
Obj4
Obj5
Objfinal
‹#›
86
An Algorithm As
A Sequence of Decisions
Exit Alg commit to or reject each object.
codeC
Has given a “solution” Afinal=S.
$ optSol Sfinal that extends Afinal.
Afinal=Sfinal must be an optSol.
Prover
S2
S3
Prover
S1
Prover
S0
Prover
S4
Prover
S5
Prover
Sfinal
Alg
A3
A2
Alg
A1
Alg
A0
Alg
A4
Alg
A5
Alg
Afinal
Obj1
Obj2
Obj3
Obj4
Obj5
Objfinal
‹#›
87
Changing St-1 into St
Here is advice on instructing how to change St-1 into St so that it extends previous & new choice.
‹#›
88
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
My little brother made a decision about Objt.
I must first tell the Fairy Godmother to make this same decision about Objt.
S’t = St-1 + At’s decision made about Objt.
Changing St-1 into St
‹#›
89
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
Changing St-1 into St
Dude! My solution St-1 had been a valid optimal solution.
and you messed it up.
Ok, I will try and fix it.
‹#›
90
Changing St-1 into St
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
I will find some object Obj’ in St-1
(but not in At) that ”conflicts” with this changed decision about Objt and describe
a way of changing the decision made by the fairy godmother about Obj’ so that the solution St is made to be again valid.
‹#›
91
Changing St-1 into St
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
Or maybe adding Objt to St-1
made it not be optimal.
I will change the decision made about
some Obj’ so that the solution St is made to be again optimal.
‹#›
92
Changing St-1 into St
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
St = St-1
+ At’s decision made about Objt
+ the prover’s new decision about Obj’.
Well done!
You made my solution St
a valid and optimal again.
‹#›
93
Past, Present, and Future
At-1 denotes the algorithm’s past
Objt denotes his present
His future is not define.
‹#›
94
Past, Present, and Future
St-1 a full solution without a time line.
St-1’s “past” is the same as At-1’s
‹#›
95
Past, Present, and Future
We make its “present” the same as the algorithm’s.
Now this solution St extends At
We do not know St’s “future”.
Don’t change this.
‹#›
96
Past, Present, and Future
Is St valid?
No conflict between these decisions because the alg did them.
No conflict between these decisions because the same.
‹#›
97
Past, Present, and Future
Is St valid?
No conflict between these decisions because St-1 is valid.
‹#›
98
Past, Present, and Future
Is St valid?
Conflict here?
Maybe
Change St’s future to fix these conflicts.
‹#›
99
Past, Present, and Future
Is St optimal?
Change St’s future to fix these conflicts.
Show that it is at least as good as St-1.
‹#›
100
The Job/Event Scheduling Problem
Schedule as
many events
in your room
as possible
‹#›
101
Ingredients:
Instances: Events with starting and finishing times <
Solutions: A set of events that do not overlap.
Cost of Solution: The number of events scheduled.
Goal: Given a set of events, schedule as many as possible.
The Job/Event Scheduling Problem
‹#›
102
Possible Criteria for Defining “Best”
The Shortest Event
Counter Example
Does not book the room
for a long period of time.
Motivation:
Optimal
Schedule first
Optimal
Greedy Criteria:
‹#›
103
Possible Criteria for Defining “Best”
The Earliest Starting Time
Counter Example
Common scheduling algorithm.
Motivation:
Optimal
Schedule first
Optimal
Greedy Criteria:
‹#›
104
Possible Criteria for Defining “Best”
Conflicting with the Fewest Other Events
Counter Example
So many can still be scheduled.
Motivation:
Schedule first
Optimal
Optimal
Greedy Criteria:
‹#›
105
Possible Criteria for Defining “Best”
Earliest Finishing Time
Schedule the event which will
free up your room for someone
else as soon as possible.
Motivation:
Works!
Greedy Criteria:
‹#›
106
Earliest Finishing Time
‹#›
107
The Greedy Algorithm
‹#›
108
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
to school
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
109
We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
Initially with A0, no choices have been made and hence all optimal solutions extend these choices.
Establishing Loop Invariant
‹#›
110
¬
codeB
Exit
Maintaining Loop Invariant
Let St-1 denote one.
$ optSol that extends At-1.
codeB
Commits or rejects the next best object.
Proof changes St-1 into St and proves it
is a valid solution
extends both previous and new choices At.
is optimal
$ optSol St that extends these choices.
‹#›
111
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices At-1.
I instruct how to change St-1 into St so that it extends previous & new choice.
I commit to keeping next event i.
Case 1
Changing St-1 into St
‹#›
112
St-1
Start by adding new event i.
Delete events conflicting with
event i.
Changing St-1 into St
‹#›
113
St-1
St-1 was valid and we removed any new conflicts.
Proving St is valid
Changing St-1 into St
‹#›
114
St-1
St-1 did extend At-1.
We added event i to be consistent
with At.
Events in Commit do not conflict with event i because the Alg has Commit and added it. Hence none of these were deleted.
Proving St extends At
Changing St-1 into St
‹#›
115
St-1
St-1 was optimal, i.e. max # events.
If we delete at most one event
then St is optimal too.
Proving St is optimal
Changing St-1 into St
‹#›
116
Changing St-1 into St
St-1
Only one in St-1.
Deleted at most one event j
j
i
St
Changing St-1 into St
Case 1
¬
codeB
Exit
Maintaining Loop Invariant
‹#›
118
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices At-1.
I reject next event i.
Changing St-1 into St
Case 2
Event i conflicts with committed to
events so can’t be in St-1 either.
‹#›
119
St-1
Changing St-1 into St
¬
codeB
Exit
Maintaining Loop Invariant
‹#›
120
Exit Clean up loose ends
codeC
Alg commit to or reject each object.
Has given a “solution” Aexit=S.
$ optSol Sexit that extends Aexit. codeC ‹#› Designing an Algorithm 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› Running Time only comparing it with the last such event. ‹#› Greedy Algorithms Don’ts We prove that the algorithm’s solution is … The algorithm has made some commitments ‹#› Greedy Algorithms Don’ts What the algorithm has done so far is optimal. ‹#› Greedy Algorithms Don’ts What is the loop invariant of We have not gone wrong. St is longer than At. St extends At. ‹#› Greedy Algorithms Don’ts We prove it extends At, is optimal, and is valid. ‹#› Greedy Algorithms Don’ts We tell the Fairy God Mother to change her Great, but what does this mean? ‹#› Greedy Algorithms Don’ts We tell the Fairy God Mother to change her Add object Objt that the algorithm took next ‹#› Greedy Algorithms Don’ts We tell the Fairy God Mother to change her Add object Objt to St if is not in St-1. ‹#› Greedy Algorithms Don’ts We tell the Fairy God Mother to change her Define St to be new solution ‹#› Greedy Algorithms Don’ts The Prover is unable to see The Prover compares the Fairy God Mother’s ‹#› Greedy Algorithms Don’ts By the LI, St-1 extends what the algorithm ‹#› Greedy Algorithms Don’ts It is true that this is important. Show that the steps taken ‹#› Greedy Algorithms Don’ts By the LI, St-1 is valid ‹#› Greedy Algorithms Don’ts It is true that this is important. Show that the steps taken by the algorithm ‹#› Greedy Algorithms Don’ts By the LI, St-1 is optimal Good ‹#› The algorithm does ‹#› Why do we change ‹#› Why do we change ‹#› Minimal Spanning Tree Click to edit Master text styles ‹#› Minimal Spanning Tree c a d f i j h g 40 1 1 Click to edit Master text styles ‹#› Minimal Spanning Tree s a d f i j h g 40 1 1 Click to edit Master text styles ‹#› 3 Minimal Spanning Tree s a d f i j h g 40 1 Must prove that this is Click to edit Master text styles ‹#› ‹#› Designing an Algorithm 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› We have not gone wrong. Initially with A0, no choices have been made and hence all optimal solutions extend these choices.
Aexit=Sexit must be an optSol.
Alg returns Aexit.
121
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
122
Greedy algorithms are very fast because they take only a small amount of time per object in the instance.
Checking whether next event i conflicts with
previously committed events requires
123
What is the loop invariant of
any greedy algorithm?
already, but this does not yet constitute
a valid solution.
124
What does this mean?
The “More of the Input” loop invariant
does not work.
What is the loop invariant of
any greedy algorithm?
125
any greedy algorithm?
There is at least one optimal solution St that extends the choices At made so far.
At extends St.
No! Extends means “to make longer”.
126
Don’t say “it” without saying what “it” is.
The loop invariant of any greedy algorithm is
“There is at least one optimal solution St that extends the choices At made so far.”
How do we prove that this loop invariant
is maintained?
127
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.
The loop invariant of any greedy algorithm is
“There is at least one optimal solution St that extends the choices At made so far.”
How do we prove that this loop invariant
is maintained?
128
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.
and delete the object Obj’t that the fairy
godmother took next.
Unlike the alg, the fairy godmother does
not make decisions about the objects in any particular order. Hence, it is meaningless to say, “Let Obj’t be the object that the fairy
godmother considered at time t.”
129
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.
We know that St-1 is a valid solution as it is.
Adding Objt makes it no longer valid.
Let object Obj’ be the object in St-1 that
“conflicts” with Objt in the following way …
Define St to be new solution
St = St-1
+ At’s decision made about Objt
+ the prover’s new decision about Obj’.
130
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.
St = St-1 + At’s decision made about Objt
+ the prover’s new decision about Obj’.
The key thing about Obj’ is that it fixes the conflict that was created in St-1
when Objt was added to it,
namely we will need to prove that though
St-1+taking Objt is not valid
St = St-1+taking Objt+not taking Obj’ is valid.
131
the Fairy God Mother’s optimal solution.
optimal solution to what the algorithm
has done.
How do we prove St extends At?
132
did in the first t-1 steps.
The Prover instructs the Fairy God Mother
to change it to St to make it consistent
with the tth step without messing up the
earlier commitments.
How do we prove St extends At?
133
But it is not what we need here.
by the algorithm are valid.
How do we prove St is valid?
134
(ie does not contain conflicts within it.)
The Prover instructs the Fairy God Mother
to change it to St in a way that provably
does not introduce conflicts.
How do we prove St is valid?
135
But it is not what we need here.
are the best choices available.
How do we prove St is optimal?
136
(ie there is not a valid solution worth more.)
The Prover instructs the Fairy God Mother
to change it to St in a way that provably
does not decrease its worth.
How do we prove St is optimal?
137
not change solutions.
It just keeps making choices.
Who are “You”?
Why do we change
the optimal solution each iteration?
138
the optimal solution each iteration?
The Prover changes St-1
in order to ensure that:
The LI is maintained
The last bridge is not burned.
139
the optimal solution each iteration?
The Prover changes St-1
in order to ensure that:
But why?
To prove that the algorithm produces
a globally optimal solution
and not just one produced by
a sequence of locally optimal choices.
140
Second level
Third level
Fourth level
Fifth level
141
Instance: A undirected graph
with weights on the edges.
s
b
1
2
15
1
6
1
30
3
30
2
2
k
2
2
4
Second level
Third level
Fourth level
Fifth level
142
c
b
1
2
15
1
6
1
30
3
30
2
2
k
Instance: A undirected graph
with weights on the edges.
Solution: A subset of edge
A tree (no cycles, not rooted)
Spanning
Connected nodes still connected.
Cost: Sum of edge weights
Goal: Find Minimal Spanning Tree
2
2
4
Second level
Third level
Fourth level
Fifth level
143
c
b
1
2
15
1
4
6
1
30
2
30
2
1
2
2
k
Instance: A undirected graph
with weights on the edges.
Solution: A subset of edge
A tree (no cycles)
Spanning
Connected nodes still connected.
Cost: Sum of edge weights
Goal: Find Minimal Spanning Tree
Greedy Alg: Commit to the edge
that looks the “best.”
Can’t add because of cycle.
acylic
spanning
optimal.
Done
Second level
Third level
Fourth level
Fifth level
144
145
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
146
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
Establishing Loop Invariant
Though one does have to prove that there exists
at least one tree that spans the graph.
‹#›
147
¬
codeB
Exit
Maintaining Loop Invariant
Let St-1 denote one.
$ optSol that extends At-1.
codeB
Commits or rejects the next best object.
Proof changes St-1 into St and proves it
is a valid solution
extends both previous and new choices At.
is optimal
$ optSol St that extends these choices.
‹#›
148
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices At-1.
I instruct how to change St-1 into St so that it extends previous & new choice.
I commit to keeping next edge .
Case 1
Changing St-1 into St
‹#›
149
St-1
Changing St-1 into St
Hey Fairy God Mother,
The algorithm just added this edge.
u
v
If the solution you hold
contains this edge,
then we are done.
‹#›
150
St-1
Changing St-1 into St
Otherwise:
Because your solution spans the graph,
it must have a path from u to v.
u
v
‹#›
St-1
Changing St-1 into St
The algorithm might have already committed to some of these edges.
u
v
Is it possible that the algorithm
has committed to all of them?
No. This gives a cycle.
‹#›
St-1
Changing St-1 into St
u
v
Before adding this edge ,
the algorithm made sure that it did not create cycle with the other edges committed to.
Hence, there is an edge in this path
that has not been committed
to by the algorithm.
‹#›
St-1
Changing St-1 into St
u
v
Before adding this edge ,
the algorithm made sure that it did not create cycle with the other edges committed to.
Hence, there is an edge in this path
that has not been committed
to by the algorithm.
u’
v’
This edge is in St-1
but not taken by the Alg.
‹#›
St-1
Changing St-1 into St
u
v
Fairy God Mother,
replace with
in St-1 to form St.
u’
v’
‹#›
St-1
Changing St-1 into St
u
v
Proving St extends At
The solution St-1 extends the previous choices At-1 made by the algorithm.
Now St extends At
with this new choice too.
u’
v’
‹#›
St-1
Changing St-1 into St
u
v
I must prove that St is
valid (i.e. acyclic and spanning)
and optimal.
u’
v’
‹#›
3
Minimal Spanning Tree
s
c
b
a
d
f
i
j
h
g
40
1
2
15
1
4
6
1
30
2
30
2
1
2
1
2
k
First lets give an example
showing more of the edges.
Suppose the algorithm has
committed to these edges.
The Fairy God Mother holds
St-1 which extends At-1.
The algorithm commits to
new edge
Prover tells Fairy God Mother to
add this new edge.
This creates a cycle in St-1.
Prover tells Fairy God Mother to
remove edge .
This gives St.
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹#›
3
Minimal Spanning Tree
s
c
b
a
d
f
i
j
h
g
40
1
2
15
1
4
6
1
30
2
30
2
1
2
1
2
k
The algorithm commits to
new edge .
Prover tells Fairy God Mother to
add this new edge.
This creates a cycle in St-1.
Prover tells Fairy God Mother to
remove edge .
This gives St.
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹#›
St-1
Changing St-1 into St
u
v
I must prove that St is
valid (i.e. acyclic and spanning)
and optimal.
u’
v’
‹#›
St-1
Changing St-1 into St
u
v
Proving St is valid
St-1 was acyclic.
We added , which created one unique cycle.
We broke it by removing .
Hence, St is acyclic.
u’
v’
‹#›
St-1
Changing St-1 into St
u
v
Proving St is valid
St-1 was spanning.
Hence, if x and y are connected in the graph than they are connected in St-1.
We may have broken the connection
by removing .
But we fixed it by adding .
Hence, St is spanning.
u’
v’
x
y
‹#›
St-1
Changing St-1 into St
u
v
Proving St is optimal.
St-1 was optimal.
We replaced with .
The cost changes by +wu,v – wu’v’.
u’
v’
wu,v
wu’,v’
‹#›
St-1
Changing St-1 into St
u
v
The algorithm chooses to take
over .
Hence, wu,v wu’,v’
u’
v’
wu,v
wu’,v’
wu,v wu’,v’
‹#›
St-1
Changing St-1 into St
u
v
We replaced with .
The cost changes by +wu,v – wu’v’.
Hence, St only improves.
St-1 was optimal.
Hence, St is optimal.
u’
v’
wu,v
wu’,v’
wu,v wu’,v’
‹#›
St-1
Changing St-1 into St
u
v
In fact, because St-1 was optimal,
it can’t improve.
Hence, wu,v = wu’v’
Multiple optimal solutions only arise from having equal weights.
u’
v’
wu,v
wu’,v’
wu,v wu’,v’
=
‹#›
3
Minimal Spanning Tree
s
c
b
a
d
f
i
j
h
g
40
1
2
15
1
4
6
1
30
2
30
2
1
2
1
2
k
Multiple optimal solutions
only arise from having equal
weights.
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹#›
St-1
St
St is valid
St extends At
St is optimal
St
Changing St-1 into St
Case 1
¬
codeB
Exit
Maintaining Loop Invariant
‹#›
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices At-1.
I reject next edge .
Changing St-1 into St
Case 2
Edge creates a cycle with the
other committed to edges so can’t
be in St-1 either.
‹#›
St-1
Changing St-1 into St
¬
codeB
Exit
Maintaining Loop Invariant
‹#› Exit Clean up loose ends
codeC
Alg commit to or reject each object.
Has given a “solution” Aexit=S.
$ optSol Sexit that extends Aexit. codeC ‹#› Designing an Algorithm 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› St-1 I want to find the minimum spanning tree for this little input. 1000 1 ‹#› St-1 This is fun. 1000 1 ‹#› St-1 Loop Invariant 1000 1 We have not gone wrong. No problem! ‹#› O(E) ‹#› 3 Minimal Spanning Tree s a d f i j h g 40 1 Click to edit Master text styles ‹#› 3 Minimal Spanning Tree s a d f i j h g 40 1 Click to edit Master text styles ‹#› 3 Minimal Spanning Tree s a d f i j h g 40 1 Can’t add because of cycle. Click to edit Master text styles ‹#› ‹#› Average Time = Akerman’s-1(E) Click to edit Master text styles ‹#› An Adaptive Algorithm s a d f i j h g 40 1 1 2 These edges are never found. Click to edit Master text styles ‹#› Adaptive Priority: ‹#› Why so restrictive? To ensure the Fixed vs Adaptive Priority ‹#› Alg Greedy Criteria: Next decision made. ‹#› One step of a greedy algorithm Alg Greedy Criteria Alg Greedy Criteria Alg Greedy Criteria Alg Greedy Criteria Alg Greedy Criteria Alg Greedy Criteria ‹#› Fixed vs Adaptive Priority ‹#› s a d f i j h g 40 1 1 2 Click to edit Master text styles ‹#› An Adaptive Algorithm ‹#› Dijkstra’s shortest weighted path algorithm can be considered to be a greedy algorithm with an adaptive priority criteria. ‹#› Greedy Alg: ‹#› Interval Point Cover ‹#› Interval Point Cover ‹#› Interval Point Cover ‹#› Interval Point Cover ‹#› Interval Point Cover ‹#› 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› Initially with A0, no choices have been made and hence all optimal solutions extend these choices.
Aexit=Sexit must be an optSol.
Alg returns Aexit.
171
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
172
It is so easy, surely my little brother can do it.
Loop Invariant
1000
I want 1000.
Loop Invariant
1000
Oops! That is a very bad edge to take!
Is there any hope for my little brother?
Has he violated the loop invariant?
1000
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
Time =
Time =
O(E log(E))
c
b
1
2
15
1
4
6
1
30
2
30
2
1
2
2
k
How does the algorithm
detect a cycle?
No cycle.
Cycle.
Second level
Third level
Fourth level
Fifth level
c
b
1
2
2
1
2
6
1
30
2
30
2
1
2
2
k
Cycle detection algorithm:
Keep track of sets of nodes
in connected components.
If edge with one component,
then new cycle.
If edge bridges two components,
then no new cycle.
Merge components.
Second level
Third level
Fourth level
Fifth level
c
b
1
2
2
1
2
6
1
30
2
30
2
1
2
2
k
Cycle detection algorithm:
Keep track of sets of nodes
in connected components.
If edge with one component,
then new cycle.
If edge bridges two components,
then no new cycle.
Merge components.
Second level
Third level
Fourth level
Fifth level
Minimal Spanning Tree
Algorithm for keeping track of components:
Union-Find Data structure.
4
Second level
Third level
Fourth level
Fifth level
for Minimal Spanning Tree
c
b
1
2
15
1
6
1
30
3
30
2
2
k
Another application: (www)
Suppose we don’t know of edges
until we find them searching
from s.
Another Greedy Alg:
Expand out from s,
committing to best edge
connected to component.
2
4
Can’t add because of cycle.
Done
Is this a greedy algorithm?
(The priorities on the edges
keep changing.)
Second level
Third level
Fourth level
Fifth level
Fixed vs Adaptive Priority
Fixed Priority:
Sort the objects from best to worst
and loop through them.
Greedy criteria depends on which objects have been committed to so far.
At each step, the next “best” object is chosen according to the current greedy criteria.
Searching or re-sorting takes too much time.
Use a priority queue.
Greedy Criteria:
The algorithm does not know the objects in the input.
But for every possible object
it assigns a real value priority.
The algorithm receives the objects from the input
in this order.
Decision Criteria:
When the algorithm receives the next object,
it knows the past but not the future objects.
It must make an irrivokable decision about this object.
algorithm is fast.
184
The algorithm does not know the future objects.
But for every possible future object
it assigns a real value priority.
The algorithm then receives
the next best object in the input.
Objt
At
At-1
Decisions made
by alg so far.
One step of a greedy algorithm
Objt
Fixed vs Adaptive Priority
185
Fixed vs Adaptive Priority
A3
A2
A1
A0
A4
A5
Afinal
Obj1
Obj2
Obj3
Obj4
Obj5
Objfinal
186
c
b
1
2
15
1
6
1
30
3
30
2
2
k
Another application: (www)
Suppose we don’t know of edges
until we find them searching
from s.
Another Greedy Alg:
Expand out from s,
committing to best edge
connected to component.
2
4
This is an adaptive greedy algorithm.
An Adaptive Algorithm
for Minimal Spanning Tree
Second level
Third level
Fourth level
Fifth level
for Minimal Spanning Tree
Another Example
Interval Point Cover
Smallest subset of the intervals
to cover the set of points.
Take interval that covers the most uncovered points.
Smallest subset of the intervals
to cover the set of points.
Greedy Alg:
Consider the leftmost uncovered point.
Of intervals that cover it,
Take the one the goes furthest to the right.
Smallest subset of the intervals
to cover the set of points.
Greedy Alg:
Consider the leftmost uncovered point.
Of intervals that cover it,
Take the one the goes furthest to the right.
Smallest subset of the intervals
to cover the set of points.
Greedy Alg:
Consider the leftmost uncovered point.
Of intervals that cover it,
Take the one the goes furthest to the right.
Smallest subset of the intervals
to cover the set of points.
Greedy Alg:
Consider the leftmost uncovered point.
Of intervals that cover it,
Take the one the goes furthest to the right.
Smallest subset of the intervals
to cover the set of points.
Greedy Alg:
Consider the leftmost uncovered point.
Done
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
Establishing Loop Invariant
‹#›
¬
codeB
Exit
Maintaining Loop Invariant
Let St-1 denote one.
$ optSol that extends At-1.
codeB
Commits or rejects the next best object.
Proof changes St-1 into St and proves it
is a valid solution
extends both previous and new choices At.
is optimal
$ optSol St that extends these choices.
‹#›
Changing St-1 into St
I have committed
to these intervals.
‹#›
Changing St-1 into St
St-1
I hold St-1 witnessing
that there is an optSol
that extends previous choices At-1.
‹#›
Changing St-1 into St
I consider these.
And commit to this interval.
‹#›
St-1
Changing St-1 into St
I instruct how to change St-1 into St so that it extends previous & new choice.
‹#›
St-1
Changing St-1 into St
Fairy God Mother,
you must have some interval that covers the point.
Yes
Replace any such interval
with our interval.
‹#›
St-1
Changing St-1 into St
Fairy God Mother,
you must have some interval that covers the point.
Replace any such interval
with our interval.
‹#›
St-1
St-1 did extend At-1.
We made St to extend the new choices At as well.
Changing St-1 into St
We did not delete previously committed to intervals because these do not cover the point in question.
‹#›
St-1
Changing St-1 into St
St-1 was optimal,
min number of intervals taken.
We added one interval
and deleted at least one.
Hence, St is just as good,
so is optimal as well.
‹#›
St-1
To prove St is valid,
we need to prove it covers
all the points.
Changing St-1 into St
‹#›
St-1
It covers these points because,
Changing St-1 into St
it extends the algorithm
and the algorithm has
covered these points.
‹#›
St-1
It covers this point because,
Changing St-1 into St
we added an interval to cover it.
‹#›
St-1
It covers these points because:
Changing St-1 into St
St-1 covered them.
Our replacement interval
extends at least as far to the right.
Hence, optLI’ covers them.
‹#›
Changing St-1 into St
I consider these.
And commit to this interval,
Because it extends farther
to the right.
‹#›
St-1
St
St is valid
St extends At
St is optimal
St
Changing St-1 into St
¬
codeB
Exit
Maintaining Loop Invariant
‹#› Exit Clean up loose ends
codeC
Alg commit to or reject each object.
Has given a “solution” Aexit=S.
$ optSol Sexit that extends Aexit. codeC ‹#› Designing an Algorithm 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› Adaptive Priority: ‹#› Start interval event: ‹#› Start interval event: ‹#› Point event: ‹#› Start interval event: ‹#› Point event: ‹#› Point event: ‹#› End interval event: ‹#› Start interval event: ‹#› Point event: ‹#› Start interval event: ‹#› Point event: ‹#› Start interval event: ‹#› Point event: ‹#› Start interval event: ‹#› Point event: ‹#› Point event: ‹#› Start interval event: ‹#› Start interval event: ‹#› Point event: ‹#› Start interval event: ‹#› Point event: ‹#› Point event: ‹#› Point event: ‹#› Done ‹#› ‹#› Communication & Entropy In thermodynamics, entropy is a measure of disorder. #Poss( ) = N #Poss( ) = Entropy( ) = log(N2) = 2 Entropy( ) ‹#› Communication & Entropy The log of number of possibilities equals the number of bits to communicate it ‹#› Communication & Entropy Tell Uncle Shannon which toy you want Bla bla bla bla bla bla Claude Shannon ‹#› Communication & Entropy 00100 Use a Huffman Code ‹#› Communication & Entropy Claude Shannon 001000101 ‹#› Communication & Entropy Claude Shannon ‹#› Communication & Entropy Claude Shannon ‹#› Ingredients: ‹#› Communication & Entropy 0.495 ‹#› Communication & Entropy 0.02 0.025 0.495 ‹#› Communication & Entropy 0.04 0.04 0.025 0.495 ‹#› Communication & Entropy 0.04 0.025 0.495 0.08 0.055 ‹#› Communication & Entropy 0.04 0.495 0.08 0.055 ‹#› Communication & Entropy 0.495 0.055 0.08 ‹#› Communication & Entropy 0.495 0.08 0.105 ‹#› Communication & Entropy 0.495 0.105 0.16 ‹#› Communication & Entropy 0.495 0.16 0.215 ‹#› Communication & Entropy 0.495 0.215 0.29 ‹#› Communication & Entropy 0.495 0.505 ‹#› Communication & Entropy 1 ‹#› Designing an Algorithm 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› We have not gone wrong. Initially with A0, no choices have been made and hence all optimal solutions extend these choices.
Aexit=Sexit must be an optSol.
Alg returns Aexit.
214
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
Fixed vs Adaptive Priority
Fixed Priority:
Sort the objects from best to worst
and loop through them.
Greedy criteria depends on which objects have been committed to so far.
At each step, the next “best” object is chosen according to the current greedy criteria.
Searching or re-sorting takes too much time.
Use a priority queue.
Implemented with Events
Add interval to priority queue.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point not covered, cover
with interval in priority queue
that extends farthest right.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point covered, do nothing.
Implemented with Events
If point covered, do nothing.
Implemented with Events
Could remove interval from priority queue,
But no harm leaving it.
Hence, we will ignore these events.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point covered, do nothing.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point not covered, cover
with interval in priority queue
that extends farthest right.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point covered, do nothing.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point not covered, cover
with interval in priority queue
that extends farthest right.
Implemented with Events
If point covered, do nothing.
Implemented with Events
Add interval to priority queue.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point covered, do nothing.
Implemented with Events
Add interval to priority queue.
Implemented with Events
If point not covered, cover
with interval in priority queue
that extends farthest right.
Implemented with Events
If point covered, do nothing.
Implemented with Events
If point covered, do nothing.
Implemented with Events
Lazare Carnot
(1803)
It is a measured as the logarithm of the number of specific ways in which the micro world may be arranged, given the macro world.
Low
entropy
High
entropy
Purpose for log
N2
= 2 log(N)
Entropy( ) = log(N)
242
Tell Uncle Lazare the location and the velocity of each particle.
01101000
In thermodynamics, entropy is a measure of disorder.
Lazare Carnot
(1803)
It is a measured as the logarithm of the number of specific ways in which the micro world may be arranged, given the macro world.
Few bits
needed
Low
entropy
Lots of bits
needed
High
entropy
243
No. Please use the minimum number of bits to communicate it.
01101000
Great, but we need a code.
011
01
1
…
011
Oops. Was that or
(1948)
244
Claude Shannon
(1948)
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
I follow the path and get
described by a binary tree.
245
(1948)
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
Use a Huffman Code
described by a binary tree.
I first get , the I start over to get
246
(1948)
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
Objects that are more likely will have shorter codes.
I get it.
I am likely to answer .
so you give it a 1 bit code.
247
(1948)
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
Pi is the probability of the ith toy.
Li is the length of the code for the ith toy.
Li
The expected number of bits sent is
= i pi Li
0.495
0.13
0.11
0.05
0.031
0.02
0.02
0.08
0.02
0.02
0.01
Pi = 0.01
We choose the code lengths Li to minimized this.
Then we call it the Entropy of
the distribution on toys.
248
Instances: Probabilities of objects
Solutions: A Huffman code tree.
Cost of Solution: The expected number of bits sent
= i pi Li
Goal: Given probabilities, find code with minimum
number of expected bits.
Communication & Entropy
249
0.025
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.05
0.03
0.02
0.02
0.08
0.02
0.02
0.015
0.01
250
0.02
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.04
0.13
0.11
0.05
0.03
0.02
0.02
0.08
251
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.05
0.03
0.02
0.02
0.08
252
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.05
0.03
0.04
253
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.05
0.04
0.08
254
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.05
0.08
0.105
255
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.08
0.16
256
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.11
0.215
257
Greedy Algorithm.
Put the objects in a priority queue sorted by probabilities.
Take the two objects with the smallest probabilities.
They should have the longest codes.
Put them in a little tree.
Join them into one object, with the sum probability.
Repeat.
0.13
0.29
258
0.505
259
1
260
Greedy Algorithm.
Done when one object
(of probability 1)
261
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
262
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant
Establishing Loop Invariant
‹#›
263
¬
codeB
Exit
Maintaining Loop Invariant
Let St-1 denote one.
$ optSol that extends At-1.
codeB
Commits or rejects the next best object.
Proof changes St-1 into St and proves it
is a valid solution
extends both previous and new choices At.
is optimal
$ optSol St that extends these choices.
‹#›
264
St-1
At-1 has merged the following trees together so far
Changing St-1 into St
0.5
0.2
0.03
0.1
0.1
0.07
‹#›
265
St-1
I hold St-1 witnessing that there is an optSol that extends previous choices At-1.
Changing St-1 into St
0.5
0.2
0.03
0.1
0.1
0.07
‹#›
266
St-1
Changing St-1 into St
0.5
0.2
0.03
0.1
0.1
0.07
I merge the two least likely objects,
i.e. insist that they be siblings
‹#›
267
St-1
Changing St-1 into St
0.5
0.2
0.03
0.1
0.1
0.07
I instruct how to change St-1 into St so that it extends previous & new choice.
‹#›
268
St-1
Changing St-1 into St
0.5
0.2
0.03
0.1
0.1
0.07
Hey Fairy God Mother,
The lowest two leaves of your tree must be siblings.
‹#›
269
St-1
Changing St-1 into St
0.5
0.2
0.03
0.1
0.1
0.07
Swap these with what the algorithm took.
‹#›
270
St-1
Changing St-1 into St
0.5
0.1
0.2
0.03
0.1
0.07
Swap these with what the algorithm took.
‹#›
271
St-1
Changing St-1 into St
0.5
0.1
0.2
0.03
0.1
0.07
Note, despite appearances,
the height and shape of this tree changes because the subtrees that the algorithm has already built have different heights and shapes.
‹#›
272
St-1
Changing St-1 into St
0.5
0.1
0.2
0.03
0.1
0.07
Proving St extends At
St-1 did extend At-1.
We merged the trees together
as the algorithm did.
‹#›
273
St-1
Changing St-1 into St
0.5
0.1
0.2
0.03
0.1
0.07
St-1 was a valid tree and we just rearranged some subtrees.
Proving St is valid
‹#›
274
St-1
Changing St-1 into St
0.5
0.1
0.2
0.03
0.1
0.07
St-1 was optimal.
We did not increased = i pi Li
because we gave things with higher pi shorter Li
Proving St is Optimal
‹#›
275
St-1
St
St is valid
St extends At
St is optimal
St
Changing St-1 into St
¬
codeB
Exit
Maintaining Loop Invariant
‹#›
276
Exit Clean up loose ends
codeC
Alg commit to or reject each object.
Has given a “solution” Aexit=S.
$ optSol Sexit that extends Aexit. codeC ‹#› Designing an Algorithm 79 km Exit Exit 79 km 75 km Exit Exit 0 km Exit ‹#› Communication & Entropy Claude Shannon Huffman’s algorithm says how to choose ‹#› Communication & Entropy Claude Shannon ‹#› Communication & Entropy Claude Shannon ‹#› Communication & Entropy Claude Shannon Giving the expected number of bits is ‹#› Communication & Entropy Claude Shannon ‹#› Entropy The Entropy H(X) is the expected number of bits to communicate the value of X. ‹#› H(XY) then is the expected number of bits to communicate the value of both X and Y. ‹#› If I tell you the value of Y, then H(X|Y) is the expected number of bits to communicate the value of X. ‹#› I(X;Y) is the number of bits that are revealed about X by me telling you Y. ‹#› ‹#› Sometimes the decision I make about an object is forced St ‹#› My job is then easy. St For example if the next edge u v Forced Moves ‹#› Logic – Horn Clauses “Mrs Peacock committed the murder”. L1 ‹#› Logic – Horn Clauses “Mrs Peacock committed the murder”. And of unnegated variables ‹#› Logic – Horn Clauses Do NOT assume this means causality: But we mean that in no universe is A true and B false Hence if is A false, then we say that the statement or A B ‹#› Logic – Horn Clauses “Mrs Peacock committed the murder”. If all on left are true, ‹#› Logic – Horn Clauses “Mrs Peacock committed the murder”. If one on left is false, ‹#› Logic – Horn Clauses “Mrs Peacock committed the murder”. ‹#› Logic – Horn Clauses “Mrs Peacock committed the murder”. ‹#› Logic – Horn Clauses L1 w K This looks hard No. Be greedy. ‹#› Logic – Horn Clauses L1 w K Start with all variables false. Negative clause: ‹#› Logic – Horn Clauses L1 w K Great. ‹#› Logic – Horn Clauses L1 w K When forced make a variable true. Positive Implications: Negative clause: ‹#› Logic – Horn Clauses L1 w K x Positive Implications: Negative clause: Excellent, ‹#› Logic – Horn Clauses L1 w K x Oops, the greedy method did not manage to satisfy all the clauses. St ‹#› Done Greedy ‹#› km /docProps/thumbnail.jpeg
Aexit=Sexit must be an optSol.
Alg returns Aexit.
277
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
to school
278
(1948)
Pi is the probability of the ith toy.
Li is the length of the code for the ith toy.
0.495
0.13
0.11
0.05
0.031
0.02
0.02
0.08
0.02
0.02
0.01
Pi = 0.01
Li
Minimize: expected number of bits sent
i pi Li
the code lengths Li.
We want a nice equation for this number.
279
(1948)
Pi is the probability of the ith toy.
Li is the length of the code for the ith toy.
0.495
0.13
0.11
0.05
0.031
0.02
0.02
0.08
0.02
0.02
0.01
Pi = 0.01
Li
1/2
1/4
1/8
1/16
1/32
1/32
Minimize: expected number of bits sent
i pi Li
Subject to i 2-Li = 1
280
(1948)
Pi is the probability of the ith toy.
Li is the length of the code for the ith toy.
0.495
0.13
0.11
0.05
0.031
0.02
0.02
0.08
0.02
0.02
0.01
Pi = 0.01
Li
Minimize: expected number of bits sent
i pi Li
Subject to i 2-Li = 1
What if relax the condition that Li is an integer?
Calculus minimizes by setting Li = log(1/pi)
Example:
Suppose all toys had probability pi = 0.031,
Then there would be 1/pi = 32 toys,
Then the codes would have length Li = log(1/pi)=5.
281
(1948)
Pi is the probability of the ith toy.
Li is the length of the code for the ith toy.
0.495
0.13
0.11
0.05
0.031
0.02
0.02
0.08
0.02
0.02
0.01
Pi = 0.01
Li
Minimize: expected number of bits sent
i pi Li
Subject to i 2-Li = 1
What if relax the condition that Li is an integer?
Calculous minimizes by setting Li = log(1/pi)
H(p) = i pi log(1/pi). (Entropy)
(The answer given by Huffman Codes
is at most one bit longer.)
282
(1948)
Let X, Y, and Z be random variables.
i.e. they take on random values according to some probability distributions.
0.495
0.13
0.11
0.05
0.031
0.02
0.02
0.08
0.02
0.02
0.01
Pi = 0.01
Li
The expected number of bits needed to communicate the value of X is …
H(p) = i pi log(1/pi). (Entropy)
H(X) = x pr(X=x) log(1/pr(X=x)).
X = toy chosen by this distribution.
283
It can be drawn as the area of this circle.
Entropy
Entropy
Note that if X and Y are independent, then knowing Y does not help and H(X|Y) = H(X)
Entropy
Note that if X and Y are independent, then knowing Y does not help and I(X;Y) = 0.
Or about Y by telling you X.
Entropy
Forced Moves
– or else the solution will be invalid when combined with previous decissions.
289
St = St-1 extends At.
I made the same previous decissions, so am forced in the same way.
creates a cycle with previous,
then I must reject it.
290
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”
L2
K
P
True/False Variables:
291
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”
L1
L2
K
P
If
then
and
and
L1 L2 K P
implies
unnegated variable
Two types of statements:
– Positive Implications
– Negative clause
292
Recall the logic statement: A B
A being true causes B to be true
or B being true causes A to be true
or C being true causes A and B to be true
( A B)
A B
is trivially true.
(or at least irrelevant).
293
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”
L1
L2
K
P
If
then
and
and
L1 L2 K P
then that on right is true.
Two types of statements:
– Positive Implications
– Negative clause
294
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”
L1
L2
K
P
If
then
and
and
L1 L2 K P
then the others don’t matter.
Two types of statements:
– Positive Implications
– Negative clause
295
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”
L1
L2
K
P
K
This simple states that K is true.
Two types of statements:
– Positive Implications
– Negative clause
296
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”
L1
L2
K
P
L3 K P
Or of negated variables
At least one of these
must be false
Two types of statements:
– Positive Implications
– Negative clause
297
L3 K P
Find a setting of the variables
that satisfies all the clauses.
L1 L2 K
x y
x
x y z
w z
x z
L1
P
z
y
L1
L3
L2
K
Only set a variable true if forced.
298
L3 K P
Find a setting of the variables
that satisfies all the clauses.
L1 L2 K
x y
x
x y z
w z
x z
L1
P
z
y
L1
L3
L2
K
Positive Implications:
If one on left is false,
clause is trivially true.
If one is false,
clause is trivially true.
299
L3 K P
Find a setting of the variables
that satisfies all the clauses.
L1 L2 K
x y
x
x y z
w z
x z
L1
P
z
y
L1
L3
L2
K
How about these
clauses?
x
300
L3 K P
Find a setting of the variables
that satisfies all the clauses.
L1 L2 K
x y
x
x y z
w z
x z
L1
P
z
y
L1
L3
L2
K
x
If one on left is false,
clause is trivially true.
If one is false,
clause is trivially true.
301
L3 K P
Find a setting of the variables
that satisfies all the clauses.
L1 L2 K
x y
x
x y z
w z
x z
L1
P
z
y
L1
L3
L2
K
If one on left is false,
clause is trivially true.
If one is false,
clause is trivially true.
all clauses are satisfied.
302
K P
Find a setting of the variables
that satisfies all the clauses.
L1 L2 K
x y
x
x y z
w z
x z
L1
P
z
y
L1
L3
L2
K
How about these clauses?
Maybe there is another way to get a solution.
We know not,
because I was forced
as well.
303
¥