CS/ECE 374 A (Spring 2022) Homework 7 Solutions
Problem 7.1: (Social distancing for koalas?) We are given a binary tree T with n nodes, and a number k. (You may assume that every non-leaf node has exactly 2 children.) We want to pick a subset S of k leaves that maximizes the value ∆(S) = minu,v∈S d(u, v), where d(u, v) denotes the distance between u and v, i.e., the length of the (unique) path from u to v in T. (Intuitively, ∆(S) represents the amount of “separation” between the leaves in S.) You will design an efficient dynamic programming algorithm to solve this problem.
In the example below, one optimal subset S is shown in red, with ∆(S) = 5. (Turn the picture upside down if you are a koala 🙂
(a) Let Tv denote the subtree rooted at a node v. Consider the following definition of subproblems: for each node v and each i ∈ {0,…,k} and j ∈ {0,…,n}, let F(v,i,j) be the maximum of ∆(S) over all subsets S of the leaves in Tv, subject to the following two constraints:
Copyright By PowCoder代写 加微信 powcoder
S contains exactly i leaves, and
minu∈S d(u, v) = j (i.e., the closest distance from S to the root of Tv is j).
(As usual, if no feasible solution exists, the maximum is −∞.)
First, describe a recursive formula for F (v, i, j). Include appropriate base cases and justification of your formula, and indicate how the final optimal value to the original problem can be expressed in terms of F (·, ·, ·).
(b) Next, specify the evaluation order, write pseudocode to solve the problem, and analyze the running time as a function of n and k. Your algorithm only needs to output the optimal value.
(a) Let r be the root of the entire tree. The final answer we want is max F (r, k, j). j ∈{0,…,n}
Base case. For each leaf v, F(v,i,j) = −∞ for each i ∈ {1,…,k} and j ∈ {0,…,n}, except F(v,1,0) = ∞. For each internal node v, F(v,i,0) = −∞ for each i ∈ {0,…,n}.
Recursive formula. For each internal node v with children v1 and v2, and each i ∈ {1,…,k} and j ∈ {1,…,n},
max min{F(v1,i′,j′), F(v2,i−i′,j−1), j+j′ +1} i′ ∈{1,…,i−1}, j ′ ∈{j −1,…,n}
max F(v,i,j) = max i′ ∈{1,…,i−1}, j ′′ ∈{j −1,…,n}
F(v1,i,j−1)
F(v2,i,j−1)
min{F(v1,i′,j−1), F(v2,i−i′,j′′), j+j′′ +1}
(Note: the expression can be simplifed without separating out the last two cases, if we add boundary base cases for i = 0 and use sentinels, namely, set F(v,0,−∞) = ∞ for leaves v.)
Justification. Consider the optimal solution S corresponding to F (v, i, j). Let S1 denote the subset of the leaves of S from the left subtree at v1, and let S2 denote the subset of the leaves of S from the right subtree at v2. Suppose we know that |S1| = i′ and |S2| = i−i′. And suppose we know that minu∈S1 d(u,v1) = j′ and minu∈S2 d(u,v2) = j′′. We must have min{j′,j′′}+1 = j. In other words, we have (i) j′′ = j −1 and j′ ∈ {j −1,…,n}, or(ii)j′ =j−1andj′′ ∈{j−1,…,n}.
Now, ∆(S) = min{∆(S1), ∆(S2), (j′ + 1) + (j′′ + 1)}, since the closest pair in S may have both leaves in S1 (in which case the distance is ∆(S1)), or both leaves in S2 (in which case the distance is ∆(S2)), or one leaf in S1 and one leaf in S2 (in which case the distance is (j′ + 1) + (j′′ + 1) by routing through the root v).
Thus, the optimal solution has value min{F(v1,i′,j′),F(v2,i−i′,j′′),(j′ +1)+(j′′ +1)}. Exceptional cases are when i′ = i, where the value is just F(v1,i,j−1), and when i′ = 0, where the value is just F (v2, i, j − 1).
We don’t know i′ , j ′ , j ′′ in advance, and so will try all feasible choices and take the maximum.
(b) Evaluation order. Any bottom-up ordering of v (e.g., postorder traversal).
Pseudocode. We use recursion to evaluate in bottom-up order. (This is still dynamic
programming—we will use a table to memoize F (·).) Evaluate(v):
1. 2. 3. 4. 5. 6.
ifvisaleafthen for i = 1 to k do
for j = 0 to n do F[v,i,j] = −∞
F[v,1,0] = ∞ return
10. 11. 12. 13. 14. 15. 16. 17. 18.
let v1, v2 be the children of v Evaluate(v1)
Evaluate(v2) fori=1tokdo
F[v,i,0] = −∞ for j = 1 to n do
F [v, i, j] = max{F [v1, i, j − 1], F [v2, i, j − 1]} fori′ =1toi−1do
for j′ = j − 1 to n do
F [v, i, j] = max{F [v, i, j], min{F [v1, i′, j′], F [v2, i − i′, j − 1], j + j′ + 1}}
for j′′ = j − 1 to n do
F [v, i, j] = max{F [v, i, j], min{F [v1, i′, j − 1], F [v2, i − i′, j′′], j + j′′ + 1}}
Algorithm:
19. let r be the root
20. Evaluate(r)
21. returnminj=0,…,nF[r,k,j]
Analysis. Lines 1–6 take O(kn) time. Lines 10–18 take O(k · n · k · n) = O(k2n2) time. Thus, over all n nodes, Evaluate() takes O(k2n2 ·n) = O(k2n3) time. Line 21 takes O(n) additional time. Total running time: O(k2n3).
(Note: A better bound can be obtained if the tree is balanced: the running time is actually O(k2h2n) if the tree has height h, since j and j′′ only need to go up to h.)
Alternate Solution for (b):
Here is an alternate way to write pseudocode that completely avoids recursion:
1. 2. 3. 4. 5. 6. 7. 8. 9.
10. 11. 12. 13. 14. 15. 16. 17. 18.
first compute a postorder traversal for each node v in postorder do {
if v is a leaf then for i = 1 to k do
for j = 0 to n do F[v,i,j] = −∞
F[v,1,0] = ∞
let v1, v2 be the children of v for i = 1 to k do
F[v,i,0] = −∞ for j = 1 to n do
F [v, i, j] = max{F [v1, i, j − 1], F [v2, i, j − 1]} fori′ =1toi−1do
for j′ = j − 1 to n do
F [v, i, j] = max{F [v, i, j], min{F [v1, i′, j′], F [v2, i − i′, j − 1], j + j′ + 1}}
for j′′ = j − 1 to n do
F [v, i, j] = max{F [v, i, j], min{F [v1, i′, j − 1], F [v2, i − i′, j′′], j + j′′ + 1}}
19. let r be the root
20. returnminj=0,…,nF[r,k,j]
The analysis is similar.
Problem 7.2: (Turning a sequence into a tree) We are given a sequence of n numbers ⟨a1, . . . , an⟩. We want to compute a binary tree T with nodes a1, . . . , an such that the inorder traversal is precisely ⟨a1,…,an⟩, while minimizing the cost function c(T) = (ai,aj) is an edge of T |ai−aj|. (Here, an internal node of T may have degree 1 or 2.) You will design two efficient dynamic programming algorithms to solve this problem.
For example, for the input sequence ⟨5, 6, 16, 13, 2, 11, 14, 15, 3, 12, 8, 7⟩, one feasible solution is the following, which has cost |3−6|+|3−8|+|6−5|+|6−11|+|8−12|+|8−7|+|11− 13|+|11−14|+|13−16|+|13−2|+|14−15| = 39 (but we are not claiming that this is optimal).
5 1112 7 13 14
(a) Consider the following definition of subproblems: for each i, j, m with 1 ≤ i ≤ m ≤ j ≤ n, let C(i, j, m) be the minimum of c(T ) over all binary trees T with nodes ai, ai+1, . . . , aj such that
the inorder traversal of T is ⟨ai,ai+1,…,aj⟩, and
therootofT isam.
First, describe a recursive formula for C(i,j,m). Include appropriate base cases and justification of your formula, and indicate how the final optimal value to the original problem can be expressed in terms of C(·, ·, ·).
(b) Next, specify the evaluation order, and analyze the running time of the resulting dynamic programming algorithm. (Your algorithm only needs to compute the optimal cost.) For this problem, there is no need to give pseudocode (if your descriptions of the recursive formula and evaluation order are precise enough).
(c) Consider a different definition of subproblem: for each i, j, p with 1 ≤ i ≤ j ≤ n and 1 ≤ p ≤ n, let C′(i,j,p) be the minimum of c(T) + |ap − r(T)| over all binary trees T with nodes ai, ai+1, . . . , aj such that the inorder traversal of T is ⟨ai, ai+1, . . . , aj ⟩, where r(T) denotes the root of T.
Describe a new recursive formula for C′(i, j, p). Include appropriate base cases, justifi- cation of your formula, and indicate how the final optimal value to the original problem can be expressed in terms of C′(·, ·, ·).
(d) Next, using (c), specify the evaluation order, and analyze the running time of the re- sulting dynamic programming algorithm. (Your algorithm only needs to compute the optimal cost.) Again, there is no need to give pseudocode (if your descriptions of the recursive formula and evaluation order are precise enough). Your algorithm in (d) should be more efficient than your algorithm in (b).
(a) The final answer we want is min C (1, n, m). m∈{1,…,n}
Base case. For each i ∈ {1,…,n}, C(i,i,i) = 0.
Recursive formula. For each i,j,m with 1 ≤ i < m < j ≤ n,
C(i, j, m) = min (C(i, m−1, m1)+C(m+1, j, m2)+|am−am1 |+|am−am2 |) m1∈{i,...,m−1}, m2∈{m+1,...,j}
And for each i, j with 1 ≤ i < j ≤ n,
C(i,j,j)= min C(i,j−1,m1)+|aj −am1|
m1 ∈{i,...,j −1}
C(i,j,i)= min C(i+1,j,m2)+|ai −am2|
m2 ∈{i+1,...,j }
Justification. Consider the optimal solution corresponding to C(i, j, m), which is a tree rooted at am. Suppose we know that the left subtree has root am1 and the right subtree has root am2 . The left subtree should have inorder traversal ⟨ai, . . . , am−1⟩, and the right subtree should have inorder traversal ⟨am+1 , . . . , aj ⟩. Thus, the optimal cost is C(i,m−1,m1)+C(m+1,j,m2)+|am −am1|+|am −am2|.
Exceptional cases are when m = j (the right subtree is empty), where the optimal cost is C(i,j − 1,m1) + |aj − am1|, and when m = i (the left subtree is empty), where the optimal cost is C(i+1,j,m2)+|ai −am2|.
We don’t know m1,m2 in advance, and so will try all choices and take the minimum.
(b) Evaluation order. Increasing order of j; and for subproblems with the same j, decreasing order of i.
(Increasing order of j − i would also work.)
Analysis. There are O(n3) subproblems or table entries, indexed by (i, j, m). Each table entry can be evaluated in O(n2) time using the above recursive formula, since we take min over O(n2) choices of (m1,m2). Thus, the total running time is O(n5).
(Note: Actually, it can be improved to O(n4), by rewriting the formula as
C(i, j, m) = min (C(i, m−1, m1)+|am−am1 |)+ min (C(m+1, j, m2)+|am−am2 |)
m1 ∈{i,...,m−1} m2 ∈{m+1,...,j }
since the two parts can be minimized separately. This way, the loops for m1 and for m2
can be done separately. This idea is similar to the next solution in (c)–(d). . . )
(c) The final answer we want is min (C′(1,m−1,m)+C′(m+1,n,m)). m∈{1,...,n}
Basecase. Foreachi,p∈{1,...,n},C′(i,i,p)=|ap−ai|.
Recursive formula. For each i,j with 1 ≤ i < j ≤ n and p ∈ {1,...,n},
min (C′(i,m−1,m)+C′(m+1,j,m)+|ap −am|) ′ m∈{i+1,...,j−1}
C (i, j, p) = min C ′ (i, j − 1, j ) + |ap − aj | C′(i+1,j,i)+|ap −ai|
(Note: the expression can be simplifed, if we add boundary base cases for C′(i, i − 1, p).)
Justification. Consider the optimal solution T corresponding to C′(i, j, p). Suppose we know that the root is r(T) = am. The left subtree should have inorder traversal ⟨ai , . . . , am−1 ⟩, and the right subtree should have inorder traversal ⟨am+1 , . . . , aj ⟩. Thus, the cost c(T )+|ap−r(T )| is C′(i, m−1, m)+C′(m+1, j, m)+|ap−am| (since C′(i, m−1, m) accounts for the cost of the left subtree plus the edge of its root to am, and C′(i, m−1, m) accounts for the cost of the right subtree plus the edge of its root to am, and these two parts are independent and can be optimized separately).
Exceptional cases are when m = j (the right subtree is empty), where the optimal cost is C′(i,j −1,j)+|ap −aj|, and when m = i (the left subtree is empty), where the optimal cost is C′(i+1,j,i)+|ap −ai|.
We don’t know m in advance, and so will try all choices and take the minimum.
(d) Evaluation order. Increasing order of j; and for subproblems with the same j, decreasing order of i.
(Increasing order of j − i would also work.)
Analysis. There are O(n3) subproblems or table entries, indexed by (i, j, p). Each table entry can be evaluated in O(n) time using the above recursive formula, since we take min over O(n) choices of m. Thus, the total running time is O(n4).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com