Transcript tut0911

More On Dynamic programming
Algorithms
Shortest path with edge constraint:
Let G=(V, E) be a directed graph with weighted edges. Let s and v be
two vertices in V. Find a shortest path from s to u with exactly k
edges. Here kn-1 is part of the input.
Solution:
Define d(i, v) be the length of the shortest path from s to v with exactly i
edges.
d(i, v)=min {c(w, v)+d(i-1, w)}
wV.
Initial values: d(i, s)=0, for i=0, d(i,s)=  for i=1, 2, …, d(0, v)=;
d(k, v) will give the length of the shortest path. A backtracking process can
give the path.
1
u
5
v
8
8
-2
6
z 0
-3
8
7
-4
2
8
8
7
9
x
y
i
z,
u,
x,
v,
y
0
0




•

6z
7z


2 

14u
4x
3
2v

9y
4y
2u
23x.
2
Shortest path with delay constraint:
Let G=(V, E) be a directed path. Each edge (u, v) has a
positive weight edges c(u, v) and a (positive integer)
delay delay(u, v). Let s and v be two vertices in V. Find a
shortest path from s to u with delay at most k.
Solution:
Define l(d, v) be the length of the shortest path from s to v with
delay = d.
l(d, v)=
min
{c(w, v)+l(d-delay(w, v), w), }.
wV & delay(w,v)d
Initial values: l(0, s)=0, l(i, s)=  and d(0, v)=;
l(k, u) will give the length of the shortest path.
A backtracking process can give the path.
The previous example is for delay(u, v)=1.
3
u
5
v
8
8
-2
6
z 0
delay(v,u)=2.
-3
8
7
-4
2
8
8
7
9
x
d
z,
0
0

1

x,
y
v,
y



6z
7z


2 

14u
4x
2u
3


