Transcript oldlecture12

Assignment 4. (Due on Dec 2. 2:30 p.m.)
This time, Prof. Yao and I can explain the questions,
but we will NOT tell you how to solve the
problems.
Question 1. (20 points) Give an O(n2) dynamic
algorithm to find the longest monotonically
increasing subsequence of a sequence of n numbers.
(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.
Assignment 4. (Due on Dec 2. 2:30 p.m.)
• Question 2. (40 points) Give an O(n2) dynamic
algorithm to find the longest monotonically
increasing subsequence of a sequence of n numbers,
where an odd number in the monotonically
increasing subsequence must be followed by an
even number.
• Example: Consider sequence 1,7,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 not the one that we are looking for
since 5 is not followed by an even number.
Assignment 4. (Due on Dec 2. 2:30 p.m.)
Question 3 (40 points) 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. If every end of e is
assigned a letter, then 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.
A
A
C
Figure 1
Lemma 26.8: If the Edmonds-Karp algorithm is run
on a flow network G=(V,E) with source s and sink t,
then for all vertices vV-{s, t}, the shortest-path
distance f(s,v) in the residual network Gf increases
monotonically with each flow augmentation.
Proof: We prove it by contradiction.
Let f and f’ be the flows for the k-th and (k+1)-th
iterations, the augmentation between them is the
first that decrease some shortest-path distance.
• Let v be the vertex with minimum f’(s,v) such that
f’(s,v)< f(s,v).
Let P: s -- … u->v be the shortest path in Gf’.
Thus, (u,v) Ef’ and f’(s,u)= f’(s,v)-1.
By the choice of v, f’(s,u) f(s,u).
Thus, (u,v) Ef.
(Otherwise, we have
f(s,v) f(s,u)+1  f’(s,u)+1 = f’(s,v). )
How can we have (u,v) Ef’ and (u,v) Ef. ?
The augmentation must have increased the
flow form v to u.
Since E-K algorithm always uses shortest path,
edge (v, u) is the last edge in the path from s
to u. So,
f(s,v)= f(s,u)-1  f’(s,u)-1 = f’(s,v)-2.
Contradiction to f’(s,v)< f(s,v).
Theorem 26.9. If Edmonds-Karp algorithm is run on
a flow network G=(V,E) with source and sink t, then
the total number of flow augmentations performed
by the algorithm is O(VE).
Proof: Each augmentation has a critical edge (u, v),
where c(u,v) is minimum among all edges in the
shortest path.
We show that each edge (u,v) can be a critical edge
for at most O(|V|) times.
Consider a critical edge (u,v) for flow f.
f(s,v)= f(s,u)+1.
(u,v) will disappear after that path is used for
augmentation.
(u,v) will appear again after an augmentation
with (v,u) in the shortest path. Let f’ be the
flow in G when this event occurs, we have
f’(s,u)= f’(s,v)+1.
Thus, f’(s,u)= f’(s,v)+1 f(s,v)+1=
f(s,u)+2.
Since the length of the shortest path is at most
|V|-1. Thus, each edge (u,v) can be a critical
edge for at most |O(|V|) times.
Total number of augmentations is O(VE).
Each iteration takes at most O(E) time, the
total time is O(VE2).
Maximum k-Clustering
Problem: Given a set of points V in the plane
(or some other metric space), find k points c1,
c2, .., ck such that for each v in V,
min { i=1, 2, …, k} d(v, si)  d
and d is minimized.
Fasthest-point clustering algorithm
Step 1: arbitrarily select a point in V as c1.
Step 2: let i=2.
Step 3: pick a point ci from V –{c1, c2, …, ci-1}
to maximize min {|c1ci|, |c2ci|,…,|ci-1 ci|}.
Step 4: i=i+1;
Step 5: repeat Steps 3 and 4 until i=k.
Theorem: Farthest-point clustering algorithm
has ratio-2.
Proof: Let c k+1 be an point in V that maximize
=min {|c1ck+1|, |c2ck+1|,…,|ck ck+1|}.
Since two of the k+1 points must be in the
same group,  <=2opt.
Since for any v in V,
min {|c1v|, |c2v|,…,|ck v|}<=  (based on the
alg.), so the algorithm has ratio-2.