程序代写代做代考 Excel algorithm data structure math

$ optSol Sexit that extends Aexit.
Aexit=Sexit must be an optSol.
Alg returns Aexit.

codeC

‹#›
71

Making Change Example
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

79 km
to school

Exit

Exit

79 km

75 km

Exit

Exit

0 km

Exit

Greedy Choice: Start by grabbing a 25 coin.
change
solutions

‹#›
72

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.
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

I will now instruct how to change St-1 into St so that it extends previous & new choice.
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

I commit to keeping a 4¢

I hold St-1.
Oops!

‹#›
74

Running Time
Greedy algorithms are very fast because they take only a small amount of time per object in the instance.

‹#›
75

Proof Greedy Algorithm Works
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

Do I take the first object?
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?

An Algorithm As
A Sequence of Decisions

Do I take the third?

‹#›
77

When the algorithm makes
an irrevocable decision
some solutions are no longer possible.

An Algorithm As
A Sequence of Decisions

The fairy god mother wants what is best for the alg.
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.

St-1

At-1

‹#›
78

When the algorithm makes
an irrevocable decision
some solutions are no longer possible.

An Algorithm As
A Sequence of Decisions

The prover is babysitting his little brother.
His job is to make sure his mom stays happy.

St-1

At-1

‹#›
79

When the algorithm makes
an irrevocable decision
some solutions are no longer possible.

An Algorithm As
A Sequence of Decisions

The fairy god mother really had in mind that he be a lawyer.
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.

St

-1
-1

At

‹#›
80

An Algorithm As
A Sequence of Decisions

Alg

Objt
At
At-1
Decisions made
by alg so far.

Next decision made.

‹#›
81

An Algorithm As
A Sequence of Decisions

Alg

A3
A2

Alg

A1

Alg

A0

Alg

A4

Alg

A5

Alg

Afinal
Obj1
Obj2
Obj3
Obj4
Obj5
Objfinal
Decisions made
by alg so far.

Next decision made.
No decisions made yet.
The final
output.
A full
solution

‹#›
82

An Algorithm As
A Sequence of Decisions

Prover

Alg

Objt
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

Decisions made
by alg so far.

At-1

‹#›
83

An Algorithm As
A Sequence of Decisions

Prover

Alg

Objt
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.

Decisions made
by alg so far.

At-1



‹#›
84

An Algorithm As
A Sequence of Decisions

Prover

Alg

Objt
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.

Decisions made
by alg so far.

At-1




¬
codeB

Exit

‹#›
85

An Algorithm As
A Sequence of Decisions

Prover
S2
S3

Prover
S1

Prover
S0

Prover
S4

Prover
S5

Prover
Sfinal








Initially with A0, no choices have been made and hence all optimal solutions extend these choices.

$ 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.

$ optSol Sexit that extends Aexit.
Aexit=Sexit must be an optSol.
Alg returns Aexit.

codeC

‹#›
121

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

‹#›
122

Running Time
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

only comparing it with the last such event.

‹#›
123

Greedy Algorithms Don’ts
What is the loop invariant of
any greedy algorithm?

We prove that the algorithm’s solution is …

The algorithm has made some commitments
already, but this does not yet constitute
a valid solution.

‹#›
124

Greedy Algorithms Don’ts

What the algorithm has done so far is optimal.
What does this mean?
The “More of the Input” loop invariant
does not work.
What is the loop invariant of
any greedy algorithm?

‹#›
125

Greedy Algorithms Don’ts

What is the loop invariant of
any greedy algorithm?

We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
At extends St.

St is longer than At.
No! Extends means “to make longer”.

St extends At.

‹#›
126

Greedy Algorithms Don’ts

We prove it extends At, is optimal, and is valid.
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

Greedy Algorithms Don’ts

We tell the Fairy God Mother to change her
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.

Great, but what does this mean?
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

Greedy Algorithms Don’ts

We tell the Fairy God Mother to change her
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.

Add object Objt that the algorithm took next
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

Greedy Algorithms Don’ts

We tell the Fairy God Mother to change her
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.

Add object Objt to St if is not in St-1.
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

Greedy Algorithms Don’ts

We tell the Fairy God Mother to change her
solution St-1 into St. We must prove
St extends At, is optimal, and is valid.

