5.1 The hiring problem¶
5.1-1¶
Show that the assumption that you are always able to determine which candidate is best, in line 4 of procedure HIRE-ASSISTANT, implies that you know a total order on the ranks of the candidates.
In mathematics, a total order or linear order is a partial order in which any two elements are comparable.That is, a total order is a binary $\geq$ relation on some set, which satisfies reflexive,transitive,antisymmetric and strongly connected relation.
- reflexive: since the procedure does not involve a candidate compares with himself, we can just assume that the candidate $i\geq i$
- transitive: The assumption that line 4 can determine which is best implies that the two candidates $i,best$, if $i\geq best$, then $i\geq j,j=0,1,...,i-1$, otherwise we can not ensure $i$ is the best.
- antisymmetric: $i\geq best\implies best\ngeq i$
- strongly connected: any two candidates can be comparable
$\star$ 5.1-2¶
Describe an implementation of the procedure RANDOM$(a,b)$ that makes calls only to RANDOM$(0,1)$. What is the expected running time of your procedure, as a function of a and b?
RANDOM(a, b)
range = b - a
if range == 0
return a + 0
bits = floor(log(2, range))+1
result = 0
for i = 1 to bits
r = RANDOM(0, 1)
result = result << 1 + r
if result > range
return RANDOM(a, b)
else return a + result
Each calling of RAMDOM(a,b) takes $\Theta(\lfloor\lg(b-a)\rfloor +1)=\Theta(\lg(b-a))$, the expected times of calling RAMDOM(a,b) is $\frac{2^{\lfloor\lg(b-a)\rfloor +1}}{(b-a)}=\Theta(1)$, expected running time of the procedure is $\Theta(\lg(b-a))$.
$\star$ 5.1-3¶
You wish to implement a program that outputs 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, but it outputs 1 with some probability $p$ and 0 with probability $1-p$, where $0 < p < 1$. 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$?
UNBIASED-RAMDON()
a=BIASED-RANDOM()
b=BIASED-RANDOM()
if a==0 and b==1
return 1
if a==1 and b==0
return 0
return UNBIASED-RAMDON()
Each calling of UNBIASED-RAMDON() take $\Theta(1)$, the expected times of calling UNBIASED-RAMDON() is $\frac{1}{2p(1-p)}$, the expected running time of this algorithm is $\Theta(\frac{1}{2p(1-p)})$.