5.1-1

Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure HIRE-ASSISTANT, implies that we know a total order on the ranks of the candidates.

Sol’n

rough draft:

Seems to show total relation, that is, for all \(a, b \in A,\) we must have either \(aRb\) or \(bRa.\) Maybe prove some of the other properties using proof by contradiction and carefully constructed examples.

5.1-2 ⭑

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\)?

Sol’n

rough draft:

Run the test repeatedly on each element, until a single winner is left.

5.1-3 ⭑

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\)?