5.1.md

Exercises 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.

Answer

always这个词表示对所有n!种组合，都能够确定，而这n!种组合已经囊括了所有的两两比较.

Exercises 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?

Answer

Without loss of generality we may assume that a = 0. Otherwise we can generate a random number between 0 and b − a, then add a to it.

solution

Each iteration of the while loop takes O(n) time to run. The probability that the while loop stops on a given iteration is (b+1)/(2^n). Thus the expected running time is the expected number of iterations of the while-loop times n. This is given by:

Since we assume a = 0 in the first, the final running time is: O(lg(b-a))

But this algorithm is non-deterministic.

Reference1: mathcamp.org Reference2: stackoverflow

Exercises 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?

Answer

while true:
	x = BIASED-RANDOM()
	y = BIASED-RANDOM()
	if x != y:
		return x

expected running time = 1/(2p(1-p))

---

Follow @louis1992 on github to help finish this task.