5.1 The hiring problem

没啥好说的，很经典的雇佣问题。做一下习题。

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.
这道题翻译过来就是，如果我们总能确定哪个候选人是最好的，请证明我们知道候选人们的全序。

solution:我们总能确定哪个候选人是最好的，这其实是一个很无敌的条件，这意味着，无论候选人出现的次序如何，我们都能唯一确定一个最佳候选人，说明我们能将任意两个候选人比较得出先后顺序，也就是说，我们知道候选人们的全序。

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?

Solution: 这道题刚开始的时候读错题了，尴尬，我以为是生成连续性的(0,1)中的值，心想这有什么难的，return a+(b-a)*RANDOM(0,1)不就完事了，后面发现RANDOM函数其实生成的是离散值，RANDOM(0,1)表示生成0和1的概率各是1/2。然后就有点不会做了..查了下答案，答案的思路是利用RANDOM(0,1)随机生成0，1值作为二进制值，然后证明这个随机生成的二进制值的概率是1/(b-a+1),继而算出期望。

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。

Solution：这道题我也不会做…看了答案觉得自己蠢死了…

unbiased-random(){
	while(1){
		a=biased-random();
		b=biased-random();
		if(a==0&&b==1) return 0;
		if(a==1&&b==0) return 1;
	}
}

其实就是利用了p(1-p)=(1-p)p。会生成01或10的概率是p(1-p)，E(x)=1/2p(1-p)。

5.2 Indicator random variables

这个小节提出了一个叫indicatior random variables的东西，很容易理解，但是却能在我们分析问题的时候使思路和公式变得清晰简洁。

indicator random variables有一个很简单的性质，它的期望等于其中一个事件发生的概率。

那么hiring problem的次数期望也就很容易得知：

5.2-1

In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability that you hire exactly n times?

solution：这个简单，只雇佣一次，也就是最好的assistant在第一个，这件事发生的概率是1/n，雇佣n次，也就是确定了一种排序：升序，概率是1/n!。

5.2-2

In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?

solution：这道题可以理解为，如果最好的assistant在第i位，那么前i-1中最好的在第一个。也就对1/(i-1)*n在 i=2到n求和。

5.2-3

Use indicator random variables to compute the expected value of the sum of n dice.

solution: 3.5n

5.2-4

Use indicator random variables to solve the following problem, which is known as the hat-check problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers who get back their own hat?

solution: 每个人拿到自己帽子的概率为1/n，期望是n*1/n=1.

5.2-5

solution: n(n-1)/4.

Randomized algorithms

这章首先探讨了一下什么是probabilistic analysis和randomized algorithms，probabilistic analysis其实是假设输入是随机的，而random algorithms是不管输入是怎么样的，我在算法的前面强制性的加入一个随机过程，使得输入随机化。

uniform random permutation

uniform random permutation：所有的permutation都是等可能性的产生。
然后开始介绍两种产生数组的uniform random permutation的方法，

permute-by-sorting
permute-in-place

这一章的内容没有很详细看。

Probabilistic analysis and further uses of indicator random variables

The birthday paradox

在一个房间里，如果有两个人同一天生日的概率是50%，至少需要多少人在房间里？

一个房间需要多少人同时在场才能有两个人同一天生日？

Balls and bins

平均情况下我们需要投多少次球才能让每个桶都有一个球？b

平均情况下我们需要投多少次球才能让特定的一个桶有一个球？blnb

Streaks

What is the longest streak of consecutive heads that you expect to see? Θ(logn)

The on-line hiring problem

在前面的hiring problem中，如果我们奉行一个这样的策略：在前i个雇员中不招人，雇用后面的雇员中比前面所有雇员更优秀的。

i取什么值表现最好？i=n/e。