9y
23x.
4y
u,
For any other
edge, it is 1.
4
5
Weighted interval scheduling for a lazy
man
Input: the same as weighted interval scheduling.
Goal: find a set of compatible jobs such that for any
two consecutive jobs in the subset either there is
some idle time or the total length of the two
consecutive jobs is at most k.
If k=4, we can choose black,
blue, yellow as a subset. But
we cannot choose black, blue
and green as the subset.
6
Solution:
Still the same equation, but use different p().
OPT(j) be the weight of the optimal solution
containing at most the first j jobs.
OPT(j)=min {OPT(j-1), vj+ OPT(p(j))}
Initial Value: OPT(0)=0.
P(j) is redefined as: the largest i<j such that job i is
compatible with j and either there is some idle time
between i and j or fj-si k.
7
K=4
p(b)=0;
p( c )=0;
p(a)=0;
p(e)=0;
p(d)=0;
p(f)=b;
p(g)=c;
p(h)=e;
8
k=6
p(b)=0;
p( c )=0;
p(a)=0;
p(e)=b;
p(d)=0;
p(f)=c;
p(g)=c;
p(h)=e;
9
Weighted maximum independent set on a path.
Given a graph G(V, E), where V={v1, v2, …, vn} and E={(vi,
vi+1)|for i=1, 2, …, n-1}. Each vertex vi has a weight wi.
Find an independent set with maximum weight.
• An independent set in a graph is a subset of vertices in V
such that no two vertices in the independent set share an
edge.
Solution: Define d(i) be the weight of the optimal solution for
the first i vertices.
d(i)=max {d(i-1), wi+d(i-2)}.
d(0)=0;
Remarks: The problem is almost identical to the weighted
interval scheduling problem if we treat p(i)=i-2.
10
Weighted maximum set on a path.
Given a graph G(V, E), where V={v1, v2, …, vn} and E={(vi,
vi+1)|for i=1, 2, …, n-1}. Each vertex vi has a weight wi.
d(vi, vi+1) is the length of the edge.
d(vi, vi+2)=d(vi, vi+1)+d(vi+1, vi+2).
Find a subset of vertices with maximum weight such that the
distance between any pair of vertices in the subset is at least
k.
Solution: Define d(i) be the weight of the optimal solution for
the first i vertices.
d(i)= max {d(i-1), wi+d(p(i))}.
d(0)=0;
Remarks: p(i) is the biggest j<i such that d(vi,vj)≥k.
11
Another setting of the previous problem.
Text book page 307.
Consider a highway from west to east. The possible sites for billboards are
given by numbers x1, x2, …, xn, each in the interval [0, M]. If you place
a billboard at location xi, you receive revenue of ri>0.
Regulations imposed by the county’s Highway Department require that no
two of the billboards be within less than or equal to 5 miles of each other.
How to place billboards at a subset of sites so as to maximize your total
revenue, subject to this restriction.
.
Solution: Define d(i) be the revenue of the optimal solution for the first i
sites.
d(i)=max { d(i-1), ri+d(p(i))}.
d(0)=0;
Remarks: p(i) is the biggest j<i such that xi-xj >5.
x1
x2
x3
xn
12
Another setting of the previous problem.
X1=0, x2=3, x3=6, x4=8, x5=15, x6=25.
W1=2, w2=5, w3=8, w4=6, w5=9, w6=12.
i
0 1 2 3
4 5 6
p(i): 0 0 0 1 1 4 5
d(i): 0 2, 5 10 10 19 31
d(i)=max { d(i-1), wi+d(p(i))}.
d(0)=0;
Remarks: p(i) is the biggest j<i such that xi-xj >5.
x1
x2
x3
xn
13
Change-making problem:
Given an amount n and unlimited quantities of coins
of each of the denominations
d1, d2, …, dm,
find the smallest number of coins that add up to n or
indicate that the problem does not have a solution.
Solution:
Let d(i) be the minimum number of coins used for
amount i.
Initial values: d(0)=0, d(i)=.
equation: d(i) = min d(i-dk)+1.
k=1, 2, …, m.
14
Change-making problem:
Initial values: d(0)=0, d(i)=.
equation: d(i) = min d(i-dk)+1
k=1, 2, …, m & i-d ≥0
k
d1=2 and d2=5. i=7.
i= 0, 1, 2, 3, 4, 5, 6, 7
d(i): 0, , 1, , 2, 1, 3, 2.
Backtracking: $5, $2.
(how do you get d(7)=2? d(7)=d(2)+5. Print $5 and
goto d(2). How do you get d(2)? D(2)=2+d(0). Print
out $2 and goto d(0). Whenever reach d(0), we stop. )
for i=3, since d(3)= , there is no solution.
15
LCS for three sequences.
Give three sequences X, Y, X.
Find the longest common subsequence for three sequences.
First try.
1. construct W, the LCS for X and Y
2. Construct U, the LCS for W and Z.
3. U will be the LCS for the tree sequences X, Y and Z.
It does not work!
Counter Example:
X=bbaaa, Y=aaaabb and Z=cbcbc.
LCS for X and Y is aaa. LCS for aaa and cbcbc is empty.
However, the LCS for X, Y and Z is bb.
16
LCS for three sequences.
Give three sequences X, Y, X.
Find the longest common subsequence for three sequences.
Solution:
Define c[i, j, k] be the length of LCS for the first I letters in X,
the first j letters in Y and the first k letters in Z.
c[i,j,k] is the maximum of the following:
c[i-1, j-1, k-1]+1, if Xi=Yj=Zk.
c[i-1, j-1, k];
c[i-1, j, k-1]
c[i, j-1, k-1]
c[i, j, k-1]
c[i,j-1, k]
c[i-1, j,k].
Initial values: c[i,jk]=0 if i=0 or j=0 or k=0.
17
• Exercise 1: Let T be a rooted binary tree, where
each internal node in the tree has two children and
every node (except the root) in T has a parent.
Each leaf in the tree is assigned a letter in ={A, C,
G, T}. Figure 1 gives an example. Consider an
edge e in T. Assume that every end of e is
assigned a letter. The cost of e is 0 if the two letters
are identical and the cost is 1 if the two letters are
not identical. The problem here is to assign a letter
in  to each internal node of T such that the cost of
the tree is minimized, where the cost of the tree is
the total cost of all edges in the tree. Design a
polynomial-time dynamic programming algorithm
to solve the problem.
18
A
A
A
C
Figure 1
19
Exercise 2. Give a polynomial time algorithm
to find the longest monotonically increasing
subsequence of a sequence of n numbers.
Can you give a linear space algorithm?
(Assume that each integer appears once in
the input sequence of n numbers)
Example: Consider sequence 1,8, 2,9, 3,10, 4,
5. Both subsequences 1, 2, 3, 4, 5 and 1, 8,
9, 10 are monotonically increasing
subsequences. However, 1,2,3, 4, 5 is the
longest.
20
Assignment 4.
(Due on Friday of Week 14. Drop it in
Mail Box 76 )
This time, I can explain the questions, but we
will NOT tell you how to solve the problems.
Question 1. (20 points) Change-making problem (version 1):
Given an amount n and coins of each of the denominations d1, d2, …, dm, where
there are k copies of d1 coin and unlimited quantities of other coins, design a
dynamic programming algorithm to find the smallest number of coins that add
up to n or indicate that the problem does not have a solution.
Question 2. (20 points) Change-making problem (version 2): Given an amount n
and coins of the denominations d1, d2, …, dm, where there are 2 copies of each
di coin, design a dynamic programming algorithm to find the smallest number of
coins that add up to n or indicate that the problem does not have a solution.
Question 3. (60 points) will be give in week 12.
21