2
$\begingroup$

We have a network of sensors organized in tree form, where the sensors occupy the nodes. Most of the time the sensors are turned off, until the root sensor wakes up the rest of the sensors. This process of awakening the nodes requires a certain amount of time since, in a unit of time, a sensor can awaken only one of its children. Obviously, the total wake-up time for all sensors depends on the order in which each sensor wakes up your children.

It is asked to design an efficient algorithm that gives a sorting of the children of each node in the tree providing the minimum time to wake up all the sensors.

The solution must use dynamic programming.

I have got no clue where to start from; I know dynamic programming exercises are based on suboptimal structure and overlapping problems, and in this case, at least, overlapping problems is quite obvious since the tree structure is used.

Have you got any clue about the underlying recurrence? -- I am not asking you the solution since those are my homework :)

Thanks.

$\endgroup$
1
$\begingroup$

Suppose that the root of the tree has subtrees $T_1,\ldots,T_m$, and that you found the optimal wake-up times $t_1,\ldots,t_m$ for each of the subtrees (that's the "dynamic programming" part, though I'd just call it recursion). In which order should you wake up the subtrees? If $t_i > t_j$, should you wake $T_i$ or $T_j$ first? Use this to come up with a recursive formula for the optimal wake-up time of the tree.

$\endgroup$
  • $\begingroup$ My question is, now, should I use a bottom-up algorithm? I mean, by $val[node] = 1$ if $node$ is a sheet and $val[node] =1 + \max_{\forall son \in sons(node)}{son}$, I am just getting a kind of "inverted deepness". Should I do it with memoization, maybe? Thank you a lot. $\endgroup$ – JnxF Nov 29 '17 at 14:28
  • 1
    $\begingroup$ You can implement this in many ways. Choose whatever is most convenient for you. In programming there is usually more than one correct answer. $\endgroup$ – Yuval Filmus Nov 29 '17 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.