Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/ n, where n = (b-a+1)
my soln: 1.we can run random(0,1) b-a times....and sum up all the values generated........that is what i thought.......but smone told me that it is not correct coz sum follows binomial distribution, thus don't have equally like chance 2.on some site: RANDOM(a,b) range = b - a; d = the number of binary bits %range has do for(i = 1 to d): i th bit of integer res = rand(0,1); while(res >range); return (a + res); Each time of while loop need O(log(b-a)) time, and the expectation of that while loop is constant. Therefore, it takes time O(log(b- a))..........how does he say that "expectation of that while loop is constant"........m weak with probability.....plz enlighten me.... -- 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.
