5.1 The hiring problem
5.1-1
Because we are always able to determine which candidate is best, that means we can compare any two candidates and know which is better. Thus we are able to sort the candidates based on this knowledge, which implies that we know a total order on the ranks of the candidates.
5.1-2
First we find the smallest number p
, such that 2^p > b - a
. Then call RANDOM(0, 1)
to generate p
bits, thus we have a random number r
. If r + a <= b
, then that's what we want, otherwise we regenerate r
. (Link 1, link 2)
import math
import random
def random_number(a, b):
bits = math.ceil(math.log2(b - a + 1))
while True:
number = random_binay(bits)
if a + number <= b:
return a + number
def random_binay(bits):
number = 0
for i in range(bits):
number = number * 2 + random.randint(0, 1)
return number
The running time of function random_binay
is $O(\lg{(b - a)})$. And it's possible that we need to call random_binay
multiple times if a + number > b
, but that doesn't affect the expected running time, since $cO(\lg{(b - a)})$ is still $O((\lg{(b - a)}))$.
Thus the expected running time is $O(\lg{(b - a)})$.
5.1-3
We can call BIASED-RANDOM
twice to get two numbers x
and y
. The results would be 0, 0
, '1, 0', '0, 1', '1, 1', with probability (1 - p)(1 - p)
, p(1 - p)
, (1 - p)p
, pp
respectively. Since p(1 - p) = (1 - p)p
, we can treat one as 0
and the other as 1
. So we can generate 0 with probability 1/2 and 1 with probability 1/2.
The probability to generate 0, 1
and 1, 0
is $2p(1 - p)$, so we have to try $\frac{1}{2p(1 - p)}$ times. Thus the expected running time is $O(\frac{1}{p(1 - p)})$.
def unbiased_random():
while True:
x = BIASED-RANDOM()
y = BIASED-RANDOM()
if x != y:
return x