CLRS Exercises 5.1-3:

Problem:

Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your
disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some
probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is.
Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased
answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected
running time of your algorithm as a function of p?

Solution:

1. Start while loop
2. a=rand(); b=rand()
3. if(a==0 && b==1) return 0;
4. else if(a==1 && b==0) return 1;
5. else continue;

Complexity: