Skip to content

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)})$.