2023年11月25日

算法代写｜CS/ECE 374 A Homework 7

这是一个澳洲的计算与算法代写案例

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;v2S 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 2 f0; : : : ; kg and j 2 f0; : : : ; ng, 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:

S contains exactly i leaves, and
minu2S 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 −1.)

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.

Problem 7.2: (Turning a sequence into a tree) We are given a sequence of n numbers ha1; : : : ; ani.
We want to compute a binary tree T with nodes a1; : : : ; an such that the inorder traversal is precisely ha1; : : : ; ani, while minimizing the cost function c(T) = P(ai; aj) is an edge of T jai−ajj.
(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 h5; 6; 16; 13; 2; 11; 14; 15; 3; 12; 8; 7i, one feasible solution is the following, which has cost j3 − 6j + j3 − 8j + j6 − 5j + j6 − 11j + j8 − 12j + j8 − 7j + j11 − 13j + j11 − 14j + j13 − 16j + j13 − 2j + j14 − 15j = 39 (but we are not claiming that this is optimal).

(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 hai; ai+1; : : : ; aji, and
the root of T is am.

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 C0(i; j; p) be the minimum of c(T) + jap − r(T)j over all binary trees T with nodes ai; ai+1; : : : ; aj such that the inorder traversal of T is hai; ai+1; : : : ; aji, where r(T) denotes the root of T.

Describe a new recursive formula for C0(i; j; p). Include appropriate base cases, justification of your formula, and indicate how the final optimal value to the original problem can be expressed in terms of C0(·; ·; ·).

(d) Next, using (c), specify the evaluation order, and analyze the running time of the resulting 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).