算法代写|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).

blank

(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, justifi
cation 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 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).


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论