(2) [3+10=13 points) As a child, you might have had nice neighbors who (1) owned fruit trees, and (2) let you climb the

[answerhappygod]

2 3 10 13 Points As A Child You Might Have Had Nice Neighbors Who 1 Owned Fruit Trees And 2 Let You Climb The 1 (64.1 KiB) Viewed 29 times

(2) [3+10=13 points) As a child, you might have had nice neighbors who (1) owned fruit trees, and (2) let you climb the trees and pick some of the fruit for yourself. Knowing the fruit eating prowess of children, such neighbors would have had to be careful to avoid you just completely emptying their tree. So they might have given you a time limit on how long you are allowed to be in the tree. In turn, that would create an optimization problem for you: how to get the most fruit in the allotted time. Here, we will solve this problem. We model the fruit tree as a binary tree T with n nodes. For each node u of the tree, you are given the amount of fruit fu > 0 at that place. The neighbor's total time limit is 70. We will assume that climbing along one branch/edge of the tree always takes exactly one unit of time (in either direction). You start at a designated root noder, and must finish at r again after at most r time steps. Your goal is to find a climbing route maximizing the total amount of fruit you collect Specifically, if your route visits the set S of nodes, then you get ves fo units of fruit. T (a) Prove that if 2(n-1), you can completely clear the tree, i.e., get all the fruit. (b) Give (and analyze) a polynomial-time algorithm for maximizing the amount of fruit collected within 7 units of time. Your algorithm should return the amount of fruit you collect, as well as the set S of vertices you visit. of course, the point of Red-Black Trees and AVL Trees was to deal with the case when keys are added and deleted, something we will completely ignore here. Also, you might remember Splay Trees - they are actually remarkably good at quickly adapting the tree structure to put frequently accessed items near the root. But while they are remarkably good, they are not completely optimal, and here, we want to perfectly optimize