Define St to be new solution
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

Greedy Algorithms Don’ts

The Prover is unable to see
the Fairy God Mother’s optimal solution.

The Prover compares the Fairy God Mother’s
optimal solution to what the algorithm
has done.
How do we prove St extends At?

‹#›
132

Greedy Algorithms Don’ts

By the LI, St-1 extends what the algorithm
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

Greedy Algorithms Don’ts

It is true that this is important.
But it is not what we need here.

Show that the steps taken
by the algorithm are valid.
How do we prove St is valid?

‹#›
134

Greedy Algorithms Don’ts

By the LI, St-1 is valid
(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

Greedy Algorithms Don’ts

It is true that this is important.
But it is not what we need here.

Show that the steps taken by the algorithm
are the best choices available.
How do we prove St is optimal?

‹#›
136

Greedy Algorithms Don’ts

By the LI, St-1 is optimal
(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?

Good

‹#›
137

The algorithm does
not change solutions.
It just keeps making choices.
Who are “You”?
Why do we change
the optimal solution each iteration?

‹#›
138

Why do we change
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

Why do we change
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

Minimal Spanning Tree

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
141

Minimal Spanning Tree
Instance: A undirected graph
with weights on the edges.
s

c
b

a

d

f

i

j

h

g

40
1
2
15
1
6
1
30
3
30

1
2

1
2
k
2
2
4

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
142

Minimal Spanning Tree

s
c
b

a

d

f

i

j

h

g

40
1
2
15
1
6
1
30
3
30

1
2

1
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

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
143

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
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.

Must prove that this is
acylic
spanning
optimal.
Done

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›
144

‹#›
145

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

‹#›
146

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.

$ optSol Sexit that extends Aexit.
Aexit=Sexit must be an optSol.
Alg returns Aexit.

codeC

‹#›
171

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

‹#›
172

St-1

I want to find the minimum spanning tree for this little input.
It is so easy, surely my little brother can do it.
Loop Invariant

1000

1
1000

‹#›

St-1

This is fun.
I want 1000.
Loop Invariant

1000

1
1000
Oops! That is a very bad edge to take!
Is there any hope for my little brother?
Has he violated the loop invariant?

‹#›

St-1

Loop Invariant

1000

1
1000

We have not gone wrong.
There is at least one optimal solution St that extends the choices At made so far.
Loop Invariant

No problem!

‹#›

O(E)
Time =
Time =
O(E log(E))

‹#›

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
How does the algorithm
detect a cycle?
No cycle.
Cycle.

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
2
1
2
6
1
30
2
30
2
1
2

1
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.

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
2
1
2
6
1
30
2
30
2
1
2

1
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.

Can’t add because of cycle.

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›

‹#›
Minimal Spanning Tree
Algorithm for keeping track of components:
Union-Find Data structure.

Average Time = Akerman’s-1(E)
 4

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›

An Adaptive Algorithm
for Minimal Spanning Tree

s
c
b

a

d

f

i

j

h

g

40
1
2
15
1
6
1
30
3
30

1
2

1
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
2
4
Can’t add because of cycle.

These edges are never found.
Done
Is this a greedy algorithm?
(The priorities on the edges
keep changing.)

Click to edit Master text styles
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.

Adaptive Priority:
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.

Why so restrictive?

To ensure the
algorithm is fast.

Fixed vs Adaptive Priority

‹#›
184

Alg

Greedy Criteria:
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.

Next decision made.
One step of a greedy algorithm
Objt
Fixed vs Adaptive Priority

‹#›
185

One step of a greedy algorithm
Fixed vs Adaptive Priority

Alg

Greedy Criteria
A3
A2

Alg

Greedy Criteria
A1

Alg

Greedy Criteria
A0

Alg

Greedy Criteria
A4

Alg

Greedy Criteria
A5

Alg

Greedy Criteria
Afinal
Obj1
Obj2
Obj3
Obj4
Obj5
Objfinal

‹#›
186

Fixed vs Adaptive Priority

‹#›

s
c
b

a

d

f

i

j

h

g

40
1
2
15
1
6
1
30
3
30

1
2

1
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
2
4
This is an adaptive greedy algorithm.
An Adaptive Algorithm
for Minimal Spanning Tree

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

‹#›

An Adaptive Algorithm
for Minimal Spanning Tree

‹#›
Another Example

Dijkstra’s shortest weighted path algorithm can be considered to be a greedy algorithm with an adaptive priority criteria.

‹#›
Interval Point Cover
Smallest subset of the intervals
to cover the set of points.

Greedy Alg:
Take interval that covers the most uncovered points.

‹#›

Interval Point Cover
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.

‹#›

Interval Point Cover
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.

‹#›

Interval Point Cover
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.

‹#›

Interval Point Cover
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.

‹#›

Interval Point Cover
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

79 km
to school

Exit

Exit

79 km

75 km

Exit

Exit

0 km

Exit

‹#›
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.

$ optSol Sexit that extends Aexit.
Aexit=Sexit must be an optSol.
Alg returns Aexit.

codeC

‹#›
214

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

‹#›
Fixed vs Adaptive Priority
Fixed Priority:
Sort the objects from best to worst
and loop through them.

Adaptive Priority:
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

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point not covered, cover
with interval in priority queue
that extends farthest right.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

End interval event:
Could remove interval from priority queue,
But no harm leaving it.
Hence, we will ignore these events.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point not covered, cover
with interval in priority queue
that extends farthest right.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point not covered, cover
with interval in priority queue
that extends farthest right.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Start interval event:
Add interval to priority queue.

‹#›
Implemented with Events

Point event:
If point not covered, cover
with interval in priority queue
that extends farthest right.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Point event:
If point covered, do nothing.

‹#›
Implemented with Events

Done

‹#›

‹#›

Communication & Entropy

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.
Low
entropy
High
entropy
Purpose for log

#Poss( ) = N
N2
= 2 log(N)

#Poss( ) =
Entropy( ) = log(N)

Entropy( ) = log(N2)

= 2 Entropy( )

‹#›
242

Communication & Entropy
Tell Uncle Lazare the location and the velocity of each particle.

The log of number of possibilities equals the number of bits to communicate it
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

Communication & Entropy

Tell Uncle Shannon which toy you want

Bla bla bla bla bla bla
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

 Claude Shannon
(1948) 

‹#›
244

Communication & Entropy

00100
 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

Use a Huffman Code
described by a binary tree.

‹#›
245

Communication & Entropy

 Claude Shannon
(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.

001000101
I first get , the I start over to get

‹#›
246

Communication & Entropy

 Claude Shannon
(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

Communication & Entropy

 Claude Shannon
(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

Ingredients:
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

Communication & Entropy
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.495
0.13
0.11
0.05
0.03
0.02
0.02
0.08
0.02
0.02
0.015
0.01

‹#›
250

Communication & Entropy

0.02
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.025
0.04

0.495
0.13
0.11
0.05
0.03
0.02
0.02
0.08

‹#›
251

Communication & Entropy
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.04

0.025

0.495
0.13
0.11
0.05
0.03
0.02
0.02
0.08

‹#›
252

Communication & Entropy
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.025

0.495
0.13
0.11
0.05
0.03
0.04

0.08

0.055

‹#›
253

Communication & Entropy
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.495
0.13
0.11
0.05
0.04

0.08

0.055
0.08

‹#›
254

Communication & Entropy
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.495
0.13
0.11
0.05
0.08

0.055

0.08
0.105

‹#›
255

Communication & Entropy
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.495
0.13
0.11
0.08

0.08

0.105
0.16

‹#›
256

Communication & Entropy
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.495
0.13
0.11

0.105

0.16
0.215

‹#›
257

Communication & Entropy
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.495
0.13

0.16

0.215
0.29

‹#›
258

Communication & Entropy

0.495

0.215

0.29
0.505

‹#›
259

Communication & Entropy

0.495

0.505
1

‹#›
260

Communication & Entropy

1
Greedy Algorithm.
Done when one object
(of probability 1)

‹#›
261

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

‹#›
262

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.

$ optSol Sexit that extends Aexit.
Aexit=Sexit must be an optSol.
Alg returns Aexit.

codeC

‹#›
277

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

‹#›
278

Communication & Entropy

 Claude Shannon
(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

Huffman’s algorithm says how to choose
the code lengths Li.
We want a nice equation for this number.

‹#›
279

Communication & Entropy

 Claude Shannon
(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

Communication & Entropy

 Claude Shannon
(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

Communication & Entropy

 Claude Shannon
(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)

Giving the expected number of bits is
H(p) = i pi  log(1/pi). (Entropy)
(The answer given by Huffman Codes
is at most one bit longer.)

‹#›
282

Communication & Entropy

 Claude Shannon
(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

Entropy

The Entropy H(X) is the expected number of bits to communicate the value of X.
It can be drawn as the area of this circle.

‹#›
Entropy

H(XY) then is the expected number of bits to communicate the value of both X and Y.

‹#›
Entropy

If I tell you the value of Y, then H(X|Y) is the expected number of bits to communicate the value of X.
Note that if X and Y are independent, then knowing Y does not help and H(X|Y) = H(X)

‹#›
Entropy

I(X;Y) is the number of bits that are revealed about X by me telling you Y.
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

Sometimes the decision I make about an object is forced
– or else the solution will be invalid when combined with previous decissions.

St

‹#›
289

My job is then easy.
St = St-1 extends At.

St
I made the same previous decissions, so am forced in the same way.

For example if the next edge
creates a cycle with previous,
then I must reject it.

u

v

Forced Moves

‹#›
290

Logic – Horn Clauses
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”

“Mrs Peacock committed the murder”.

L1 
L2 
K 
P 
True/False Variables:

‹#›
291

Logic – Horn Clauses
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”

“Mrs Peacock committed the murder”.
L1 
L2 
K 
P 
If
then
and
and
L1  L2  K  P

And of unnegated variables
implies
unnegated variable
Two types of statements:
– Positive Implications
– Negative clause

‹#›
292

Logic – Horn Clauses
Recall the logic statement: A  B

Do NOT assume this means causality:
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

But we mean that in no universe is A true and B false
( A  B)

Hence if is A false, then we say that the statement
A  B
is trivially true.

or A  B
(or at least irrelevant).

‹#›
293

Logic – Horn Clauses
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”

“Mrs Peacock committed the murder”.
L1 
L2 
K 
P 
If
then
and
and
L1  L2  K  P

If all on left are true,
then that on right is true.
Two types of statements:
– Positive Implications
– Negative clause

‹#›
294

Logic – Horn Clauses
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”

“Mrs Peacock committed the murder”.
L1 
L2 
K 
P 
If
then
and
and
L1  L2  K  P

If one on left is false,
then the others don’t matter.
Two types of statements:
– Positive Implications
– Negative clause

‹#›
295

Logic – Horn Clauses
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”

“Mrs Peacock committed the murder”.
L1 
L2 
K 
P 
 K
This simple states that K is true.
Two types of statements:
– Positive Implications
– Negative clause

‹#›
296

Logic – Horn Clauses
“Mrs Peacock loves Colonel Mustard”
“Colonel Mustard loves Miss Scarlet”
“it happened in the kitchen”

“Mrs Peacock committed the murder”.
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

Logic – Horn Clauses
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

L1  w  K

This looks hard

No. Be greedy.
Only set a variable true if forced.

‹#›
298

Logic – Horn Clauses
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

L1  w  K

Start with all variables false.
Positive Implications:
If one on left is false,
clause is trivially true.

Negative clause:
If one is false,
clause is trivially true.

‹#›
299

Logic – Horn Clauses
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

L1  w  K

Great.
How about these
clauses?
x

‹#›
300

Logic – Horn Clauses
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

L1  w  K

When forced make a variable true.
x

Positive Implications:
If one on left is false,
clause is trivially true.

Negative clause:
If one is false,
clause is trivially true.

‹#›
301

Logic – Horn Clauses
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

L1  w  K

x

Positive Implications:
If one on left is false,
clause is trivially true.

Negative clause:
If one is false,
clause is trivially true.

Excellent,
all clauses are satisfied.

‹#›
302

Logic – Horn Clauses
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

L1  w  K

x

Oops, the greedy method did not manage to satisfy all the clauses.
How about these clauses?
Maybe there is another way to get a solution.

St
We know not,
because I was forced
as well.

‹#›
303

Done Greedy

‹#›

km
¥

/docProps/thumbnail.jpeg