Re: [algogeeks] Directi question
This can be solved using Dynamic Programming approach.
Let MinJump(n) = Minimum number of Jumps required to reach the Nth index
of array A.
then, for 1 i N, MinJump(i) = Min{1 + MinJump(j)} for all j such that
(0= j i) and (j + A[j] = i).
We can prepare an auxiliary array say MinJump[1..N] where for MinJump[i]
contains the minimum jump required to reach ith
index of array A and use MinJump[1...i] and A[1i] to calculate the
value of A[i+1] and so on..
HTH,
Sumit
On Mon, Jul 9, 2012 at 7:02 PM, Akshat Sapra sapraaks...@gmail.com 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 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] Directi question
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 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] Directi question
http://www.geeksforgeeks.org/archives/13209
On Mon, Jul 9, 2012 at 7:02 PM, Akshat Sapra sapraaks...@gmail.com 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 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] Directi Question
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.
Re: [algogeeks] Directi Question
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] Directi Question
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.
Re: [algogeeks] Directi Question
If we get even number (probability 1/2) in first throw , so the expected run is 1 If first throw give ODD (probability 1/2) ,the run needed become 1 + run needed until second odd number .This last waiting time is 2 . Thus expected run become (1/2) (1) + (1/2)(1+2) = 2 On Sat, Aug 6, 2011 at 8:04 PM, 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. -- 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] Directi Question
let expected time is T , if we get even(probability 1/2) on first throw so T become 1 If dont then you are at same place where you started so T = (1/2) (1) + (1/2) ( 1+T) = T =2 On Sun, Aug 7, 2011 at 6:05 PM, rajul jain rajuljain...@gmail.com wrote: If we get even number (probability 1/2) in first throw , so the expected run is 1 If first throw give ODD (probability 1/2) ,the run needed become 1 + run needed until second odd number .This last waiting time is 2 . Thus expected run become (1/2) (1) + (1/2)(1+2) = 2 On Sat, Aug 6, 2011 at 8:04 PM, 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. -- 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] Directi Question
@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.
[algogeeks] Directi Question
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] Directi Question
Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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] Directi Question
1/6*5/6*5/6*3+ 1/6*1/6*5/6*3+ 1/6*1/6*1/6 =91/216 On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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] Directi Question
There are two cases: First if we get even number in first roll. So P(A)= 1/2 And if We get odd number in second roll, then we need keep rolling untill we find another odd number. So, (1/2)*[1/2] + 1/2*1/2*1/2 upto infinity. On Sat, Aug 6, 2011 at 8:46 PM, Nitin Gupta gupta.nitingupta.ni...@gmail.com wrote: 1/6*5/6*5/6*3+ 1/6*1/6*5/6*3+ 1/6*1/6*1/6 =91/216 On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- 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] Directi Question
Sorry, I mis understood the ques. On Sat, Aug 6, 2011 at 8:56 PM, Pankaj jatka.oppimi...@gmail.com wrote: There are two cases: First if we get even number in first roll. So P(A)= 1/2 And if We get odd number in second roll, then we need keep rolling untill we find another odd number. So, (1/2)*[1/2] + 1/2*1/2*1/2 upto infinity. On Sat, Aug 6, 2011 at 8:46 PM, Nitin Gupta gupta.nitingupta.ni...@gmail.com wrote: 1/6*5/6*5/6*3+ 1/6*1/6*5/6*3+ 1/6*1/6*1/6 =91/216 On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- 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] Directi Question
1-(5/6)^3 = 91/216 -- 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/-/oZi0vvu8SOgJ. 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] Directi Question
what about the first question guys ? On Sat, Aug 6, 2011 at 9:00 PM, Nitish Garg nitishgarg1...@gmail.comwrote: 1-(5/6)^3 = 91/216 -- 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/-/oZi0vvu8SOgJ. 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] Directi Question
On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216 so ans 1- 91/216 let me know how was the paper and the pattern *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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] Directi Question
Expected value of a random variable x is defined as E(x)= summation of xp(x) over all value of x where p(x) is the probability. so in this case E(x)= E(2)+E(4)+ E(6)+ . = 2*1/6 + 4* 3/(6*6)+ 6*10/(6*6*6) + . On Sat, Aug 6, 2011 at 9:19 PM, sukran dhawan sukrandha...@gmail.comwrote: On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216 so ans 1- 91/216 let me know how was the paper and the pattern *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- 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] Directi Question
Hey sry for my above post. I got a little confused. x is the no of times dice is rolled so e(x)=e(1)+e(2)+e(3)+ =1/2 + 2*1/(2*2) + 3*1/(2*2*2) + .. Please correct me if m wrong.. On Sat, Aug 6, 2011 at 10:54 PM, Kunal Yadav kunalyada...@gmail.com wrote: Expected value of a random variable x is defined as E(x)= summation of xp(x) over all value of x where p(x) is the probability. so in this case E(x)= E(2)+E(4)+ E(6)+ . = 2*1/6 + 4* 3/(6*6)+ 6*10/(6*6*6) + . On Sat, Aug 6, 2011 at 9:19 PM, sukran dhawan sukrandha...@gmail.comwrote: On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216 so ans 1- 91/216 let me know how was the paper and the pattern *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- Regards Kunal Yadav (http://algoritmus.in/) -- 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] Directi Question
I think this is correct. -- 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/-/5gZRPfLAwNYJ. 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] Directi Question
E(x)= 1 x (1/2) + 2 x (1/2 x 1/2 (Odd-Odd) + 1/2 x 1/2 (Even-Even) + 3 (1/4 x 1/2 (Odd-Odd-Even)+ 1/4 x 1/2 (Odd-Even-Odd)+ 1/4 x 1/2 (Even-Odd-Odd)+ 1/4 x 1/2(Even-Even-Even) )+ E(x)= 1/2 + 1 + 3/2 . According to me, since the series does not converge, Expectation value does not exist. @Kunal: For E(2)...The running sum can be even if (i) On the first die, we get an odd and then again an odd. (ii) On the first die, we get an even and then again an even. How have you considered only a single case? Please correct if I'm wrong. Regards, Mukul Gupta 3rd Year, COE NSIT On Sat, Aug 6, 2011 at 11:22 PM, Kunal Yadav kunalyada...@gmail.com wrote: Hey sry for my above post. I got a little confused. x is the no of times dice is rolled so e(x)=e(1)+e(2)+e(3)+ =1/2 + 2*1/(2*2) + 3*1/(2*2*2) + .. Please correct me if m wrong.. On Sat, Aug 6, 2011 at 10:54 PM, Kunal Yadav kunalyada...@gmail.comwrote: Expected value of a random variable x is defined as E(x)= summation of xp(x) over all value of x where p(x) is the probability. so in this case E(x)= E(2)+E(4)+ E(6)+ . = 2*1/6 + 4* 3/(6*6)+ 6*10/(6*6*6) + . On Sat, Aug 6, 2011 at 9:19 PM, sukran dhawan sukrandha...@gmail.comwrote: On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216 so ans 1- 91/216 let me know how was the paper and the pattern *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- Regards Kunal Yadav (http://algoritmus.in/) -- 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] Directi Question
According to me if we get even number in first case then the series will end there only as we just need an even sum. Similarly in case of e(3) the only possible sequence for which the sum is even in exactly 3 turns is odd then even and then odd. On Sat, Aug 6, 2011 at 11:40 PM, Mukul Gupta mukul.gupta...@gmail.comwrote: E(x)= 1 x (1/2) + 2 x (1/2 x 1/2 (Odd-Odd) + 1/2 x 1/2 (Even-Even) + 3 (1/4 x 1/2 (Odd-Odd-Even)+ 1/4 x 1/2 (Odd-Even-Odd)+ 1/4 x 1/2 (Even-Odd-Odd)+ 1/4 x 1/2(Even-Even-Even) )+ E(x)= 1/2 + 1 + 3/2 . According to me, since the series does not converge, Expectation value does not exist. @Kunal: For E(2)...The running sum can be even if (i) On the first die, we get an odd and then again an odd. (ii) On the first die, we get an even and then again an even. How have you considered only a single case? Please correct if I'm wrong. Regards, Mukul Gupta 3rd Year, COE NSIT On Sat, Aug 6, 2011 at 11:22 PM, Kunal Yadav kunalyada...@gmail.comwrote: Hey sry for my above post. I got a little confused. x is the no of times dice is rolled so e(x)=e(1)+e(2)+e(3)+ =1/2 + 2*1/(2*2) + 3*1/(2*2*2) + .. Please correct me if m wrong.. On Sat, Aug 6, 2011 at 10:54 PM, Kunal Yadav kunalyada...@gmail.comwrote: Expected value of a random variable x is defined as E(x)= summation of xp(x) over all value of x where p(x) is the probability. so in this case E(x)= E(2)+E(4)+ E(6)+ . = 2*1/6 + 4* 3/(6*6)+ 6*10/(6*6*6) + . On Sat, Aug 6, 2011 at 9:19 PM, sukran dhawan sukrandha...@gmail.comwrote: On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216 so ans 1- 91/216 let me know how was the paper and the pattern *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- Regards Kunal Yadav (http://algoritmus.in/) -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- 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] Directi Question
@Kunal: Perhaps, you are right :) On Sat, Aug 6, 2011 at 11:45 PM, Kunal Yadav kunalyada...@gmail.com wrote: According to me if we get even number in first case then the series will end there only as we just need an even sum. Similarly in case of e(3) the only possible sequence for which the sum is even in exactly 3 turns is odd then even and then odd. On Sat, Aug 6, 2011 at 11:40 PM, Mukul Gupta mukul.gupta...@gmail.comwrote: E(x)= 1 x (1/2) + 2 x (1/2 x 1/2 (Odd-Odd) + 1/2 x 1/2 (Even-Even) + 3 (1/4 x 1/2 (Odd-Odd-Even)+ 1/4 x 1/2 (Odd-Even-Odd)+ 1/4 x 1/2 (Even-Odd-Odd)+ 1/4 x 1/2(Even-Even-Even) )+ E(x)= 1/2 + 1 + 3/2 . According to me, since the series does not converge, Expectation value does not exist. @Kunal: For E(2)...The running sum can be even if (i) On the first die, we get an odd and then again an odd. (ii) On the first die, we get an even and then again an even. How have you considered only a single case? Please correct if I'm wrong. Regards, Mukul Gupta 3rd Year, COE NSIT On Sat, Aug 6, 2011 at 11:22 PM, Kunal Yadav kunalyada...@gmail.comwrote: Hey sry for my above post. I got a little confused. x is the no of times dice is rolled so e(x)=e(1)+e(2)+e(3)+ =1/2 + 2*1/(2*2) + 3*1/(2*2*2) + .. Please correct me if m wrong.. On Sat, Aug 6, 2011 at 10:54 PM, Kunal Yadav kunalyada...@gmail.comwrote: Expected value of a random variable x is defined as E(x)= summation of xp(x) over all value of x where p(x) is the probability. so in this case E(x)= E(2)+E(4)+ E(6)+ . = 2*1/6 + 4* 3/(6*6)+ 6*10/(6*6*6) + . On Sat, Aug 6, 2011 at 9:19 PM, sukran dhawan sukrandha...@gmail.comwrote: On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.comwrote: Microsoft written: What is the probability of getting atleast one 6 in 3 attempts of a dice? probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216 so ans 1- 91/216 let me know how was the paper and the pattern *Muthuraj R IV th Year , ISE PESIT , Bangalore* On Sat, Aug 6, 2011 at 7: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. -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- Regards Kunal Yadav (http://algoritmus.in/) -- 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. -- Regards Kunal Yadav (http://algoritmus.in/) -- 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] Directi Question
(for first outcome odd) 1/6 * 3/6 + (for first outcome even) 1/6 * 3/6 = 1/6 so expected 6 cases. On Sat, Aug 6, 2011 at 8:04 PM, 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. -- *MOHIT VERMA* -- 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] Directi question-centre of the tree
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.
