Re: [algogeeks] Message distribution through rooted tree dynamic programming
Kumar think of the tree like this : d[node] is the minimum days required
for tree rooted at 'node' to be solved.
if node is a leave then the answer is zero.
Otherwise suppose 'node' has k children, and values to 'node's children are
like this d1 = d2 = ... = dk
then the answer for 'node' ( d[node] ) is max(d1 + 1, d2 + 2, ... , dk + k)
I can not prove it here for you, but you can check it on an arbitrary tree.
By the way, Where did you get this problem?
On Fri, Nov 8, 2013 at 8:47 AM, kumar raja rajkumar.cs...@gmail.com wrote:
I forgot to mention that the tree is n-ary tree, it need not be a binary
tree. So what is the approach ?
On 7 November 2013 01:04, Don dondod...@gmail.com wrote:
Atul, the depth is the important factor, not the number of nodes.
If you always pass the message to the deeper subtree first, followed by
the other subtree, you get the minimum number of rounds.
The problem is to compute the required number of rounds. This can be done
in a way similar to computing the depth of a tree. However, be careful to
handle the case where the subtrees take an equal number of rounds.
int numRounds(TreePtr t)
{
int result = 0;
if (t)
{
int L = numRounds(t-left);
int R = numRounds(t-right);
if (L == R) result = R + 2;
else result = 1 + max(L,R);
}
return result;
}
On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote:
we can first count number of nodes in a subtree below each node.Now
transfer message to max(count(root-left),count-root-right);
On 11/1/13, kumar raja rajkuma...@gmail.com wrote:
Suppose we need to distribute a message to all the nodes in a rooted
tree.
Initially, only the root
node knows the message. In a single round, any node that knows the
message
can forward it
to at most one of its children. Design an algorithm to compute the
minimum
number of rounds
required for the message to be delivered to all nodes.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
MeHdi KaZemI
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Message distribution through rooted tree dynamic programming
I forgot to mention that the tree is n-ary tree, it need not be a binary
tree. So what is the approach ?
On 7 November 2013 01:04, Don dondod...@gmail.com wrote:
Atul, the depth is the important factor, not the number of nodes.
If you always pass the message to the deeper subtree first, followed by
the other subtree, you get the minimum number of rounds.
The problem is to compute the required number of rounds. This can be done
in a way similar to computing the depth of a tree. However, be careful to
handle the case where the subtrees take an equal number of rounds.
int numRounds(TreePtr t)
{
int result = 0;
if (t)
{
int L = numRounds(t-left);
int R = numRounds(t-right);
if (L == R) result = R + 2;
else result = 1 + max(L,R);
}
return result;
}
On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote:
we can first count number of nodes in a subtree below each node.Now
transfer message to max(count(root-left),count-root-right);
On 11/1/13, kumar raja rajkuma...@gmail.com wrote:
Suppose we need to distribute a message to all the nodes in a rooted
tree.
Initially, only the root
node knows the message. In a single round, any node that knows the
message
can forward it
to at most one of its children. Design an algorithm to compute the
minimum
number of rounds
required for the message to be delivered to all nodes.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Message distribution through rooted tree dynamic programming
Atul, the depth is the important factor, not the number of nodes.
If you always pass the message to the deeper subtree first, followed by the
other subtree, you get the minimum number of rounds.
The problem is to compute the required number of rounds. This can be done
in a way similar to computing the depth of a tree. However, be careful to
handle the case where the subtrees take an equal number of rounds.
int numRounds(TreePtr t)
{
int result = 0;
if (t)
{
int L = numRounds(t-left);
int R = numRounds(t-right);
if (L == R) result = R + 1;
else result = max(L,R);
}
return result;
}
On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote:
we can first count number of nodes in a subtree below each node.Now
transfer message to max(count(root-left),count-root-right);
On 11/1/13, kumar raja rajkuma...@gmail.com javascript: wrote:
Suppose we need to distribute a message to all the nodes in a rooted
tree.
Initially, only the root
node knows the message. In a single round, any node that knows the
message
can forward it
to at most one of its children. Design an algorithm to compute the
minimum
number of rounds
required for the message to be delivered to all nodes.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+...@googlegroups.com javascript:.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Message distribution through rooted tree dynamic programming
Atul, the depth is the important factor, not the number of nodes.
If you always pass the message to the deeper subtree first, followed by the
other subtree, you get the minimum number of rounds.
The problem is to compute the required number of rounds. This can be done
in a way similar to computing the depth of a tree. However, be careful to
handle the case where the subtrees take an equal number of rounds.
int numRounds(TreePtr t)
{
int result = 0;
if (t)
{
int L = numRounds(t-left);
int R = numRounds(t-right);
if (L == R) result = R + 2;
else result = 1 + max(L,R);
}
return result;
}
On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote:
we can first count number of nodes in a subtree below each node.Now
transfer message to max(count(root-left),count-root-right);
On 11/1/13, kumar raja rajkuma...@gmail.com javascript: wrote:
Suppose we need to distribute a message to all the nodes in a rooted
tree.
Initially, only the root
node knows the message. In a single round, any node that knows the
message
can forward it
to at most one of its children. Design an algorithm to compute the
minimum
number of rounds
required for the message to be delivered to all nodes.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+...@googlegroups.com javascript:.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Message distribution through rooted tree dynamic programming
Suppose we need to distribute a message to all the nodes in a rooted tree. Initially, only the root node knows the message. In a single round, any node that knows the message can forward it to at most one of its children. Design an algorithm to compute the minimum number of rounds required for the message to be delivered to all nodes. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Message distribution through rooted tree dynamic programming
we can first count number of nodes in a subtree below each node.Now transfer message to max(count(root-left),count-root-right); On 11/1/13, kumar raja rajkumar.cs...@gmail.com wrote: Suppose we need to distribute a message to all the nodes in a rooted tree. Initially, only the root node knows the message. In a single round, any node that knows the message can forward it to at most one of its children. Design an algorithm to compute the minimum number of rounds required for the message to be delivered to all nodes. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
