Some formulas about combinatorics

\begin{equation} C_{n+1}^{k+1} = C_n^k + C_n^{k+1} \end{equation} \begin{equation} C_k^k + C_{k+1}^k + \cdots + C_n^k = C_{n+1}^{k+1} \end{equation}

clrs Exercise 5.3-3

Suppose that instead of swapping element $A[i]$ with a random element from the subarray $A[i \ldots n]$, we swapped it with a random element from anywhere in the array:

PERMUTE-WITH-ALL(A)
n = A.length
for i = 1 to n
    swap A[i] with A[RANDOM(1,n)]

Does this code produce a uniform random permutation? Why or why not?

Of course, this is a popular problem and there are tons of posts and papers written on it. Here's one from Coding Horror

clrs Exercise 5.2-2

Ref http://clrs.skanev.com/05/02/02.html
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?
You hire twice when you first hire is the candidate with rank $i$ and all the candidates with rank $k > i$ come after the candidate with rank $n$. There are $n - i$ better suited candidates and the probability of the best one coming first is $1/(n-i)$ (we can ignore the other candidates and they don't affect the probability). Thus, the probability for hiring twice if your first candidate has rank $i$ is:
$$ \Pr\{T_i\} = \frac{1}{n}\frac{1}{n-i} $$
The first part reflects the probability of picking that particular candidate out of $n$.
The probability to hire twice is:
$$ \Pr\{T\} = \sum_{i=1}^{n-1}\Pr\{T_i\} = \sum_{i=1}^{n-1}\frac{1}{n}\frac{1}{n-i} = \frac{1}{n} \sum_{i=1}^{n-1}\frac{1}{i} = \frac{1}{n} \Big(\lg(n-1) + \O(1)\Big) $$

死理性派恋爱法：拒绝掉前面37%的人

游戏规则：假设MM 可以对$n$个男生的优劣进行排名，并且不到男生前来表白，MM也没法知道究竟谁才是the one，$n$个男生会以一定顺序表白。 MM一定会首先试试水深，先处几个玩玩，等到发现比以前都好的，和这个男生发展关系，游戏结束。 问题：MM应该先和多少个男生处着玩，才能以最大的概率最终遇到到那个最合适的the one 假设先拒绝掉前$k$个男生，$k$取小了，可能还没等the one出现，游戏就结束了；$k$取大了，可能the one很不幸的成炮灰被刷掉了。 对于某个固定的 $k$，如果最适合的人出现在了第 $i$ 个位置（$k < i \leq n$），要想让他有幸正好被 MM 选中，就必须得满足前 $i-1$ 个人中的最好的人在前 $k$ 个人里，这有 $k/(i-1)$ 的可能

\begin{eqnarray*} \Pr(k) = \sum_{i=k+1}^n \frac{1}{n} \cdot \frac{k}{i-1} &=& \frac{k}{n} \sum_{i=k+1}^n \frac{k}{i-1}\\ &=& \frac{k}{n} \left(\frac{1}{k}+\frac{1}{k+1}+\cdots +\frac{1}{n-1} \right) \\ &=& \frac{k}{n}\cdot \frac{1}{n} \cdot \left( \frac{1}{\frac{k}{n}} + \frac{1}{\frac{k+1}{n}} + \cdots + \frac{1}{\frac{n-1}{n}} \right) \end{eqnarray*}

令$\frac{k}{n}=x,n \to +\infty$,上式可化为积分$x\int_x^1\frac{1}{t}\,dt = -x\ln x$. 求导, $\frac{k}{n}=x=\frac{1}{e}$

clrs problems 4-5 chip testing

Chip A says	Chip B says	Conclusion
B is good	A is good	both are good, or both are bad
B is good	A is bad	at least one is bad
B is bad	A is good	at least one is bad
B is bad	A is bad	at least one is bad

Pair-wise comparison

• Pick any two chips and test them together
• If we have the first outcome then pick any of the two chips and throw it away. Put the other into the output set.
• If we have any of the other outcomes throw away both chips.
• Repeat this until we have at least two chips available
• If we are left with only one chip then add it to the output set if the number of tests with the first outcome is even and throw it away otherwise.

The recurrence for the problem is T(n) = T(n/2) + n/2

Master Theorem of Dive-and-Conquer

\[ T(n) = aT(n/b)+f(n) \] Then $ T(n) $ has the following asympotic bounds:

1. If $f(n) = O (n^{\log_b a - \epsilon})$ for some constant $\epsilon>0$, Then $T(n) = \Theta(n^{log_b a})$
2. If $f(n) = \Theta (n^{log_b a})$, Then $T(n) = \Theta(n^{log_b a}\lg n)$
3. If $f(n) = \Omega(n^{log_b a + \epsilon})$ for some constant $\epsilon>0$, and if $af(n/b) \leq cf(n)$ for some constant $c \leq 1$ and all sufficiently large $n$, then $T(n)=\Theta(f(n))$

Maximum subarray O(n)

输入：数组arr
输出：maximum subarray，[begin, end)

1. 初始化result为- ∞，begin0 = 0, begin = begin0
2. 从前往后扫描，如果当前局部和大于result，更新result为局部和，更新begin = begin0, 更新end = i+1,
3. 如果局部和小于0，更新begin0 = i+1, 更新局部和为0

int maximum_subarray(int *arr, int len, int &begin, int &end)
{
    begin = 0;
    end = 1;
    int sum = 0, result = INT_MIN;
    int begin0 = 0;
    for (int i = 0; i < len; i++) {
        sum += arr[i];
        if (sum > result) {
            result = sum;
            begin = begin0;
            end = i + 1;
        }
        if (sum < 0) {
            begin0 = i + 1;
            sum = 0;
        }
    }
    return result;
}