程序代写代做代考 algorithm math

math

Recursive Back Tracking
&
Dynamic Programming
Jeff Edmonds York University

COSC 3101
Lecture 7
Thinking about Algorithms Abstractly

‹#›
1

Optimization Problems
A Sequence of Decisions
The Little Bird & Friend
Memoization
Set of Sub-Instances
Tracing Dyn. Prog. Alg
Reversing
Code
Speeding Up Running Time
Multiple Opt Solutions
Review
Optimal Substructure
Question for Little Bird
Review & Don’ts
Bellman Ford
Best Path
Printing Neatly
Longest Common Subsequence
Knapsack Problem
The Event Scheduling Problem
Parsing
Satisfiability
Techniques
Problems

‹#›
2

Consider your instance I.
Ask a little question (to the little bird) about its optimal solution.
Try all answers k.
Knowing k about the solution
restricts your instance to a subinstance subI.
Ask your recursive friend for a optimal solution subsol for it.
Construct a solution optS = subsol + k
for your instance that is the best of those consistent with the kth bird’ s answer.
Return the best of these best solutions.

Recursive Back Tracking

‹#›
3

Specification: All Nodes Shortest-Weighted Paths : The input is a graph G (directed or undirected)
with edge weights (possibly negative) : For each u,v, find a shortest path from u to v
Stored in a matrix Dist[u,v].

b
d
c

u

k

g

i

v

h

40
1
10
2
15
181
2
6
8
1
2
30
3
25
1
2

3

For a recursive algorithm,
we must give our friend
a smaller subinstance.
How can this instance be
made smaller?
Remove a node? and edge?
Recursive Back Tracking
Bellman Ford
with ≤l edges
and integer l.
with at most l edge.
l=3
l=4

‹#›
4

b
d
c

u

k

g

i

v

h

40
1
10
2
15
181
2
6
8
1
2
30
3
25
1
2

3

Recursive Back Tracking
Bellman Ford
l=4
Consider your instance I = u,v,l.
Ask a little question (to the little bird) about its optimal solution.
“What node is in the middle of the path?”
She answers node k.
I ask one friend subI = u,k, l/2
and another subI = k,v, l/2
optS = subsolu,k,l/2
+ k +
subsolk,v,l/2
is the best solution for I
consistent with the kth bird‘s
answer.
Try all k and return the best
of these best solutions.

‹#›
5

Dynamic Programming Algorithm
Given an instance I,
Imagine running the recursive alg on it.
Determine the complete set of subI
ever given to you, your friends, their friends, …
Build a table indexed by these subI
Fill in the table in order so that nobody waits.
Recursive Back Tracking

Given graph G, find Dist[uv,l] for l =
1,2,4,8,…

b
d
c

u

k

g

i

v

h

40
1
10
2
15
181
2
6
8
1
2
30
3
25
1
2

3

l=4

,n
Generally
Exponential
Time
Hopefully
Polynomial
Time

‹#›
6

b
d
c

u

k

g

i

v

h

40
1
10
2
15
181
2
6
8
1
2
30
3
25
1
2

3

l=4

Dynamic Programming Algorithm
Loop Invariant: For each u,v,
Dist[u,v,l] = a shortest path from u to v with ≤l edges

Exit

for l = 2,4,8,16,…,2n
for all u,v  Verticies
% Find Dist[uv,l] from Dist[u,v,l/2]
Dist[u,v,l] = mink ( Dist[u,k,l/2]+Dist[k,v,l/2] )
Time = O(n3 logn)

‹#›
7

b
d
c

u

k

g

i

v

h

40
1
10
2
15
181
2
6
8
1
2
30
3
25
1
2

3

l=4

Dynamic Programming Algorithm
Loop Invariant: For each u,v,
Dist[u,v,l] = a shortest path from u to v with ≤l edges

When l = 1, Dist[b,c,1] =
10
Dist[u,v,1] =

% Smallest Instances
for all u,v  Verticies
if u,v  Edges
Dist[u,v,1] = weight[u,v]
else
Dist[u,v,1] = ∞
Dist[u,u,1] =
0 (sometimes useful)

‹#›
8

b
d
c

u

k

g

i

v

h

40
1
10
2
15
181
2
6
8
1
2
30
3
25
1
2

3

l=4

Dynamic Programming Algorithm
Loop Invariant: For each u,v,
Dist[u,v,l] = a shortest path from u to v with ≤l edges

Exit

When to exit?
A simple path never uses a node more than once
and so does not have more than l=n-1.
for all u,v  Verticies
Dist[u,v] = Dist[u,v,n]

‹#›
9

Dynamic Programming Algorithm
Dealing with negative cycles.

b
d
c

u
v
-5
1
2
25

3
Dist[u,v,2] =

Dist[u,v,3] =
25+3+2 = 30
Dist[u,v,6] =
25+(3+1-5)+3+2 = 29
Dist[u,v,1] =

