Re: [algogeeks] Re: Directi question
int no_of_steps[arr_length] = {MAX};
if ( (arr_length==0) || (arr[0] == 0) ) //if there are no elements or
the very first element is 0 - we can't jump anywhere
return MAX;
no_of_steps[0] = 0; //no jumps required to jump from element 0 to itself.
for (int i=1; iarr_length; i++)
{
no_of_steps [i] = MAX;
for(int j=0; ji; j++) //from 0th element till the element we need
to jump to.
{
if( arr[j] = (i - j) )//if it is possible for us to jump from
jth element to ith element.
{
if( no_of_steps[i] no_of_steps[j] + 1)// if no. of steps to
reach the ith element recorded till now is greater than the no of
{ //
steps reqd to reach jth element + 1, then replace.
no_of_steps[i] no_of_steps[j] + 1;
}
}
}
}
coutno_of_steps[n-1];
On Mon, Jul 9, 2012 at 8:32 PM, Mr.B sravanreddy...@gmail.com wrote:
There is a greedy solution discussion about this approach. I don't have a
formal proof for this.
Any counter example will be helpful.
at every place 'k' .. do the following.
-- find max ( a[k+i]+i ) where 1 = i = a[i]
for the given example:
A = {4 0 0 3 6 5 4 7 1 0 1 2}
initially a 4, the loop will be.
0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
now at 6. (since, you can't reach end.)
5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, == 10 is max. jump to 7.
make another step. (but you can reach the end.) so jump to last.
this is greedy approach.. and a linear time soultion.
On Monday, 9 July 2012 09:32:08 UTC-4, Akshat wrote:
Given an array A and the elements stored in an array denotes how much
jump an element can make from that array position. For example there is an
array A = {4 0 0 3 6 5 4 7 1 0 1 2}
Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
are stuck if you end up at 0.
You have to output the minimum number of jumps that can be made from
starting position to end position of an array.
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question
^ cout no_of_steps[arr_length -1];
On Mon, Jul 9, 2012 at 8:44 PM, algo bard algo.b...@gmail.com wrote:
int no_of_steps[arr_length] = {MAX};
if ( (arr_length==0) || (arr[0] == 0) ) //if there are no elements
or the very first element is 0 - we can't jump anywhere
return MAX;
no_of_steps[0] = 0; //no jumps required to jump from element 0 to itself.
for (int i=1; iarr_length; i++)
{
no_of_steps [i] = MAX;
for(int j=0; ji; j++) //from 0th element till the element we need
to jump to.
{
if( arr[j] = (i - j) )//if it is possible for us to jump from
jth element to ith element.
{
if( no_of_steps[i] no_of_steps[j] + 1)// if no. of steps to
reach the ith element recorded till now is greater than the no of
{ //
steps reqd to reach jth element + 1, then replace.
no_of_steps[i] no_of_steps[j] + 1;
}
}
}
}
coutno_of_steps[n-1];
On Mon, Jul 9, 2012 at 8:32 PM, Mr.B sravanreddy...@gmail.com wrote:
There is a greedy solution discussion about this approach. I don't have a
formal proof for this.
Any counter example will be helpful.
at every place 'k' .. do the following.
-- find max ( a[k+i]+i ) where 1 = i = a[i]
for the given example:
A = {4 0 0 3 6 5 4 7 1 0 1 2}
initially a 4, the loop will be.
0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
now at 6. (since, you can't reach end.)
5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, == 10 is max. jump to 7.
make another step. (but you can reach the end.) so jump to last.
this is greedy approach.. and a linear time soultion.
On Monday, 9 July 2012 09:32:08 UTC-4, Akshat wrote:
Given an array A and the elements stored in an array denotes how much
jump an element can make from that array position. For example there is an
array A = {4 0 0 3 6 5 4 7 1 0 1 2}
Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
are stuck if you end up at 0.
You have to output the minimum number of jumps that can be made from
starting position to end position of an array.
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question
There is a greedy solution discussion about this approach. I don't have a
formal proof for this.
Any counter example will be helpful.
at every place 'k' .. do the following.
-- find max ( a[k+i]+i ) where 1 = i = a[i]
for the given example:
A = {4 0 0 3 6 5 4 7 1 0 1 2}
initially a 4, the loop will be.
0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
now at 6. (since, you can't reach end.)
5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, == 10 is max. jump to 7.
make another step. (but you can reach the end.) so jump to last.
this is greedy approach.. and a linear time soultion.
On Monday, 9 July 2012 09:32:08 UTC-4, Akshat wrote:
Given an array A and the elements stored in an array denotes how much jump
an element can make from that array position. For example there is an array
A = {4 0 0 3 6 5 4 7 1 0 1 2}
Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
are stuck if you end up at 0.
You have to output the minimum number of jumps that can be made from
starting position to end position of an array.
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
farthest from 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. won't v2 be farthest from r? or we are talking about alternate pats also Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jun 20, 2012 at 6:25 PM, adarsh kumar algog...@gmail.com wrote: As you traverse along and find the diameter of the tree, keep track of the number of nodes thereby traversed. Let that be equal to n. Now, centre is the node corresponding to floor((n+1)/2). On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: I am asking again .. can any one please suggest better method for getting the median on the longest path of the tree .. efficient method . On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to
Re: [algogeeks] Re: Directi question-centre of the tree
@ashish it wont be...first we r finding one end from any node dat is r n den frm dat end we r traversing to other deepest end... it is possible dat r b d intermediate node...n distance from r to v2 is smaller than from r to v1 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
I am asking again .. can any one please suggest better method for getting the median on the longest path of the tree .. efficient method . On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/* *msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
As you traverse along and find the diameter of the tree, keep track of the number of nodes thereby traversed. Let that be equal to n. Now, centre is the node corresponding to floor((n+1)/2). On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: I am asking again .. can any one please suggest better method for getting the median on the longest path of the tree .. efficient method . On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/ **msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi Question
@maddy: The students should be assigned consecutive books only. That is, u
CANNOT assign book 1, 2 and 5 to a single student. either assign book 1, 2
and 3 or 1 and 2 or any such combination of consecutive numbers.
On Thursday, June 14, 2012 12:26:09 PM UTC+5:30, algogeek wrote:
In a library there are N books with the number of pages in i th book given
by bi . These books are to be distributed among K students such that the
difference between the largest sum of pages in the books assigned to any
student and the smallest sum of number of pages in the books assigned to
any student is minimum for the given input. Also the books are arranged in
a certain order and this order must never be changed.
For eg:
suppose B[ ] contains the number of pages in each book.
then
N=6
K=3
B={3,7,8,2,6,4}
then the output will be 0 as we can give book 1 and 2 to student 1 and
book 3 and 4 to student 2 and the remaining to student 3. That makes 10
pages for student 1 10 for 2 and 10 for 3 and thus the difference is 0
similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/7jAw-C4JI1AJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
+ 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Hemesh singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi Question
On Jun 16, 2:1@shubham
couldnt understand following logic in you algo please explain
when first k elemnts traversed then traverse again k elemnts of B
and
S[2*k-i]+=B[i])...again S[i-2*k]+=B[i][.so on till B is traversed
completely.
6 am, Shubham Sandeep s.shubhamsand...@gmail.com wrote:
wat constraints does dis bring in the question... Also the books are
arranged in a certain order and this order must never be changed.
does this imply --- a student gets only consecutivly numbered book
if not then
sort the array B in decreasing order in Onlogn
take another array S of k elements
traverse B(sorted)
S[i]=B[i]
when first k elemnts traversed then traverse again k elemnts of B and
S[2*k-i]+=B[i])...again S[i-2*k]+=B[i][.so on till B is traversed
completely..
On Sat, Jun 16, 2012 at 2:22 AM, Hemesh Singh hemesh.mn...@gmail.comwrote:
At first look it appears to be a simple problem of discrete binary
search. Take sum of b[i] as the upper_bound and 0 as the lower bound. Then
apply a simple binary search for the number of pages that can be given to a
student. Complexity : O(N log( sum( B ) ) )
On Thu, Jun 14, 2012 at 12:26 PM, algogeek
dayanidhi.haris...@gmail.comwrote:
In a library there are N books with the number of pages in i th book
given by bi . These books are to be distributed among K students such that
the difference between the largest sum of pages in the books assigned to
any student and the smallest sum of number of pages in the books assigned
to any student is minimum for the given input. Also the books are arranged
in a certain order and this order must never be changed.
For eg:
suppose B[ ] contains the number of pages in each book.
then
N=6
K=3
B={3,7,8,2,6,4}
then the output will be 0 as we can give book 1 and 2 to student 1 and
book 3 and 4 to student 2 and the remaining to student 3. That makes 10
pages for student 1 10 for 2 and 10 for 3 and thus the difference is 0
similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/JjKITS_gN9UJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Hemesh singh
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi Question
@Dave - Can you please explain how did you generate the series? Shouldn't it be : 1/2 + 2(1/4) + 3(1/8) and so on? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/p0QMbnK5zUIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi Question
Dave shouldn't it be :: E(x) = Summation( xp(x) ) thus it should be 1*1/2 + 2*(1/2 * 1/2) + 3*(1/2 * 1/2 * 1/2) . On Sun, Aug 7, 2011 at 11:55 AM, Nitish Garg nitishgarg1...@gmail.comwrote: @Dave - Can you please explain how did you generate the series? Shouldn't it be : 1/2 + 2(1/4) + 3(1/8) and so on? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/p0QMbnK5zUIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
Traverse the tree inorder. Store the values in an array. Find the element in the middle of the array. On Sun, Aug 7, 2011 at 8:57 AM, subramania jeeva subramaniaje...@gmail.comwrote: 5 /\ 6 7 / 8 Here the centre is both 5 and 6 . we need to find both of them..:) Cheers ~ Jeeva ~ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi Question
Probability of getting an even sum in one roll is 1/2.. Thus, expected number of rolls required to get even sum is inverse of that i.e. 2. Alternatively, Going by basics... Let P(x) be probability of getting Even sum in x rolls. P(1) = 1/2(Even) P(2) = (1/2) * (1/2) (Odd + Odd) P(3) = (1/2) * (1/2) * (1/2) (Odd + Even + Odd) P(4) = (1/2) * (1/2) * (1/2) * (1/2) (Odd + Even + Even + Odd) So on Expected number is given by Summation( X*P(x) )...i.e. 1*(1/2) + 2*(1/4) + 3*(1/8) + 4*(1/16) + (theoretically infinite terms) Let this sum be S. Thus, S = (1/2) + (2/4) + (3/8) + (4/16) + (5/32) + S / 2 = (1/4) + (2/8) + (3/16) + (4/32) + S - (S/2) = (1/2) + (2-1)/4 + (3-2)/8 + (4-3)/16 + (5-4)/32 + Thus, S/2 = (1/2) + 1/4 + 1/8 + 1/16 + 1/32 + (theoretically infinite terms) R.H.S. is GP which evaluates to 1. Thus, S = 2. Thus, expected number of rolls required to get even sum is 2. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi Question
@kunal patil: how can u say Probability of getting an even sum in one roll is 1/2 if tht is the case..can u find the ans in one go if the dice is having *5 faces*?? i mean the numbers on dice are 1 2 3 4 5 ...and it is unbiased... what will be the *Probability of getting an even sum in one roll*?? PS:ur explanation for basic method(alternative one) was awesome..:) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/klq4DPvoyvIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi Question
@kunal patil expected number of rolls required to get even sum is inverse of that i.e. 2 can we say like this all the time ? i have understood the alternative method, thanks :D On Sun, Aug 7, 2011 at 1:33 PM, Kunal Patil kp101...@gmail.com wrote: Probability of getting an even sum in one roll is 1/2.. Thus, expected number of rolls required to get even sum is inverse of that i.e. 2. Alternatively, Going by basics... Let P(x) be probability of getting Even sum in x rolls. P(1) = 1/2(Even) P(2) = (1/2) * (1/2) (Odd + Odd) P(3) = (1/2) * (1/2) * (1/2) (Odd + Even + Odd) P(4) = (1/2) * (1/2) * (1/2) * (1/2) (Odd + Even + Even + Odd) So on Expected number is given by Summation( X*P(x) )...i.e. 1*(1/2) + 2*(1/4) + 3*(1/8) + 4*(1/16) + (theoretically infinite terms) Let this sum be S. Thus, S = (1/2) + (2/4) + (3/8) + (4/16) + (5/32) + S / 2 = (1/4) + (2/8) + (3/16) + (4/32) + S - (S/2) = (1/2) + (2-1)/4 + (3-2)/8 + (4-3)/16 + (5-4)/32 + Thus, S/2 = (1/2) + 1/4 + 1/8 + 1/16 + 1/32 + (theoretically infinite terms) R.H.S. is GP which evaluates to 1. Thus, S = 2. Thus, expected number of rolls required to get even sum is 2. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
@Everyone: Wladimir has posted the correct solution to the problem and it is
an O(N) bottom up solution.
*The original solution:*
On Wednesday, 6 October 2010 21:10:40 UTC+5:30, wladimirufc wrote:
Find the leaf of tree then put all leaf in a queue.
While queue not empty:
remove u from queue
remove u of tree
if some v adjacent a u become leaf
insert v in queue
the last vertice is the center of the tree
Let me expand on the solution for a bit.
*Definition:*
1. For the purposes of this solution, a *leaf node* is defined as a node
having only one edge connected to it.
*Visualization:*
Think about the tree being flattened onto a table and laid out in a circular
fashion.
eg.
1
/ / \ \
4 2 3 7
/\
5 6
\
8
can be laid out as:
4 3
\ /
1 -- 7
|
2
/\
5 6
\
8
Now, wrap a rubber band around the layout and start tightening it.
At every stage, you'll be getting rid of nodes with only a single edge (so
called leaf nodes)
Stop when you end up with either a single node or a pair of nodes connected
by an edge.
*For example, *
remove leaf nodes as:
Step 1: 8,5,4,3,7
Step 2: 6,1 (Note: 2 is not removed as it has 2 connecting edges)
The center of the tree is thus 2.
*Proof of correctness:*
Let T be a tree for which D(u, v) = D(v, u) = C is the maximum possible.
It is obvious that both u and v must be leaf nodes since u..v is a diameter
of the graph.
Also, any non-leaf node w on the path u...v has M(w) M(u) or M(v) since
D(u, v) = D(u, w) + D(w, v)
Consider all such diameters of the tree graph T.
Let the pairs (u1, v1), (u2, v2)... (uk, vk) represent the nodes of a
diameter of the graph.
Consider the subgraph G' = G - {u1, u2, ..., uk, v1, v2, .. vk}
The diameter of G' is C-2. The center(s) of the graph is/are unchanged.*
Applying this reduction multiple times, any tree's undirected graph
representation
can be reduced to a graph of diameter 0 or 1.
*Base cases: *
Graph of diameter 0: The node itself is the center.
Graph of diameter 1: The pair of connected nodes are the center of the
graph.
*Note:* The connectedness of the graph is maintained at every stage of the
reduction process as no bridge nodes are ever removed.
** Proof of reduction of diameter by 2:*
Let us assume that the diameter of G' is C-1 with the nodes making up the
diameter being (p, q).
Therefore atleast one of p and q is a leaf node in G.
But since we removed all the leaf nodes in the reduction process, both p and
q must be internal nodes.
Hence the diameter of G' cannot be C-1.
By removing the 2 end nodes on a diameter of G, we are assured that there
exists a path of length C-2 in G'.
Since the diameter is an integral value and G' cannot have a diameter =
C-1, therefore the diameter
of G' is C-2.
** Proof of non-changing nature of the center:* *(slightly hand-wavy, I
would appreciate slightly more formality)*
Since the reduced graph G' has all the nodes of the original diameter
(except the leaf nodes) present and the
diameter of the graph G is also present as one of the diameters of graph G',
the center of the graph is
still present in G'.
Taking all these parts together proves the result and also provides the
algorithm for obtaining the result
in O(N).
Hope you enjoyed it!
--
DK
http://gplus.to/divyekapoor
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/dBlYluR4wvIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
Codechef Ques(Initiative of Directi) use DFS, BFS or Floyd Warshall... :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi Question
@kunal patil:
U were proceeding in correct way...in next series u cud hav seen a
formation of arithmatico geometric series...
It doesnt matter what the value of no of faces in a dice is..ans will
be always 2...:)
My simplified soln: o+e+1
o=probability of odd number coming in 1
throw of dice
In case o e are mutually exclusive the
ans is always 2...(and in even odd case like
here e+o=1...so ans is always 2...let n be
anything)
On 8/8/11, Kunal Patil kp101...@gmail.com wrote:
@Shady :
No...we can say this only at the time when following constraints are
satisfied:
1) *Outcome* of event *should be* *binary*. (In above example Sum can have
binary outcomes only i.e. EVEN or ODD)
2) Random variable x in P(x) should be supported on set {1,2,3,4,} i.e.
It *should start from 1* and then take on *contiguous values*.
3) *Sequence* *of probabilities* for x,x+1,x+2,... *must form a GP*.
(In above sum P(1)=1/2; P(2)=1/4; P(3)=1/8 forms GP)
Taking another simple example having biased coin:
P(H) -- 1/4
P(T) -- 1 - 1/4 = 3/4.
Say we want to find out expected number of coin tosses required to get first
head.
(Outcome is binary and random variable starts from 1 can take contiguous
values.Also, sequence of probabilities form a GP.)
You may verify that answer comes out to be 1/P(H) -- 1/(1/4) -- 4
@ never_smile: If I understand your question correctly then Probability
of getting even sum in one roll is P(2) + P(4)
For e.g. say
P(1) -- 1/5
P(2) -- 2/5
P(3) -- 1/5
P(4) -- 0
P(5) -- 1/5
P(even in one roll) -- 2/5 + 0 -- 2/5.
P(even in one roll) = 2/5;
P(even in 2 rolls) = (3/5)*(3/5);
P(even in 3 rolls)=(3/5)*(2/5)*(3/5)
This probability sequence doesn't form a GP.
Thus, above formula should not be applied you should calculate E[x] by
trivial method.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sent from my mobile device
nEvEr sMiLe bUt kEEp lAuGhIn'
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
@KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
From any node, find the farthest node by DFS, save its location(say A). Now start DFS from A, and reach the farthest node, say B. AB will be diameter of tree and longest path. The central node will be the centre of tree. O(n) solution. On Jul 27, 1:53 am, sivaviknesh s sivavikne...@gmail.com wrote: we can do like creating an adjacency matrix..populate all values i.e. cost to reach each node...finally find the nodes that has min value...any other gud solutions?? On Wed, Jul 27, 2011 at 2:16 AM, sivaviknesh s sivavikne...@gmail.comwrote: the question is clear..you draw the sample test case and work out .. you will understand 1 / / \ 4 2 3 /\ 5 6 here from node 2 the maximum cost to reach any node 'i' is 2 and minimum is 1 ...so M(2) = max(1,2)=2..the same is the case for node 1 also ...if you consider node 4 , to reach 6 , cost is 3similar is applicable for other nodes therefore centre = min(M(1..6)) = 1 and 2. ...hope u got me!! On Wed, Jul 27, 2011 at 2:08 AM, siva viknesh sivavikne...@gmail.comwrote: -- Forwarded message -- From: jayapriya surendran priya7...@gmail.com Date: Sep 29 2010, 9:41 pm Subject: Directi question-centre of the tree To: Algorithm Geeks In graph theory, atreeis defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) Thecenterof atreeis the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a validtreeas defined above. Output the node labels of thecenter(or centers) of thetree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- Regards, $iva -- Regards, $iva -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi Question
@Shady: There is a 1/2 probability of getting an even number on the first roll. In the 1/2 of the cases where the first roll is odd, roll again and note that there is a 1/2 chance of getting an odd number. Etc. The probability of needing n rolls is 1/2 to the nth power. The series is 1 + 2 * (1/2) + 3 * (1/4) + 4 * (1/8) + Call the infinite sum S: S= 1 + 2 * (1/2) + 3 * (1/4) + 4 * (1/8) + Then 1/2 S = 1 * (1/2) + 2 * (1/4) + 3 * (1/8) + . Subtract the two series, getting 1/2 S = 1 +1/2 + 1/4 + 1/8 + So 1/2 S = 2, and S = 4. The expected number of rolls needed to that the sum is even is 4. Dave On Aug 6, 9:34 am, shady sinv...@gmail.com wrote: Hi, A fair dice is rolled. Each time the value is noted and running sum is maintained. What is the expected number of runs needed so that the sum is even ? Can anyone tell how to solve this problem ? as well as other related problems of such sort -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi question-centre of the tree
5 /\ 6 7 / 8 Here the centre is both 5 and 6 . we need to find both of them..:) Cheers ~ Jeeva ~ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
the question is clear..you draw the sample test case and work out .. you will understand 1 / / \ 4 2 3 /\ 5 6 here from node 2 the maximum cost to reach any node 'i' is 2 and minimum is 1 ...so M(2) = max(1,2)=2..the same is the case for node 1 also ...if you consider node 4 , to reach 6 , cost is 3similar is applicable for other nodes therefore centre = min(M(1..6)) = 1 and 2. ...hope u got me!! On Wed, Jul 27, 2011 at 2:08 AM, siva viknesh sivavikne...@gmail.comwrote: -- Forwarded message -- From: jayapriya surendran priya7...@gmail.com Date: Sep 29 2010, 9:41 pm Subject: Directi question-centre of the tree To: Algorithm Geeks In graph theory, atreeis defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) Thecenterof atreeis the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a validtreeas defined above. Output the node labels of thecenter(or centers) of thetree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- Regards, $iva -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
we can do like creating an adjacency matrix..populate all values i.e. cost to reach each node...finally find the nodes that has min value...any other gud solutions?? On Wed, Jul 27, 2011 at 2:16 AM, sivaviknesh s sivavikne...@gmail.comwrote: the question is clear..you draw the sample test case and work out .. you will understand 1 / / \ 4 2 3 /\ 5 6 here from node 2 the maximum cost to reach any node 'i' is 2 and minimum is 1 ...so M(2) = max(1,2)=2..the same is the case for node 1 also ...if you consider node 4 , to reach 6 , cost is 3similar is applicable for other nodes therefore centre = min(M(1..6)) = 1 and 2. ...hope u got me!! On Wed, Jul 27, 2011 at 2:08 AM, siva viknesh sivavikne...@gmail.comwrote: -- Forwarded message -- From: jayapriya surendran priya7...@gmail.com Date: Sep 29 2010, 9:41 pm Subject: Directi question-centre of the tree To: Algorithm Geeks In graph theory, atreeis defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) Thecenterof atreeis the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a validtreeas defined above. Output the node labels of thecenter(or centers) of thetree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- Regards, $iva -- Regards, $iva -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
I am thinking on these lines. Start from any node. DFS to the fartheset node from there. let the farthest node be B. Start a new DFS from B to reach the fartheset node from B , let that be C. It can be proved that BC is the longest path in the tree. Then, the node in the center will be the answer to the question. Incase the path length is even we will have two nodes. I havent proved it yet, the second part of my solution. this was a quick thought. On Sep 29, 9:41 pm, jayapriya surendran priya7...@gmail.com wrote: In graph theory, a tree is defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) The center of a tree is the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a valid tree as defined above. Output the node labels of the center(or centers) of the tree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi question-centre of the tree
I don't understand what you mean when you say minimum among all the nodes in the graph. In any case, your definition of centre of tree looks similar to the closeness centrality measure - http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html#Closeness I doubt you can do it in O(N)... On Sep 29, 12:41 pm, jayapriya surendran priya7...@gmail.com wrote: In graph theory, a tree is defined as a graph on N nodes,and (N-1) un-directed edges such that there are no cycles in the graph.Each node has a single unique path to every other node. Let D(u,v) be the number of edges in the unique path from node 'u' to node 'v' (or from node 'v' to 'u' since the edges are un-directed).D(u,u) is 0 for all nodes 'u'. M(u)=MAX(D(u,i):for all nodes i) The center of a tree is the node (or nodes) 'u',for which M(u) is minimum among all the nodes in the graph. You'll be given a graph which has N nodes (1=N=20).The nodes are labeled 1,2,3,..N.You will be provided with N-1 edges in the form of a b pairs where 1=a,b=N.No edge will be repeated.You can assume that the edges are specified such that the graph is a valid tree as defined above. Output the node labels of the center(or centers) of the tree. Sample Input: 6(value of N) 1 3 (edges) 1 4 1 2 2 5 2 6 Sample Output 1 2 Expected:O(N) complexity algo can anyone plz help me out with O(N) algo? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
