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

RANDOM(a,b):
	if(a == b)
		return a
	mid = (a+b)/2
	r = RANDOM(0,1)
	if(r == 0)
		return RANDOM(a,floor(mid))
	else
		return RANDOM(ceil(mid),b)

running time Θ(lg(b-a))

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.