Let T be a rooted (not necessarily binary) tree with n nodes. Each node i has a positive weight w
(i). The nodes are ordered according to postorder, which means if node i is a descendant of node j, then i < j. (Therefore node n is the root.) Suppose we wanted to "harvest" at most k nodes of the tree in such a way that we maximize the sum of the weights of the harvested nodes. However, if we harvest a node i, we must also harvest all children of i (and therefore all children of those children as well, and so on). The set of nodes consisting of i and all of its descendants is called the complete subtree of T rooted at i and is denoted T(i).
(1) A(i, j) denotes the maximum weight harvestable from T(i) if
we can harvest at most j nodes.. If we are given a leaf node i, give an expression for A(i, j) for all j.
.
(2) Let B(i, j,l) denote the maximum weight harvestable from T(i) given
that we harvest at most j nodes, AND that those nodes come from the complete
subtrees rooted at the ?rst l children of node i. Let C(i) denote the list of children
of node i, and so C(i, j) denotes the j-th child of node i. Suppose we are given i,
and we know A(x, y) for all x < i (and in particular, for all children of i) and for all
yall j.
(3) Suppose we are given i and c, and in addition to what we know in the
previous part, we further know B(i,j,c) for all j Give an expression
for B(i,j, c+1) in terms of known values for all j.
(4) Suppose we are given i, and in addition to what we know in the previous
two parts, we further know B(i, j, c) for all j and c. Give an expression for A(i, j)
in terms of known values.
(5) How many distinct entriesexist in A?
(6) How many distinct entries exist in B?
(7) Which entry of A or B answers the original problem?
(8) What is the runtime of this algorithm?