Dist[u,v,9] =
25+(3+1-5)2+3+2 = 28
Dist[u,v,303] =
25+(3+1-5)100+3+2 = 30-100 = -70
Dist[u,v,∞] =
25+(3+1-5)∞+3+2 = -∞
There is a negative cycle if
Dist[u,v,n] > Dist[u,v,2n]
% Check for negative cycles
for all u,v  Verticies
if( Dist[u,v,2n]: The input is one instance. :
The output is one of the valid solutions for this instance with optimal cost.
(minimum or maximum)
The solution might not be unique.
Be clear about these ingredients!
Optimization Problems

‹#›
16

Search Graph For Best Path
We use it because it nicely demonstrates
the concepts in a graphical way.

‹#›
17

Search Graph For Best Path

An instance (input) consists of .
G is a weighted directed layered graph
s source node
t sink node

5
3
4

2
5
3
3
2
2
1
2

4

‹#›
18

Search Graph For Best Path
An instance (input) consists of .

The cost of a solution is the sum of the weights.

2+6+3+7=18
A solution for an instance is a path from s to t.

The goal is to find a path with minimum total cost.

4+2+1+5=12

‹#›
19

Brute Force Algorithm

But there may be an exponential number of paths!

Try all paths, return the best.

‹#›
20

An Algorithm As
A Sequence of Decisions
“Which edge should we take first?”
Some how I decide .

I ask a question about the solution.
“Which edge do we take second?”
Some how he decides .
My friend asks the next question.
“Which edge do we take third?”
Some how he decided .
His friend asks the next question.

‹#›
21

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 algorithm?
Does not work!
Taking the best first edge.

‹#›
22

Local vs Global Considerations
We are able to make local observations and choices.
Eg. Which edge out of s is cheapest?
But it is hard to see the global consequences
Which path is the overall cheapest?
Sometimes a local initial sacrifice can globally
lead to a better overall solution.

‹#›
23

An Algorithm As
A Sequence of Decisions

“Which edge should we take first?”
I ask a question about the solution.
How do I decide?
But let’s skip this part
by pretending that we have
a little bird to answer this
little question.

In reality we will try
all possible first edges.

‹#›
24

“Little Bird” Abstraction
Recall: Non-deterministic Finite Automata
Non-deterministic Turing Machine

0

The little bird is a little higher power,
answering a little question about an
optimal solution.

These have a higher power to tell them
which way to go.
(It is up to you whether or not to use it)

‹#›
25

“Which edge should we take first?”
The bird answers .
I ask a question about the solution.
“Which edge do we take second?”
The bird answers .
My friend asks the next question.
But we don’t want to
worry about how our friend
solves his problem.

Little Bird & Friend Alg

‹#›
26

Sub-Instance for Friend

Our instance is : Find best path from s to t.
Our friend is recursion
i.e. he is a smaller version of ourselves
we can trust him to give us a correct answer
as long as we give him
a smaller instance
of the same problem.
What sub-instance do
we give him?

‹#›
27

“Which is the best path from v1 to t?”

I tack on the bird’s edge making the path

Friend answers
with weight 10.

If I trust the little bird, I take step along edge
and ask my friend,
The bird answers .
To get my solution

with weight
10+3=13.
Little Bird & Friend Alg

‹#›
28

Faulty Bird

But what if we do not have a bird that we trust?
i.e. the best path from s to t
from amongst those
starting with .
This work is not wasted, because we have found
Define optS to be:
the optimum solution
for instance I
consistent with the kth bird’ s answer.

the best solution to our instance
from amongst those
consistent with this bird’ s answer.

‹#›
29

Faulty Bird

But what if we do not have a bird that we trust?
This work is not wasted, because we have found
In reality we will try
all possible first edges,
giving …..

the best solution to our instance
from amongst those
consistent with this bird’ s answer.
i.e. the best path from s to t
from amongst those
starting with .

‹#›
30

…the best path from amongst
those starting with .
Faulty Bird

‹#›
31

… and the best path from amongst
those starting with .
Faulty Bird

‹#›
32

… and the best path from amongst
those starting with .
Faulty Bird

‹#›
33

… and the best path from amongst
those starting with .
Faulty Bird

‹#›
34

At least one of these four paths must be an over all best path.

I give the best of the best
as the best path.

Faulty Bird

‹#›
35

Bird/Friend – Best of the Best
A sequence of question to
a little bird about a solution
forms a tree of possible
answers.
Consider our instance I.
Consider the set of solutions

‹#›
36

Bird/Friend – Best of the Best
But we only care about
the first bird answer.
Consider our instance I.
Consider the set of solutions

The answers classifies
the possible solutions.

Solutions consistent
with the kth bird’ s answer.
k
k

‹#›
37

Bird/Friend – Best of the Best
Consider our instance I.
Consider the set of solutions

Solutions consistent
with the kth bird’ s answer.
k
Define optS to be:
the optimum solution
for instance I
consistent with the kth bird’ s answer.
Do this for each k.

optS

‹#›
38

Bird/Friend – Best of the Best
Consider our instance I.
Consider the set of solutions

Let kmax be the bird’ s answer
giving the best optS.
Define optS to be:
the optimum solution
for instance I
consistent with the kth bird’ s answer.
Do this for each k.

k

optS
kmax
optS[I] = optS = Bestk optS
max

optS[I]

‹#›
39

Bird/Friend – Best of the Best
Constructing optS :
the optimum solution
for instance I
consistent with the kth bird’ s answer.

Given my instance I.

I ask my little bird for
an answer k.
I ask my friend for his solution.
I combine them.

‹#›
40

Recursive
backtracking
code always has this
same basic structure.

‹#›
41

Be clear what are
the instances
it’s solution
the cost of a sol.

‹#›
42

Loop through the
bird answers.
Be clear which is
the current one
being tried.

‹#›
43

Give the bird
& friend algorithm
as a comment.
(Unless it is in
an earlier question.)

‹#›
44

What is the bird
asked?
What does she
answer?

‹#›
45

Get help from friend
Be clear what
sub-instance
you give him.

Store the solution
& cost
he gives you.

‹#›
46

How do you form
your solution from
the friend’s and from
the bird’s?

‹#›
47

How do you form
your cost from
the friend’s and from
the bird’s?

‹#›
48

Take the best
of the best

optSolk
is a best solution
for our instance
from amongst
those consistent
with the bird’s
kth answer.

‹#›
49

Return the solution
and cost for the
original instance.

‹#›
50

Base Cases:
Instances that are too
small to have smaller
instances to give
to friends.
What are these?
What are their
solutions
and costs?

‹#›
51

i.e. for a path from s to t to be optimal,
the sub-path from vi to t must optimal.

In order to be able to design a recursive backtracking algorithm for a computational problem,
the problem needs to have an optimal substructure,
If  shorter from vi to t.
  shorter to s to t.
Optimal Substructure

‹#›
52

i.e. for a path from s to t to be optimal,
the sub-path from vi to t must optimal.

In order to be able to design a recursive backtracking algorithm for a computational problem,
the problem needs to have an optimal substructure,
And finding such a sub-path is a
sub-instance of the same
computational problem.
Optimal Substructure

‹#›
53

Time?

I try each edge out of s.
Same as the brute force algorithm
that tries each path.
A friend tries each edge
out of these.

A friend tries each edge
out of these.

Same as Brute Force Algorithm

‹#›
54

Same as Brute Force Algorithm

But there may be an exponential number of paths!

‹#›
55

Why do all this work with birds & friends?
How else would you iterate through all paths?
But sometimes we can exploit the structure
to speed up the algorithm.

Speeding Up the Time

‹#›
56

Perhaps because these solutions are not valid
or not highly valued.
Sometimes entire an branch can be pruned off.
Or because there is at least one optimal solution elsewhere in the tree.
A Greedy algorithm prunes off all branches except the one that looks best.

Speeding Up the Time

‹#›
57

Remembers the solutions for the sub-instances
so that if ever it needs to be solved again,
the answer can be used.
This effectively prunes off this later branch of the classification tree.
Speeding Up the Time
Memoization

‹#›
58

Exponential Time
Redoing Work

“Which is the best path from v7 to t?”

How many friends solve this sub-instance?

‹#›
59

Exponential Time
Redoing Work

“Which is the best path from s to t?”

‹#›
60

Exponential Time
Redoing Work

“Which is the best path from v1 to t?”

‹#›
61

Exponential Time
Redoing Work

“Which is the best path from v4 to t?”

‹#›
62

Exponential Time
Redoing Work

“Which is the best path from v7 to t?”

There’s one.

‹#›
63

Exponential Time
Redoing Work

“Which is the best path from s to t?”

‹#›
64

Exponential Time
Redoing Work

“Which is the best path from v3 to t?”

‹#›
65

Exponential Time
Redoing Work

“Which is the best path from v5 to t?”

‹#›
66

Exponential Time
Redoing Work

“Which is the best path from v7 to t?”

There’s another.

‹#›
67

Exponential Time
Redoing Work

“Which is the best path from v7 to t?”

How many friends solve this sub-instance?

Once for each
path to v7
Save time by only doing once.
Waste time redoing work

‹#›
68

Drop
bread crumbs
and don’t revisit.
Depth First
Search
But we need
shortest path

‹#›
69

Having many friends
solving this same sub-instance
is a waste of time.
We allocate one friend to the job.

Dynamic Programming

‹#›
70

It is my job to learn
and remember
the optSol to my sub-Instance
i.e. the best path from v7 to t
Dynamic Programming

‹#›
71

When I need to find
the best path from v4 to t
I will ask you for
the best path from v7 to t

I will find my best path
and tell you.

Dynamic Programming

‹#›
72

When I need to find
the best path from v2 to t
I will ask you for
the best path from v7 to t

I remember my best path
and will tell you.

Dynamic Programming

‹#›
73

When I need to find
the best path from v5 to t
I will ask you for
the best path from v7 to t

I remember my best path
and will tell you.

Dynamic Programming

‹#›
74

But I hate to wait for you.
Recursion has a lot of overhead
Why don’t you go first?

I will find my best path
and tell you.
Dynamic Programming
When I need to find
the best path from v2 to t
I will ask you for
the best path from v7 to t
Avoid waiting.

‹#›
75

Dynamic Programming
Before anyone asks me,
I will find my best path
and remember it.

‹#›
76

Set of Sub-Instances

But what sub-instance need to be solved
and
in which order?
Imagine running the recursive algorithm on it.

Determine the complete set of sub-Instances ever given to you, your friends, their friends, …
Given an instance I,

‹#›
77

Guess the complete set S of sub-Instances.
“Best path from v7 to t?”
Yes
“Best path from v21 to t?”
No

v21

v21 is not a part of our
original instance.
Set of Sub-Instances

‹#›
78

Guess the complete set S of sub-Instances.
“Best path from v7 to t?”
Yes
“Best path from v3 to v7?”
No

“Best path from v21 to t?”
No
All paths considered
end in t.
Set of Sub-Instances

‹#›
79

Guess the complete set S of sub-Instances.
“Best path from v7 to t?”
Yes
“Best path from v3 to v7?”
No
“Best path from v21 to t?”
No
All paths considered
end in t.

Set of Sub-Instances

‹#›
80

Guess the complete set S of sub-Instances.
“Best path from v7 to t?”
Yes
“Best path from v3 to v7?”
No
“Best path from v21 to t?”
No

“Best path from vi to t?”
 i
Set of Sub-Instances
Yes

‹#›
81

Guess the complete set S of sub-Instances is
“Best path from vi to t?”
 i
Set of Sub-Instances

Assign one friend
to each sub-Instance.

‹#›
82

Guess the complete set S of sub-Instances is
“Best path from vi to t?”
 i
Set of Sub-Instances
The set S of sub-Instances needs to:
include our given I

‹#›
83

Guess the complete set S of sub-Instances is
“Best path from vi to t?”
 i
Set of Sub-Instances
closed under “friend” operation
Integers closed under addition
 x,y  I  x+y  I
 sub-Instance  S 
subsub-Instance  S
The set S of sub-Instances needs to:
include our given I

‹#›
84

Guess the complete set S of sub-Instances is
“Best path from vi to t?”
 i
Set of Sub-Instances
closed under “friend” operation
The set S of sub-Instances needs to:
include our given I
each sub-Instance needs to be
asked of some friend, friend, …

‹#›
85

Guess the complete set S of sub-Instances is
“Best path from vi to t?”
 i
Set of Sub-Instances
closed under “friend” operation
The set S of sub-Instances needs to:
include our given I
each sub-Instance needs to be
asked of some friend, friend, …
A fine set of sub-instances!

‹#›
86

The complete set S of sub-Instances is
“Best path from vi to t?”
 i
Order to complete

in an order such that
no friend must wait.
from “smallest” to “largest”
In what order should they go?
For this problem,
the order relies on
the graph being “leveled.”

‹#›
87

The complete set S of sub-Instances is
“Best path from vi to t?”
 i
in an order such that
no friend must wait.
from “smallest” to “largest”
In what order should they go?
Order to complete
First
Last

Base Case easy

Instance to be solved.

‹#›
88

Dynamic Programming

“Which is the best path from t to t?”

Base Case
easy

‹#›
89

Dynamic Programming

“Which is the best path from v8 to t?”

easy

‹#›
90

Dynamic Programming

“Which is the best path from v7 to t?”

easy

‹#›
91

Dynamic Programming

“Which is the best path from v6 to t?”

easy

‹#›
92

Dynamic Programming

“Which is the best path from v5 to t?”

Harder

‹#›
93

Dynamic Programming

“Which is the best path from v5 to t?”
Friend gives best
path .
Little bird suggests first edge

‹#›
94

Dynamic Programming

“Which is the best path from v5 to t?”
Friend gives best
path .
Little bird suggests first edge

‹#›
95

Dynamic Programming

“Which is the best path from v5 to t?”

Take best of best

‹#›
96

Dynamic Programming
“Which is the best path from v4 to t?”

‹#›
97

Dynamic Programming
“Which is the best path from v4 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
98

Dynamic Programming
“Which is the best path from v4 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
99

Dynamic Programming
“Which is the best path from v4 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
100

Dynamic Programming
“Which is the best path from v4 to t?”

Take best of best

‹#›
101

Dynamic Programming
“Which is the best path from v3 to t?”

‹#›
102

Dynamic Programming
“Which is the best path from v3 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
103

Dynamic Programming
“Which is the best path from v3 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
104

Dynamic Programming
“Which is the best path from v3 to t?”

Take best of best

‹#›
105

Dynamic Programming

“Which is the best path from v2 to t?”

‹#›
106

Dynamic Programming

“Which is the best path from v2 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
107

Dynamic Programming

“Which is the best path from v2 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
108

Dynamic Programming

“Which is the best path from v2 to t?”

Take best of best

‹#›
109

Dynamic Programming
“Which is the best path from v1 to t?”

‹#›
110

Dynamic Programming
“Which is the best path from v1 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
111

Dynamic Programming
“Which is the best path from v1 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
112

Dynamic Programming
“Which is the best path from v1 to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
113

Dynamic Programming
“Which is the best path from v1 to t?”

Take best of best

‹#›
114

Dynamic Programming
“Which is the best path from s to t?”

Original Problem

‹#›
115

Dynamic Programming
“Which is the best path from s to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
116

Dynamic Programming
“Which is the best path from s to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
117

Dynamic Programming
“Which is the best path from s to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
118

Dynamic Programming
“Which is the best path from s to t?”

Friend gives best
path .
Little bird suggests first edge

‹#›
119

Dynamic Programming
“Which is the best path from s to t?”

Take best of best
DONE

‹#›
120

Construct a table
for storing an optimal solution & cost
for each sub-instance.
Dynamic Programming
Sub-Instances
Map
Indexes
Cell of table

“Best path from vi to t?”
 i
 i ϵ [n], i.e. for each node vi

t, v8, v7, v6, v5, …., s
i
“Which is the best path from vi to t?”

‹#›
121

Fill out a table containing
an optimal solution for each sub-instance.
“Which is the best path from vi to t?”
Dynamic Programming

t, v8, v7, v6, v5, …., s
Base case
Original

‹#›
122

Communication
optSubSol = optSol[k]
Friend k gives friend i a best path from vk to t.
Recursive BackTracking

= LeveledGraph()
optSol[k] = optSolmin
return(optSolmin,optCostmin) ,
Dynamic Programming

k

i

k

i

k

i
optSoli,k = + optSol[k]
optSol[i] = bestk + optSol[k]
loopi
Alg:
optSol[0] = 0

‹#›
123

set up table
base cases
loop over subsinstances
loop over bird answers
bird
take
optSol[0] = 0

friend algorithm
the best
of the best
Code of every
Dynamic Programming
Algorithm!
optSol[i] = bestk + optSol[k]
loopi
Alg:

‹#›
124

Dynamic
Programming
code always has this
same basic structure.

‹#›
125

Be clear what are
the instances
it’s solution
the cost of
a solution.

‹#›
126

Dynamic Programs
do not recurse making
the instance smaller
and smaller.
Instead, it up front
determines the set S
of all sub-instances
that ever need
to be solved.
Be clear what
sub-instances are.

‹#›
127

Be clear what
sub-instances are.

How are they indexed?

Tables indexed by
these sub-instances
store an optimal
solution and it’s cost.

‹#›
128

The set S
of sub-instances
are solved from
smallest to largest
so that no body waits.

Base Cases:
Instances that are too
small to have smaller
instances to give
to friends.
They get solved first
and their solutions
stored.

‹#›
129

Then we iterate
through the remaining
sub-instances.

From smallest
to largest.

Each gets solved
and their solutions
stored.

‹#›
130

Consider yourself
to be a friend
working on one
of these.

Be clear which
sub-instance is yours.

Solve this as you
did before.

‹#›
131

Loop through the
bird answers.
Be clear which is
the current one
being tried.

‹#›
132

Give the bird
& friend algorithm
as a comment.
(Unless it is in
an earlier question.)

‹#›
133

What is the bird
asked?
What does she
answer?

‹#›
134

Be clear what
sub-instance
you give your friend.

k
k
k
k
Get help from friend

‹#›
135

Instead of recursing,
we simply look
in the table
for the solution.

Because his instance
is smaller, he has
already solved it and
stored sol in the table.

Get help from friend

k
k
k
k

‹#›
136

How do you form
your solution from
the friend’s and from
the bird’s?

‹#›
137

How do you form
your cost from
the friend’s and from
the bird’s?

‹#›
138

Take the best
of the best

optSol
is a best solution for
our instance subI[i]
from amongst
those consistent
with the bird’s
kth answer.

‹#›
139

Store the solution to
our instance subI[i]
in the table.

‹#›
140

Base Cases:
Instances that are too
small to have smaller
instances to give
to friends.

Is this code correct?

‹#›
141

Dynamic Programs
do not recurse making
the instance smaller
and smaller.
Hence, lets not worry
about our instance I
being a base case.

‹#›
142

But there is a table
of subinstances
that must be solved.

Some of these will be
base cases
and their solutions
must be stored
in the table.

‹#›
143

But there is a table
of subinstances
that must be solved.
Some of these will be
base cases
and their solutions
must be stored
in the table.

n
n
n
n
t=

‹#›
144

But there is a table
of subinstances
that must be solved.
Then we solve
the rest.

‹#›
145

Return the solution
and cost for the
original instance.

0
0
0
n
s=

‹#›
146

Order Feels Backwards

Path from t to t.
Path from s to t.

‹#›
147

An Esthetically Better

Path from s to s.
Path from s to t.

‹#›
148

Reversing

‹#›
149

Reversing

Determine the complete set of sub-instances

“Which is the best path from s to vi?”
 i

‹#›
150

Reversing
Fill out a table containing
an optimal solution for each sub-instance.

s, v1, v2, v3, v4, …., t
“Which is the best path from s to vi?”
Base case
Original

‹#›
151

‹#›
152

Running Time
# of Sub-Instances
× # of Bird Answers

× q(1)
Time =
?

= n
× d

‹#›
153

Communication Time

optSolk =
Friend k gives best path from s to vk
to friend i, who adds the edge .

k
i
q(1)
Time =
?

Size of path =
q(n)
Time =
q(n).

‹#›
154

# of Sub-Instances
× # of Bird Answers
× size of solution
= q(n × d × n)
Time =
Running Time

Store path costs,
not paths

Space =
# of Sub-Instances
× q(1)
= q(n)

‹#›
155

“What is cost of the best path from s to v7?”

Store Path Costs, not Paths

‹#›
156

Friend gives cost 8
of best path .
Little bird suggests last
edge with weight 2.

8
Best cost via is 8+2=10.
“What is cost of the best path from s to v7?”
Store Path Costs, not Paths

‹#›
157

Friend gives cost 2
of best path .
Little bird suggests last
edge with weight 7.

2
Best cost via is 2+7=9.
“What is cost of the best path from s to v7?”
Store Path Costs, not Paths

‹#›
158

Friend gives cost 6
of best path .
Little bird suggests last
edge with weight 5.

Best cost via is 6+5=11.

6
“What is cost of the best path from s to v7?”
Store Path Costs, not Paths

‹#›
159

Take best of best:
“What is cost of the best path from s to v7?”
Store Path Costs, not Paths
We also learn
the wise little bird’s advice.
We will store this in the table too.

9

2
10, 9, 11

‹#›
160

Running Time

birdsAdvice[i] = kmin

‹#›
161

Leave these lines
as comments
for extra clarity
for the reader

‹#›
162

Find Optimal Path

Previous algorithm gives:
Cost of the best path
from s to vi,  i.
Bird’s advice of
last edge to vi.
We run the bird-friend
algorithm again,
but with a reliable bird.

‹#›
163

Find Optimal Path

The bird gives that
the last edge
of the best path from
s to t is .

‹#›
164

Find Optimal Path

The bird gives that
the last edge
of the best path from
s to v8 is .

‹#›
165

Find Optimal Path

The bird gives that
the last edge
of the best path from
s to v5 is .

‹#›
166

Find Optimal Path

The bird gives that
the last edge
of the best path from
s to v3 is .

‹#›
167

Find Optimal Path

Done!

‹#›
168

Find Optimal Path

This could be done iteratively.
As an exercise, design it.

‹#›
169

Multiple Optimal Solutions

6
“Which is the last edge?”
I ask the bird:

She could give either answer.
By giving this edge she says
“There exists an optimal solution
consistent with this answer.”
Similar to greedy proof.

‹#›
170

Multiple Optimal Solutions

6
“Which is the last edge?”
I ask the bird:

We try all the bird answers.

When we try this bird answer,
we find this best solution.
When we try this bird answer,
we find this best solution.
When we take best of best,
we choose between them.

‹#›
171

Designing Recursive Back Tracking Algorithm
What are instances, solutions, and costs?
Given an instance I,
What question do you ask the little bird?
Given a bird answer k  [K],
What instance sub-Instance do your give your friend?
Assume he gives you optSubSol for subI.
How do you produce an optSol for I from
the bird’s k and
the friend’s optSubSol?
How do you determine the cost of optSol from
the bird’s k and
the cost of the friend’s optSubSol?
Try all bird’s answers and take best of best.

Review

‹#›
172

Recursive Back Tracking Algorithm

Dynamic Programming Algorithm
Given an instance I,
Imagine running the recursive alg on it.
Determine the complete set of sub-Instances
ever given to you, your friends, their friends, …
Build a table indexed by these sub-Instances
Fill in the table in order so that nobody waits.
the cost of its optimal solution
advice given by the bird
Run the recursive alg with bird’s advice to find
the solution to your instance.
Review

‹#›
173

Purpose of Little Bird:
An abstraction from which it is
easier to focus on the difficult issues.
Her answers give us a list of things to try.
Temporarily trusting the bird,
helps us focus on the remaining question
helping us formulate sub-instance for friend.
Coming up with which question is one of the main creative steps.
Hint: Ask about a local property
There are only so many question that you might ask so just try them all.
The Question For the Little Bird

‹#›
174

An instance: Graph, s, and t
The Question For the Little Bird
I ask the bird:

A solution: a path

s
t

“What is the first edge in the path?”
The Dynamic Programming reverses the recursive backtracking algorithm.
Hence, to end up with a “forward order”,
we first reverse the recursive backtracking algorithm.

‹#›
175

An instance: Graph, s, and t
The Question For the Little Bird
I ask the bird:

A solution: a path

s
t

The Dynamic Programming reverses the recursive backtracking algorithm.
Hence, to end up with a “forward order”,
we first reverse the recursive backtracking algorithm.
“What is the last edge in the path?”

‹#›
176

A good question for the bird leaves you
with a good recursive sub-instance to ask your friend.

An instance: Graph, s, and t
The Question For the Little Bird
I ask the bird:

A solution: a path

s
t

“What is the last edge in the path?”

“What is the rest of the path?”

‹#›
177

An instance: Graph, s, and t
The Question For the Little Bird
I ask the bird:

A solution: a path

s
t

Giving a good follow up question for your friend to ask the bird.
“What is the last edge in the path?”

“What is the second last edge in the path?”

‹#›
178

You can only ask the bird a little question.
Together with your question, you provide the little bird with a list A1, A2, …, AK of possible answers.
The little bird answers, k  [1..K].
For an efficient algorithm, K must be small.
The Question For the Little Bird
number of edges into node t.

K
K =
Eg. “What is best last edge?”

s
t

‹#›
179

You can only ask the bird a little question.
Together with your question, you provide the little bird with a list A1, A2, …, AK of possible answers.
The little bird answers, k  [1..K].
For an efficient algorithm, K must be small.
The Question For the Little Bird
Trying all is the Brute Force algorithm.
K =
Eg. “What is an optimal solution?”

# of solutions.

‹#›
180

An instance: Graph, s, and t
The Question For the Little Bird
I ask the bird:

A solution: a path

s
t

“How many edges are in the path?”
Bad Question:
it is not a local property
How does this help us solve the problem?
What is a good follow up question for the friend to ask?

‹#›
181

A solution: a sequence of objects
Z = a b c d
An instance: ???
The Question For the Little Bird
“What is the last object in the sequence?”
I ask the bird:

# of answers K =
# of possible last objects.
I ask my friend:

“What is the rest of the solution?”

‹#›
182

The Question For the Little Bird
“What is the last object in the sequence?”
I ask the bird:

An instance: a sequence of objects
X = a s b e f c h d a
A solution: a subset of these objects
Z = a b c d
X = a s b e f c h d a
# of answers K =
# of possible last objects.
Is there a smaller question that we could ask?

‹#›
183

The Question For the Little Bird
“Is the last object of the instance included
in the optimal solution?”
I ask the bird:

An instance: a sequence of objects
X = a s b e f c h d a
A solution: a subset of these objects
Z = a b c d
# of answers K =
2, Yes or No

‹#›
184

An instance: ???
The Question For the Little Bird
“What object is at the root?”
I ask the bird:

A solution: a binary tree of objects
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71

I ask my friend:

“What is the left sub-tree?”

I ask a second friend:

“What is the right sub-tree?”

Previous problems had one friend given a bird ans.

‹#›
185

A solution: a binary tree of objects
An instance: ???
The Question For the Little Bird
“What object is at a leaf?”
I ask the bird:

38
25
17
4
21
31
28
35
51
42
40
49
63
55
71

Bad Question:
How does this help us solve the problem?
What is a good follow up question for the friend to ask?

‹#›
186

i.e. for a path from s to t to be optimal,
the sub-path from vi to t must optimal.

In order to be able to design a recursive backtracking algorithm for a computational problem,
the problem needs to have an optimal substructure.
Optimal Substructure
And finding such a sub-path is a
sub-instance of the same
computational problem.

‹#›
187

Optimal substructure means that
Every optimal solution to a problem contains…
…optimal solutions to subproblems
Optimal substructure does not mean that
If you have optimal solutions to all subproblems…
…then you can combine any of them to get an optimal solution to a larger problem.
Example: In Canadian coinage,
The optimal solution to 7¢ is 5¢ + 1¢ + 1¢, and
The optimal solution to 6¢ is 5¢ + 1¢, but
The optimal solution to 13¢ is not 5¢ + 1¢ + 1¢ + 5¢ + 1¢
But there is some way of dividing up 13¢ into subsets with optimal solutions (say, 11¢ + 2¢) that will give an optimal solution for 13¢
Hence, the making change problem exhibits optimal substructure.
Optimal Substructure

‹#›
188

Don’t all problems have this optimal substructure property?
Optimal Substructure

‹#›
189

Longest simple path
Consider the following graph:
The longest simple path (path not containing a cycle) from A to D is A B C D
However, the subpath A B is not the longest simple path from A to B (A C B is longer)
The principle of optimality is not satisfied for this problem
Hence, the longest simple path problem cannot be solved by a dynamic programming approach
A
C
D
B
4
2
3
1
1
NP-Complete
Optimal Substructure

‹#›
190

Failed Algorithm
Lets make a small change in the cost of a solution.
And have the same dynamic programming algorithm fail!
Optimal Substructure

‹#›
191

Optimal Substructure

= 118
My input is this sequence of objects.

My solution is a partitioning of them.

The cost is the sum of cost of parts.

I ask the bird
for the last part.
I ask my friend to solve the rest.
8 + 40 + 60 +
cost1 = 10

‹#›
192

Optimal Substructure
cost1 = 8 + 40 + 60
cost1 = 8 +20+ 30 + 42

= 108
= 100

Suppose I have two solutions to choose between.
By recursive magic,
I take the one with smaller cost.
cost1 = 10

‹#›
193

Optimal Substructure
cost1 = 8 +20+ 30 + 42 + 10
cost1 = 8 + 40 + 60
cost1 = 8 +20+ 30 + 42

= 110
= 108
= 100
Diff = 8

Does not change
which is min
Diff = 8

My solution will be my friend’s combined with my bird’s.
My cost will be the sum of theirs.
But how do I know this is optimal?
I could have taken my friend’s other solution.

= 118
Don’t worry.
Adding in the bird’s answer does not change which is the minimum.

8 + 40 + 60 +
cost1 = 10

‹#›
194

Optimal Substructure
cost1 = 8 + 40 + 60 + 10
cost2 = (# parts) = 4
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42 + 10
cost2 = (# parts) = 5
cost = cost1 + cost2
cost1 = 8 + 40 + 60
cost2 = (# parts) = 3
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42
cost2 = (# parts) = 4
cost = cost1 + cost2

= 118
= 4
= 122
= 110
= 5
= 115
= 108
= 3
= 111
= 100
= 4
= 104

Lets change the cost to include
the # of parts.

Don’t worry.
One more part does not change which is the minimum.
Diff = 1

Does not change
which is min
Diff = 1

By recursive magic,
I take the one with smaller cost.

‹#›
195

Optimal Substructure
cost1 = 8 + 40 + 60 + 10
cost2 = 1 + 1 + 1 + 1
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42 + 10
cost2 = 1 + 1+ 1 + 1 + 1
cost = cost1 + cost2
cost1 = 8 + 40 + 60
cost2 = 1 + 1 + 1
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42
cost2 = 1 + 1+ 1 + 1
cost = cost1 + cost2

= 118
= 4
= 122
= 110
= 5
= 115
= 108
= 3
= 111
= 100
= 4
= 104

The part count can be added into the cost of the part.

Don’t worry.
One more part does not change which is the minimum.
Diff = 1

Does not change
which is min
Diff = 1

By recursive magic,
I take the one with smaller cost.

‹#›
196

Optimal Substructure

Lets change the cost to include
the (# of parts)2.

Problem!
New cost is global and nonlinear.
Diff = 9

Does change
which is min
Diff = 7

By recursive magic,
I take the one with smaller cost.
cost1 = 8 + 40 + 60 + 10
cost2 = (# parts)2 = 42
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42 + 10
cost2 = (# parts)2 = 52
cost = cost1 + cost2
cost1 = 8 + 40 + 60
cost2 = (# parts)2 = 32
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42
cost2 = (# parts)2 = 42
cost = cost1 + cost2
= 118
= 16
= 134
= 110
= 25
= 135
= 108
= 9
= 117
= 100
= 16
= 116
This mean DP fails
Because my friend’s solution is not right for my instance!

‹#›
197

Printing Neatly

‹#›
198

Printing Neatly
An instance: text to print neatly & # chars per line
“Love life man while there as we be”, 11
The goal is to to print it as “neatly” as possible.
The cost: a measure of how neat,
Love.life..
man.while..
there……
as.we.be…

11
A solution: # of words to put on each line.
few blanks on the end of each line.
2
2
6
3
3 = 8
3 = 8
3 = 216
3 = 27
259

small punishment

big punishment

‹#›
199

Brute Force Algorithm
But there may be an exponential number of ways to!

Try all ways to print, return the best.
love.life..
man……..
love…….
life.man…
love…….
life.man…
love.life..
man……..

‹#›
200

Bird & Friend Algorithm
“How many words on the last line?”
I ask the bird:

She may answer 3.

An instance:
“Love life man while there as we be”, 11
“Which is the best way to print
the remaining n-3 words?”
I ask the friend:

I combine
bird’s and
friend’s answers.

‹#›
201

Even if the bird was wrong, this work is not wasted.
This is best way to print from
amongst those ending in 3 words.
Bird & Friend Algorithm
An instance:
“Love life man while there as we be”, 11

We try the bird
answers words,

1

2

3

4

5
and take best of best.

‹#›
202

Time?

I try each # words on last line.
Same as the brute force algorithm
that tries each path.
A friend tries # on next.

A friend tries # on next.

Same as Brute Force Algorithm

‹#›
203

Memoization
Assign one friend to each sub-instance.

“Which is the best path from vi to t?”
 i

‹#›
204

Set of Sub-Instances
Given an instance I,

Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …

Determine the complete set of sub-Instances.
“Love life man while there as we be”, 11

‹#›
205

Set of Sub-Instances
Guess the complete set of sub-Instances.

“Love life man while there”, 11

Yes
“Hi there”, 81

No
“man while”, 11

No
This may appear on a line,
but it will never be a sub-Instance for a friend.
“Love life man while there as we be”, 11

‹#›
206

Set of Sub-Instances
“Love life man while there as we be”, 11

The set of sub-Instances is the set of prefixes.
closed under “friend” operation
 sub-Instance  S 
The set S of sub-Instances needs to:
include our given I

“Love life man while there”, 11

“Love life man while”, 11

“Love life man”, 11

“Love life”, 11

“Love”, 11

“”, 11

“Love life man while there as”, 11

“Love life man while there as we”, 11

‹#›
207

Set of Sub-Instances
“Love life man while there as we be”, 11

closed under “friend” operation
 sub-Instance  S 
subsub-Instance  i
The set S of sub-Instances needs to:
include our given I
The bird
answers words,

1

2

3

4

5
“Love life man while there”, 11
“Love life man while”, 11
“Love life man”, 11
“Love life”, 11
“Love”, 11
“”, 11
“Love life man while there as”, 11
“Love life man while there as we”, 11
The set of sub-Instances is the set of prefixes.

‹#›
208

Set of Sub-Instances
“Love life man while there as we be”, 11

closed under “friend” operation
The set S of sub-Instances needs to:
include our given I
each sub-Instance needs to be
asked of some friend, friend, …
“Love life man while there”, 11
“Love life man while”, 11
“Love life man”, 11
“Love life”, 11
“Love”, 11
“”, 11
“Love life man while there as”, 11
“Love life man while there as we”, 11
The set of sub-Instances is the set of prefixes.

‹#›
209

Set of Sub-Instances
“Love life man while there as we be”, 11

“Love life man while there as we”, 11

“Love life man while there as”, 11

“Love life man while there”, 11

closed under “friend” operation
The set S of sub-Instances needs to:
include our given I
each sub-Instance needs to be
asked of some friend, friend, …
The bird
answers 1.

“Love life man while”, 11

A fine set of sub-instances!
The set of sub-Instances is the set of prefixes.

‹#›
210

Set of Sub-Instances
“Love life man while there as we be”, 11

Base Case easy
Instance to be solved.

in an order such that
no friend must wait.
from “smallest” to “largest”
In what order should they go?
First
Last
“Love life man while there”, 11

“Love life man while”, 11

“Love life man”, 11

“Love life”, 11

“Love”, 11

“”, 11

“Love life man while there as”, 11

“Love life man while there as we”, 11

The set of sub-Instances is the set of prefixes.

‹#›
211

Construct a table
for storing the cost of opt sol and bird’s advice.
for each sub-instance.
Sub-Instances
Map
Indexes
Cell of table

 i ϵ [n], i.e. for each word.

i
“Which is the best printing of first i words?”
The set of prefixes of words.
The Table

‹#›
212

Dynamic Programming
Fill out a table containing
an optimal solution for each sub-instance.

“Which is the best printing of first i words?”
Base case
Original

‹#›
213

“Love life man while there as we be”, 11

“Love life man while there”, 11

The 5th sub-instance is
5 words
with 4, 4, 3, 5, 5 letters.

‹#›
214

“Love life man while there as we be”, 11

“Love life man while there”, 11
The 5th sub-instance is

Love.life..
man.while..
there……
Its solution is
with 2,2,1 words on each line.

The bird’s advice is 1 word on last.

Solution’s cost is
23 + 23 +63 = 232

‹#›
215

“Love life man while there as we be”, 11
Assume the table is filled in so far.
We will work to fill in the last line

‹#›
216

“Love life man while there as we be”, 11

be………

Love.life..
man.while..
there.as.we

‹#›
217

“Love life man while there as we be”, 11

we.be……

Love.life..
man.while..
there.as…

‹#›
218

“Love life man while there as we be”, 11

as.we.be…

Love.life..
man.while..
there……

‹#›
219

“Love life man while there as we be”, 11
there.as.we.be

‹#›
220

“Love life man while there as we be”, 11

Choose best of the best.
Tried all bird
answers.

‹#›
221

Choose best of the best.

“Love life man while there as we be”, 11

‹#›
222

Dynamic
Programming
code always has this
same basic structure.
Amusingly,
when formatting
this code, I had to fight
with line breaks to get
the height/width ratio
Printing Neatly.

‹#›
223

Be clear what are
the instances
it’s solution
the cost of
a solution.

‹#›
224

Dynamic Programs
do not recurse making
the instance smaller
and smaller.
Instead, it up front
determines the set S
of all sub-instances
that ever need
to be solved.
Be clear what
sub-instances are.

‹#›
225

Be clear what
sub-instances are.

How are they indexed?

Tables indexed by
these sub-instances
store an optimal
solution and it’s cost.

‹#›
226

The set S
of sub-instances
are solved from
smallest to largest
so that no body waits.
Base Cases:
Instances that are too
small to have smaller
instances to give
to friends.
They get solved first
and their solutions
stored.

‹#›
227

Then we iterate
through the remaining
sub-instances.

From smallest
to largest.

Each gets solved
and their solutions
stored.

Actually, we store the
bird’s advice instead
of the solution.

‹#›
228

Consider yourself
to be a friend
working on one
of these.

Be clear which
sub-instance is yours.

Solve this as you
did before.

‹#›
229

Loop through the
bird answers.
Be clear which is
the current one
being tried.

‹#›
230

Give the bird
& friend algorithm
as a comment.
(Unless it is in
an earlier question.)

‹#›
231

What is the bird
asked?
What does she
answer?

‹#›
232

Be clear what
sub-instance
you give your friend.

i-k
i-k
i-k
Get help from friend

‹#›
233

Instead of recursing,
we simply look
in the table
for the solution.

Because his instance
is smaller, he has
already solved it and
stored sol in the table.

i-k
i-k
i-k

‹#›
234

How do you form
your solution from
the friend’s and from
the bird’s?

‹#›
235

How do you form
your cost from
the friend’s and from
the bird’s?

‹#›
236

Take the best
of the best

optSol
is a best solution for
our instance subI[i]
from amongst
those consistent
with the bird’s
kth answer.

‹#›
237

Store the solution to
our instance subI[i]
in the table.

Actually, we store the
bird’s advice instead
of the solution.

‹#›
238

Base Cases:
Instances that are too
small to have smaller
instances to give
to friends.

Is this code correct?

‹#›
239

Dynamic Programs
do not recurse making
the instance smaller
and smaller.
Hence, lets not worry
about our instance I
being a base case.

‹#›
240

But there is a table
of subinstances
that must be solved.

Some of these will be
base cases
and their solutions
must be stored
in the table.

‹#›
241

But there is a table
of subinstances
that must be solved.
Some of these will be
base cases
and their solutions
must be stored
in the table.

‹#›
242

But there is a table
of subinstances
that must be solved.
Then we solve
the rest.

‹#›
243

But actually,
we don’t have
the solution.
We must rerun it,
this time with advice
from the bird.

Return the solution
and cost for the
original instance.

‹#›
244

Time =

# of Sub-Instances
× # of Bird Answers
= q(n × n)
Space =
# of Sub-Instances
= q(n)

‹#›
245

Find Optimal Path
Previous algorithm gives cost and bird’s advice.
We run the bird-friend algorithm again,
but with a reliable bird.

‹#›
246

“Love life man while there as we be”, 11

<2 Love.life.. ,1 there…… ,2 man.while.. ,3>
as we be…

‹#›
247

Printing Neatly

Failed Algorithm
Lets make a small change in the cost for this problem.
And have the same dynamic programming algorithm fail!

‹#›
248

Failed DP Algorithm
cost1 = 8 + 40 + 60 + 10

= 118
My input is this sequence of objects.

My solution is a partitioning of them.

The cost is the sum of cost of parts.

I ask the bird
for the last part.
I ask my friend to solve the rest.

‹#›
249

Failed DP Algorithm
cost1 = 8 + 40 + 60 + 10
cost1 = 8 + 40 + 60
cost1 = 8 +20+ 30 + 42

= 118
= 108
= 100

Suppose I have two solutions to choose between.
By recursive magic,
I take the one with smaller cost.

‹#›
250

Failed DP Algorithm
cost1 = 8 + 40 + 60 + 10
cost1 = 8 +20+ 30 + 42 + 10
cost1 = 8 + 40 + 60
cost1 = 8 +20+ 30 + 42

= 118
= 110
= 108
= 100
Diff = 8

Does not change
which is min
Diff = 8

Suppose I have two solutions to choose between.
By recursive magic,
I take the one with smaller cost.

‹#›
251

Failed DP Algorithm
cost1 = 8 + 40 + 60 + 10
cost2 = (# parts)2 = 42
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42 + 10
cost2 = (# parts)2 = 52
cost = cost1 + cost2
cost1 = 8 + 40 + 60
cost2 = (# parts)2 = 32
cost = cost1 + cost2
cost1 = 8 +20+ 30 + 42
cost2 = (# parts)2 = 42
cost = cost1 + cost2

= 118
= 16
= 134
= 110
= 25
= 135
= 108
= 9
= 117
= 100
= 16
= 116
Diff = 8

Does not change
which is min
Diff = 8

My input is this sequence of objects.

I then prove P(x)

My solution is a portioning of them.

I ask the bird
for the last part.

I ask the bird
for the last part.

‹#›
252

Longest Common Subsequence problem
X = a s b e f c h d a
Y = r t w a b g j c k t f d

‹#›
253

The goal is to find a longest common subsequence.
The cost: The length of Z.
A solution: A common subsequence.
Z = a b c d
Longest Common Subsequence problem
An instance: Two strings
X = a s b e f c h d a
Y = r t w a b g j c k t f d
X = a s b e t c h d a
Y = r t w a b g j c k t f d

‹#›
254

Bird & Friend Algorithm
I ask the bird:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers one of :
Last of X is not included
Last of Y is not included
Last of X is included
Last of Y is included
Neither are included
Both are included

‹#›
255

Bird & Friend Algorithm
I ask the bird:

I ask my friend:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X is not included

The instance:
X = a s b e t c h d
Y = r t w a b g j c k t f d

‹#›
256

Bird & Friend Algorithm
I ask the bird:

My friend answers:
I combine
bird’s and
friend’s answers
and give

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X is not included

The instance:
X = a s b e t c h d
Y = r t w a b g j c k t f d
Z = a b c d
X = a s b e t c h d
Y = r t w a b g j c k t f d
the same Z.

‹#›
257

Bird & Friend Algorithm
I ask the bird:

I ask my friend:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of Y is not included

The instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f

‹#›
258

Bird & Friend Algorithm
I ask the bird:

My friend answers:
I combine
bird’s and
friend’s answers
and give

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of Y is not included

The instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f
Z = a b c
X = a s b e t c h d a
Y = r t w a b g j c k t f
the same Z.
Not as good as last
but we need to try.

‹#›
259

Bird & Friend Algorithm
I ask the bird:

An instance:
X = a s b e t c h d
Y = r t w a b g j c k d f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X and last of Y are both included
I ask my friend:

The instance:
X = a s b e t c h
Y = r t w a b g j c k d f

Last chars equal

‹#›
260

Bird & Friend Algorithm
I ask the bird:

An instance:
X = a s b e t c h d
Y = r t w a b g j c k d f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X and last of Y are both included

The instance:
X = a s b e t c h
Y = r t w a b g j c k d f

I combine
bird’s and
friend’s answers
and give

Zd = abcd.
Last chars equal
Z = a b c
X = a s b e t c h
Y = r t w a b g j c k d f
My friend answers:

‹#›
261

Bird & Friend Algorithm
I ask the bird:

I politely tell her that she is wrong.
An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X and last of Y are both included
Last chars not equal

‹#›
262

Bird & Friend Algorithm
I ask the bird:

I ask my friend:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X is included

The instance:
X = a s b e t c h d
Y = r t w a b g j c k t f d

‹#›
263

Bird & Friend Algorithm
I ask the bird:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X is included

I combine
bird’s and
friend’s answers
and give

Za = abcda.
The instance:
X = a s b e t c h d
Y = r t w a b g j c k t f d
Z = a b c d
X = a s b e t c h d
Y = r t w a b g j c k t f d
My friend answers:

Wrong

‹#›
264

Bird & Friend Algorithm
I ask the bird:

I ask my friend:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X is included

The instance:
X = a s b e t c h d
Y = r t w

‹#›
265

Bird & Friend Algorithm
I ask the bird:

My friend answers:
I combine
bird’s and
friend’s answers
and give

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers:
Last of X is included

The instance:
X = a s b e t c h d
Y = r t w
Z = t
X = a s b e t c h d
Y = r t w
Za = ta.

‹#›
266

Bird & Friend Algorithm
I ask the bird:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers one of :
Last of X is not included
Last of Y is not included
Last of X is included
Last of Y is included
Neither are included
Both are included
Last chars not equal
Given any optSol
she needs to have
a valid answer.
Can we eliminate
some of her answers?
?

?

?

‹#›
267

Bird & Friend Algorithm
I ask the bird:

An instance:
X = a s b e t c h d a
Y = r t w a b g j c k t f d
“Is the last character of either X or Y included in Z?”
She answers one of :
Last of X is not included
Last of Y is not included
Last of X is included
Last of Y is included
Neither are included
Both are included
Last chars not equal

# of answers K =
3

‹#›
268

Time?

Same as the brute force algorithm
that tries each solution.

Same as Brute Force Algorithm

I try each of 3 bird ans.
My friends try 3
His friends try 3

‹#›
269

Memorization
Assign one friend to each sub-instance.

“Which is the best path from vi to t?”
 i

‹#›
270

Set of Sub-Instances
Given an instance I,

Determine the complete set of sub-Instances.
X = a s b e t c h d a
Y = r t w a b g j c k t f d
Imagine running the recursive alg on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends…
X’ = a s b e t c
Y’ = r t w a b g j c k
Is this a sub-Instance?

Yes

‹#›
271

Set of Sub-Instances
Given an instance I,

Determine the complete set of sub-Instances.
X = a s b e t c h d a
Y = r t w a b g j c k t f d
Imagine running the recursive alg on it.
Determine the complete set of sub-Instances ever given to you, your friends, their
friends, …
Is this a sub-Instance?
No
X’ = b e t
Y’ = a b g j c k

‹#›
272

Set of Sub-Instances
Given an instance I,

Determine the complete set of sub-Instances.
X = a s b e t c h d a
Y = r t w a b g j c k t f d
Imagine running the recursive alg on it.
Determine the complete set of sub-Instances ever given to you, your friends, their
friends, …
Is this a sub-Instance?
Yes
X’ = x1,…xi
Y’ = y1,…,yj
 i  [0..|X|]
 j  [0..|Y|]
|X| × |Y| of these.

‹#›
273

Set of Sub-Instances
Guess the complete set S of sub-Instances.

 i  [0..|X|]
 j  [0..|Y|]
Xi = x1,…xi
Yj = y1,…,yj
The set S of sub-Instances needs to:
include our given I
Yes: i = |X| & j = |Y|

‹#›
274

Set of Sub-Instances
Guess the complete set S of sub-Instances.

 i  [0..|X|]
 j  [0..|Y|]
Xi = x1,…xi
Yj = y1,…,yj
The set S of sub-Instances needs to:
include our given I
closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
Xi = x1,…xi
Yj = y1,…,yj
 S 
Xi-1 = x1,…xi-1 Yj = y1,…,yj
Xi = x1,…xi Yj-1 = y1,…,yj-1
Xi-1 = x1,…xi-1 Yj-1 = y1,…,yj-1
 S

‹#›
275

Set of Sub-Instances
Guess the complete set S of sub-Instances.

 i  [0..|X|]
 j  [0..|Y|]
Xi = x1,…xi
Yj = y1,…,yj
The set S of sub-Instances needs to:
include our given I
closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
each sub-Instance needs to be
asked of some friend, friend, …
We showed this.
This is a fine set of sub-Instances!

‹#›
276

Construct a table
for storing the cost of opt sol and bird’s advice.
for each sub-instance.
Sub-Instances
Map
Indexes
Cell of table

i
“LCS of x1,…xi and y1,…,yj ?”
 i  [0..|X|]
 j  [0..|Y|]
Xi = x1,…xi
Yj = y1,…,yj
j
The Table

‹#›
277

The Table

‹#›
278

Table

X
Y
Original instance
I =

‹#›
279

Table
Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

Xi
Yj

j=
i=
Cost = length of LCS.

Optimal Solution
= Longest Common
Subsequence

‹#›
280

Table
Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

Xi
Yj

Optimal Solution
= Longest Common
Subsequence
Bird’s Advice
delete xi

‹#›
281

Table

Xi
Yj

Optimal Solution
= Longest Common
Subsequence
Bird’s Advice
delete xi

take both xi and yj

Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
282

Table

Xi
Yj

Optimal Solution
= Longest Common
Subsequence

Bird’s Advice
delete xi
delete yj
take both xi and yj
Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
283

Fill in Box

Xi
Yj
Fill in box
Try all bird’s ans.

delete xi
Friend’s sub-Instance
Our cost
= friend’s cost

5

Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
284

Xi
Yj
Fill in box
Try all bird’s ans.

delete yj
Friend’s sub-Instance
Our cost
= friend’s cost

5

Fill in Box
Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
285

Xi
Yj
Fill in box
Try all bird’s ans.

take both xi and yj
Friend’s sub-Instance
Our cost
= friend’s cost
+1

6
Fill in Box

Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
286

Xi
Yj
Fill in box
Try all bird’s ans.
Take best of best

6
Fill in Box
Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
287

Fill in Box

Xi
Yj
Fill in box
Try all bird’s ans.
delete xi
Friend’s sub-Instance
Our cost
= friend’s cost

4

Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
288

Xi
Yj
Fill in box
Try all bird’s ans.

delete yj
Friend’s sub-Instance
Our cost
= friend’s cost

3

Fill in Box
Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
289

Xi
Yj
Fill in box
Try all bird’s ans.

take both xi and yj
Sorry bird is
wrong.
Our cost
= -

-
Fill in Box

Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
290

Xi
Yj
Fill in box
Try all bird’s ans.
Take best of best
Fill in Box

4

Xi = x1,…xi
Yj = y1,…,yj
sub-Instancei,j =

‹#›
291

Fill in Box

‹#›
292

Fill in Box

‹#›
293

Order to fill table:
so that nobody waits

This guy waits for

Order to Fill in Table

‹#›
294

(later)

Order to Fill in Table

‹#›
295

Base Cases:
general algorithm
does not work

This guy’s
friends are

Base Cases

‹#›
296

Base Cases:
general algorithm
does not work

Base Cases

‹#›
297

Base Cases

‹#›
298

With Advice

‹#›
299

With Advice
Done

‹#›
300

Knapsack Problem

Get as much value
as you can
into the knapsack

‹#›
301

Knapsack Problem

Ingredients:
Instances: The volume V of the knapsack.
The volume and price of n objects
<,,… ,>.
Solutions: A set of objects that fit in the knapsack.
i.e. i  S vi  V
Cost of Solution: The total value of objects in set.
i.e. i  S pi
Goal: Get as much value as you can
into the knapsack.

‹#›
302

v=4,p=4
v=4,p=4

V=8
Greedy Algorithm
Most valuable pi
Greedy Criteria:

v=7,p=5
v=4,p=4
v=4,p=4
V=8
Greedy give 5
Optimal
gives 8

‹#›

v=7,p=5

V=7
Greedy Algorithm
Greedy Criteria:

v=7,p=5
v=4,p=4
v=4,p=4
V=7
Most dense in value
pi
vi

Greedy give 4
Optimal
gives 5
V=8

‹#›
Greedy Algorithm
Greedy Criteria:

v=4,p=4
V=7
Greedy give 4

v=7,p=5

V=7

v=4,p=4
¾ of

+ ¾ × 4 = 7
If fractional solutions are allowed.
= Optimal
Works
Most dense in value
pi
vi

Optimal
gives 5
Often an Integer
solution is MUCH
harder to find.

‹#›
Bird & Friend Algorithm
I ask the bird:

My instance:
“What is the last object to take?”
,,……………………..,>.
A solution:
<,,………..,>.

# of answers K =
n

v=7,p=5
v=4,p=4
v=4,p=4
V=12

‹#›
Bird & Friend Algorithm
I ask the bird:

My instance:
A solution:

# of answers K =

v=7,p=5
v=4,p=4
v=4,p=4
V=12

“Do we keep the last object?”
2 Yes & No
<,,………..,>.
,,……………………..,>.

‹#›
Bird & Friend Algorithm
My instance:

v=7,p=5
v=4,p=4
v=4,p=4
V=12

Bird says, Yes keep the last object.
Trust her and put it into your knapsack.
I ask my friend:

To fill the rest of the knapsack.
But what instance do I give him?
,,……………………..,>.

‹#›
Bird & Friend Algorithm
His instance:

v=7,p=5
v=4,p=4
v=4,p=4
V=12-4
,,………,>.

His solution:

<,,………..,>.

My solution:
My cost:
same + pn

<,,………..,,>

‹#›
Bird & Friend Algorithm
My solution:

<,,………..,,>

My instance:

v=7,p=5
v=4,p=4
v=4,p=4
V=12
,,……………………..,>.
If we trust the bird and friend,
this is valid and optimal.
My cost:
same +pn

‹#›
Bird & Friend Algorithm
My instance:

v=7,p=5
v=4,p=4
v=4,p=4
V=12

Bird says, No do not keep the last object.
Trust her and delete it.
I ask my friend:

To fill the knapsack with the rest.
What instance do I give him?
,,……………………..,>.

‹#›
Bird & Friend Algorithm
His instance:

v=7,p=5
v=4,p=4
v=4,p=4
V=12
,,……………………..,>.

My solution:
My cost:
same
His solution:
<,,………..,>.

same
If we trust the bird and friend,
this is valid and optimal.

‹#›
Time?

Same as the brute force algorithm
that tries each solution.

Same as Brute Force Algorithm
I try each of 2 bird ans.
My friends tries 2
His friends tries 2

‹#›
Memoization
Assign one friend to each sub-instance.

“Which is the best path from vi to t?”
 i

‹#›
Set of Sub-Instances

Determine the complete set of sub-Instances.
Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …
Given an instance I,
,,,,,>.
Is this a sub-Instance?
Yes, if the bird keeps saying “No”.
,,>.

‹#›
Set of Sub-Instances

Determine the complete set of sub-Instances.
Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …
Given an instance I,
,,,,,>.
Is this a sub-Instance?
No, the set of objects is always a prefix
of the original set.
,,,,,>.

‹#›
Set of Sub-Instances

Determine the complete set of sub-Instances.
Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …
Given an instance I,
,,,,,>.
Quite possibly, if V’  V.
Is this a sub-Instance?
,,>.

It is easier to solve than to
determine if it is a sub-instance.

‹#›
Set of Sub-Instances
Guess the complete set S of sub-Instances.
The set S of sub-Instances needs to:
include our given I
Yes: V’=V & i = n
My instance:
closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
,,……………………..,>.
 i  [0..n]
,,……,>.
 V’  [0..V]
,,……,>  S
Yes

No
,,…,>
,,…,>
 S

‹#›
Construct a table
for storing the cost of opt sol and bird’s advice.
for each sub-instance.
Sub-Instances
Map
Indexes
Cell of table

i
“Which of first i objects
to put in a knapsack of size v’?”
v’
,,……,>.
 i  [0..n]
 V’  [0..V]
The Table

‹#›
319

The Table
The complete set S of sub-Instances.
 i  [0..n]
,,……,>.
 V’  [0..V]

0
1
i-1
n
0
1
2
2
V’-vi
V
V’

i

Yes

No
OptSol Cost
&
Bird’s Advice
for this
sub-Instance
Our cost?

same

same + pi
Take best
of best.

‹#›
The Table
The complete set S of sub-Instances.
 i  [0..n]
,,……,>.
 V’  [0..V]

0
1
i-1
n
0
1
2
2
V’-vi
V
V’

i

OptSol Cost
&
Bird’s Advice
for this
sub-Instance
Order to fill
so nobody
waits?

‹#›
The Code

‹#›

‹#›

‹#›
Running Time
Running time
= ( # of sub-instances × # bird answers )
= ( Vn × 2 )
= ( 2#bits in V × n )
My instance:
Polynomial?
,,……………………..,>.
The complete set S of sub-Instances is
 i  [0..n]
,,……,>.
 V’  [0..V]
Yes

No
Exponential in “size” in instance!

‹#›
The Knapsack Problem
Dynamic Programming
Running time = ( V × n )
= ( 2#bits in V × n )
Poly time if size of knapsack is small
Exponential time if size is an arbitrary integer.

‹#›
The Knapsack Problem
If there is a poly-time algorithm
for the Knapsack Problem

For EVERY optimization problem
there is a poly-time algorithm.
Dynamic Programming
Running time = ( V × n )
= ( 2#bits in V × n )
NP-Complete

‹#›
The Knapsack Problem
Likely there is not a poly-time algorithm
for the Knapsack Problem.

Likely there is not a poly-time algorithm
for EVERY optimization problem.
Dynamic Programming
Running time = ( V × n )
= ( 2#bits in V × n )
NP-Complete

‹#›
The Knapsack Problem
Dynamic Programming
Running time = ( V × n )
= ( 2#bits in V × n )
NP-Complete
Approximate Algorithm
In poly-time, solution can be found
that is (1+) as good as optimal.

done

‹#›
The Job/Event Scheduling Problem

Schedule as
many events
in your room
as possible

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

‹#›
Greedy Algorithm
Earliest Finishing Time
Schedule the event which will
free up your room for someone
else as soon as possible.
Motivation:

Greedy Criteria:

‹#›
Ingredients:
Instances: Events with starting and finishing times
and weights
<,,… ,>.
Solutions: A set of events that do not overlap.
Cost of Solution: Total weight of events scheduled.
Goal: Given a set of events, schedule max weight
Weighted Event Scheduling

‹#›
Greedy Algorithm
Earliest Finishing Time
Schedule the event which will
free up your room for someone
else as soon as possible.
Motivation:

Greedy Criteria:
100
1
1

‹#›
Bird & Friend Algorithm
I ask the bird:

An instance:
“What is the last event to take?”
<,,… ,>.
A solution:
<,,… ,>.

# of answers K =
n

‹#›
Bird & Friend Algorithm
I ask the bird:

An instance:
“Do we keep the last event?”
<,,… ,>.
A solution:
<,,… ,>.

# of answers K =
2 Yes & No

‹#›
Bird & Friend Algorithm
An instance:
I ask the bird:

“Do we keep the last event?”
<,,… ,>.
His solution:
<,,… ,>.

I ask my friend:

She answers: No
My solution:
same
My cost:
same
<,,… ,>.

‹#›
Bird & Friend Algorithm
An instance:
I ask the bird:

“Do we keep the last event?”
<,,… ,>.
His solution:
<,,… ,>.

I ask my friend:

She answers: Yes
My solution:
same + .
My cost:
same +wn
<,,… ,>.

Carefull

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
Give the rest to my friend.

No this solution is not valid!

Here is my best subsolution.
I add to his subsolution the bird’s answer.

last event

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
Then I should politely tell the bird
she is wrong

No we trust the bird!

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”

No we trust the bird!

You only tell her she is wrong
if you really know.
Eg k words don’t fit on the last line
The bear does not fit into the knapsack

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”

No we trust the bird!

Your friend could have just as easily given you this subsolution that does not conflict with the bird’s answer.

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”

No we trust the bird!

Or maybe he needs to make a sacrifice when finding his answer in order that the overall solution is the best.

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”

No we trust the bird!

Or goal now is to find the best solution to our instance that is consistent with the bird’s answer.
Then we will take the best of best.

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”

No we trust the bird!

Dude! It is your job to give me the right subinstance so that I give you a subsolution that does not conflict with the bird

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
My instance:

last event
Cant keep any events that overlap with it.

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
My instance:

last event
I ask my friend:

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
His instance:
His solution
I ask my friend:

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
I ask my friend:

My solution:
same + .
Valid?

My instance:
My solution:
Yes

‹#›

Bird & Friend Algorithm
Bird answers:

“Yes keep the last event.”
My instance:
My solution:
I ask my friend:

My solution:
same + .

My cost:
same +wn

‹#›
Time?

Same as the brute force algorithm
that tries each solution.

Same as Brute Force Algorithm
I try each of 2 bird ans.
My friends tries 2
His friends tries 2

‹#›
Memorization
Assign one friend to each sub-instance.

“Which is the best path from vi to t?”
 i

‹#›
Set of Sub-Instances
Given an instance I,

Determine the complete set of sub-Instances.
Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …

‹#›

Every subset of {1,…,9}
is a possible sub-Instance.
I.e. could be an exponential
number of them.
Hence, running time
is exponential.

Greedy algorithm sorted
jobs by finishing time.
Let us do that too.

‹#›
Each sub-Instance is prefix.
I.e. only n of them.
Hence, running time
is polynomial!

‹#›
Set of Sub-Instances
Guess the complete set S of sub-Instances.
The set S of sub-Instances needs to:
include our given I
Yes: i = n
My instance:
<,,…………….… ,>.
 i  [0..n]
<,,… ,>
closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
each sub-Instance needs to be
asked of some friend, friend…
?
Only n sub-Instances
Good enough.

‹#›
Set of Sub-Instances

sub-Instance =
<,,…………………………..,>

last event

Show closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
Events sorted by finishing time.

‹#›
Set of Sub-Instances

sub-Instance =
<,,…………………………..,>

Bird answers:

“Yes keep the last event.”

last event

Show closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
Delete overlapping events for friend.

‹#›
Set of Sub-Instances

subsub-Instance =
<,,…..,>
Bird answers:

“Yes keep the last event.”
Show closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S
Delete overlapping events for friend.

‹#›
Set of Sub-Instances

subsub-Instance =
<,,…..,>
Show closed under “friend” operation
 sub-Instance  S 
subsub-Instance  S

 subsub-Instance  S
 set of kept jobs is a prefix of events.

typical deleted job
typical kept job
Event j is kept fj  si

‹#›
Set of Sub-Instances
The complete set S of sub-Instances is
My instance:
<,,…………….… ,>.
 i  [0..n]
<,,… ,>
Table:

0, 1, 2, 3, 4, …. n
Base case
Original

‹#›
Set of Sub-Instances
The complete set S of sub-Instances is
Running time
= # of sub-instances × # bird answers
= n × 2
My instance:
<,,…………….… ,>.
 i  [0..n]
<,,… ,>
Done
But to find your friend’s “yes” sub-instance
you must know how many events overlap
with your last event. This takes time:
O(logn) using binary search
for a total of O(nlogn) time.

‹#›
Input:
Output:

s=6*8+((2+42)*(5+12)+987*7*123+15*54)
Parsing

‹#›
Parsing

Recursive Alg:
GetExp calls GetTerm
GetTerm calls GetFact
GetFact calls GetExp

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Context Free Grammar
(Not look ahead one)
For ease, we will assume every non-terminal
either goes to two non-terminals
or to one terminal

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Input:
start non-terminal = T
string to parse
= a1a2a3 ….. an
= baeaadbda
Output: A parsing
T  a1a2a3 ….. an
T
C
A

A
A
B
A
C
C
B
A
C
T
A
B

B
T
C
A

b d a
b a e a
a d b

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Recursive Algorithm:
GetT does not know
whether to call
GetA, GetC, or GetT.
Input:
T  a1a2a3 ….. an

T
C
A

A
A
B
A
C
C
B
A
C
T
A
B

B
T
C
A

b d a
b a e a
a d b

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask Little Bird:
For first rule
Ask Friend
Parse left
Ask Another Friend
Parse right.
Input:
T  a1a2a3 ….. an
T
C
A

A
A
B
A
C
C
B
A
C
T
A
B

B
T
C
A

b d a
b a e a
a d b

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask Little Bird:
For first rule
Instance to give Friend
?
Input:
T  a1a2a3 ….. an
T
C
A

b d a
b a e a
a d b

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask Little Bird:
For first rule
Want from Friend:
Left sub-parse tree.
Instance to give him:
C  baeaadb
Input:
T  a1a2a3 ….. an
C
A
A
B
A
C
C
B
A
C
T
A
B

T
A

b d a
b a e a
a d b

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask Little Bird:
For first rule
How can we know split?
Ask the Bird!

Input:
T  a1a2a3 ….. an
T
C
A

A
A
B
A
C
C
B
A
C
T
A
B

B
T
C
A

b d a
b a e a
a d b

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask Little Bird:
For first rule
For the split.

# of ans K =
# of ans K =
mT = # of rules for T.
n = # chars in string.
Total # of ans K =
mT × n.
Input:
T  a1a2a3 ….. an

b d a
b a e a
a d b
T
C
A

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask left friend:
Instance: C  baeaadb
Solution: Left parsing
Input:
T  a1a2a3 ….. an

b a e a
a d b
C
T
b d a
A

A
A
B
A
C
C
B
A
C
T
A
B

‹#›
T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Ask right friend:
Instance: A  bda
Solution: Right parsing
Input:
T  a1a2a3 ….. an
A
B
T
C
A

b d a
T
C

b a e a
a d b

‹#›
374

T  AB
 CA
 TT
A  AA
 BT
 a
B  TA
 BC
 b
 e
C  CB
 AC
 c
 d
Parsing
Combine:
Instance:
Bird’s Answer
Left Friend’s Answer
Right Friend’s Answer
Input:
T  a1a2a3 ….. an
A
A
B
A
C
C
B
A
C
T
A
B

B
T
C
A

T
b d a
b a e a
a d b
C
A

‹#›
375

‹#›
376

Time?

Same as the brute force algorithm
that tries each solution.

Same as Brute Force Algorithm
I try each of 2 bird ans.
My friends tries 2
His friends tries 2

‹#›
377

Memoization
Assign one friend to each sub-instance.

“Which is the best path from vi to t?”
 i

‹#›
378

Set of Sub-Instances

Determine the complete set of sub-Instances.
Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …
Given an instance I,

‹#›
379

Set of Sub-Instances

Determine the complete set of sub-Instances.
My instance I:
gives:

My left sub-Instance.
gives:

His right sub-Instance.
T  a1a2a3 ….. an
T
C
A

C
A

b d a
b a e a
a d b

‹#›
380

Set of Sub-Instances

Determine the complete set of sub-Instances.
T’  aiai+1 ….. aj
 non-terminals T’
 i,j  [1,n]
My instance I:
T  a1a2a3 ….. an
sub-Instances:
# of sub-Instances =
# of non-terminals × n2
C
a d b

aiai+1…aj
T’=
a1…ai-1
aj+1…an

‹#›
381

Construct a table
for storing the cost of opt sol and bird’s advice.
for each sub-instance.
Sub-Instances
Map
Indexes
Cell of table

The Table
T’  aiai+1 ….. aj
T’  i,j  [1,n]

j
T’
i

‹#›
382

‹#›
383

T’  aiai+1 ….. aj  non-terminals T’

&  i,j  [1,n]
sub-Instances:
Running Time
Running time
= ( # of sub-instances × # bird answers )
= ( # of non-terminals × n2
gives: First rule and split

× # of rules · n )
Done

‹#›
384

Find a Satisfying Assignment
c = (x3 or x5 or x6) and (x2 or x5 or x7) and (x3 or x4)

An instance (input) consists of a circuit:
A solution is an assignment of the variables.
x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 1, x6 = 0, x7 = 1
true

false

true

true

true

true

true

true

The cost of a solution is
1 if the assignment satisfies the circuit.
0 if not.
The goal is to find satisfying assignment.

‹#›
385

Find a Satisfying Assignment
c = (x3 or x5 or x6) and (x2 or x5 or x7) and (x3 or x4)

Instance:

Ask the little bird
Value of x1 in an optimal solution
or even better
Value of x3 in an optimal solution
For now, suppose she answered x3 = 0.
We will have to try both x3 = 0 and x3 = 1.

‹#›
386

Find a Satisfying Assignment
c = (x3 or x5 or x6) and (x2 or x5 or x7) and (x3 or x4)

Instance:
true

true

false

Commit to x3 = 0 and simplify

c = (x2 or x5 or x7) and x4

Sub-Instance:
Friend gives Sub-Solution:
x1 = 0, x2 = 1, x4 = 0, x5 = 1, x6 = 0, x7 = 1
Our Solution:
x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 1, x6 = 0, x7 = 1

‹#›
387

In the end, some friend looks
at each of the 2n assignments,
Speeding Up the Time

x3
0
1
x2
0
1
x1
0
1
x1
0
1
x2
0
1
x2
0
1
x1
0
1

‹#›
388

Memoization
Assign one friend to each sub-instance.

“Which is the best path from vi to t?”
 i

‹#›
389

Set of Sub-Instances
Given an instance I,

Determine the complete set of sub-Instances.
Imagine running the recursive algorithm on it.
Determine the complete set of sub-Instances ever given to you, your friends, their friends, …

‹#›
390

Set of Sub-Instances
Given an instance I,

Determine the complete set of sub-Instances.
Is this a sub-Instance?
Yes
c = (x1 or y1) and (x2 or y2) and (x3 or y3) and (x4 or y4)
c = (x1) and (x3)
Commit to
y1=0, y2=1, y3=0, y4=1,
and simplify

True for any subset of the xi.
 could be an exponential # of different sub-Instances.
 running time is exponential.

‹#›
391

In the end, some friend looks
at each of the 2n assignments,
Speeding Up the Time

x3
0
1
x2
0
1
x1
0
1
x1
0
1
x2
0
1
x2
0
1
x1
0
1

‹#›
392

Speeding Up the Time

x3
0
1
x2
0
1
x1
0
1
x1
0
1
x2
0
1
x2
0
1
x1
0
1
But sometimes we can prune off branches.

‹#›
393

Find a Satisfying Assignment
Instance:
c = (x2 or x5 or x7) and x3

x3 is forced to x3 = 0

x3
0
1
x2
0
1
x1
0
1
x1
0
1
x2
0
1
x2
0
1
x1
0
1

‹#›
394

Find a Satisfying Assignment
Instance:
c = (x2 or x5 or x7) and x3 and x3

This is trivially unsatisfiable
because x3 can’t be both 0 and 1.

x3
0
1
x2
0
1
x1
0
1
x1
0
1
x2
0
1
x2
0
1
x1
0
1

‹#›
395

‹#›
396

‹#›
397

Designing Recursive Back Tracking Algorithm
What are instances, solutions, and costs?
Given an instance I,
What question do you ask the little bird?
Given a bird answer k  [K],
What sub-Instance do your give your friend?
Assume he gives you optSubSol for sub-Instance.
How do you produce an optSol for I from
the bird’s k and
the friend’s optSubSol?
How do you determine the cost of optSol from
the bird’s k and
the cost of the friend’s optSubSol?
Try all bird’s answers and take best of best.

Review

‹#›
398

Recursive Back Tracking Algorithm

Dynamic Programming Algorithm
Given an instance I,
Imagine running the recursive alg on it.
Determine the complete set of sub-Instances
ever given to you, your friends, their friends, …
Build a table indexed by these sub-Instances
Fill in the table in order so that nobody waits.
the cost of its optimal solution
advice given by the bird
Run the recursive algorithm with bird’s advice to
find the solution to your instance.
Review

‹#›
399

Optimization Problems
Don’t mix up the following
What is an instance
What are the objects in an instance
What is a solution
What are the objects in a solution
What is the cost of a solution
Greedy algorithm
What does the algorithm do & know
What does the Prover do & know
What does the Fairy God Mother do & know
Recursive Backtracking / Dynamic Programming
What does the algorithm do & know
What does the little bird do & know
What does the friend do & know

‹#›
400

Dynamic Programming
Don’ts
Yes, the code has a basic structure that you should learn.
But don’t copy other code verbatim
Don’t say if(ai = cj)
(i.e. Longest Common Subsequence)
when our problem does not have cj

‹#›
401

Dynamic Programming
Don’ts
When looping over the sub-instances
be clear what the set of sub-instances are
which is currently being solved,
i.e. which instance is cost(i,j)?
If you know that the set of sub-instances are the prefixes of the input, i.e. ,
then don’t have a two dimensional table. Table[1..n,1..n].
Don’t loop over i and loop over j if j never gets mentioned again.

‹#›
402

Dynamic Programming
Don’ts
When trying all bird answers
be clear what the set of bird answers are,
which is currently being tried,
& what it says about the solution being looked for.
When getting help from your friend,
be clear what the sub-instance is that you are giving him
How do you use the current instance and the bird’ s answer to form his sub-instance?
Don’t simply say cost(i-1,j-1)

‹#›
403

Dynamic Programming
Don’ts
Think about what the base cases should be.
Don’t make an instance a base cases
if they can be solved using the general method.
% is used to start a comment.
Don’t put it in front of code.

‹#›
404

If a solution is a binary tree of objects,

The Question For the Little Bird
“What object is at the root of the tree?”
“Which key is at the root of the tree?”

38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
Eg. The Best Binary Search Tree problem,

‹#›
405

Matrix Multiplication

‹#›
406

‹#›
407

‹#›
408

‹#›
409

‹#›
410

All Pairs Shortest Paths

‹#›
411

‹#›
412

‹#›
413

‹#›
414

‹#›
415

‹#›
416

end

‹#›
417

Construct a table
for storing an optimal solution & cost
for each sub-instance.
Dynamic Programming
Sub-Instances
Map
Index
Cell of table

“Best path from vi to t?”
 i
 i ϵ [n], i.e. for each node vi

t, v8, v7, v6, v5, …., s
i
“Which is the best path from vi to t?”

‹#›
418

/docProps/thumbnail.jpeg