CLRS Exercises 5.1-2

Problem:

Describe an implementation of the procedure RANDOM(a, b) that only makes calls to
RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and
b?

Solution:

1. n = ceil(log(b-a+1))
2. decimal_number=0;
3. do
4. for i = 1 to n: get all binary
5. decimal_number = generate decimal from binary digits
6. while decimal_number > b-a+1
7. return decimal_number

Complexity:  Θ(log (b-a+1))

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:

Expand a random range from 1-5 to 1-7

Problem:
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
Solution:

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

Complexity: