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.

Improve this question
$\endgroup$
0

    1 Answer 1

    Reset to default
    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.

    Improve this answer
    $\endgroup$
    2
    • $\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
      CommentedNov 29, 2017 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
      CommentedNov 29, 2017 at 14:45

    Start asking to get answers

    Find the answer to your question by asking.

    Ask question

    Explore related questions

    See similar questions with these tags.