Loading [MathJax]/jax/output/HTML-CSS/jax.js

Thursday, October 9, 2014

empty base class optimization: GCC vs MS visual studio



#include 
#include 
#include 
#include 
#include 
using std::cout;
using std::cin;
using std::endl;

class Base {
};
class Derived1:public Base {
 int i;
};
class Derived2:public Base {
public:
 Base b;
 int i;
};
class Derived3:public Base {
public:
 Derived1 d1;
 int i;
};

int main(int argc, char * argv[])
{
 cout << sizeof(Base) << endl;
 cout << sizeof(Derived1) << endl;
 /*Derived2 d2;
 cout << sizeof(d2) << endl;
 cout << &d2 << endl;
 cout << &d2.b << endl;
*/
 Derived3 d3;
 cout << sizeof(d3) << endl;

 return 0;
}

Different compilers produce different result.
MS gives 8 while GCC gives 12. This is a rare case I have ever experienced that MS beats GCC.

Thursday, April 24, 2014

Some formulas about combinatorics


Ck+1n+1=Ckn+Ck+1n Ckk+Ckk+1++Ckn=Ck+1n+1

Wednesday, April 16, 2014

clrs Exercise 5.3-3


Suppose that instead of swapping element A[i]A[i] with a random element from the subarray A[in]A[in], 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

Tuesday, April 15, 2014

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 ni better suited candidates and the probability of the best one coming first is 1/(ni) (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{Ti}=1n1ni
The first part reflects the probability of picking that particular candidate out of n.
The probability to hire twice is:
Pr{T}=n1i=1Pr{Ti}=n1i=11n1ni=1nn1i=11i=1n(lg(n1)+\O(1))



Saturday, March 29, 2014

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

游戏规则:假设MM 可以对n个男生的优劣进行排名,并且不到男生前来表白,MM也没法知道究竟谁才是the one,n个男生会以一定顺序表白。 MM一定会首先试试水深,先处几个玩玩,等到发现比以前都好的,和这个男生发展关系,游戏结束。 问题:MM应该先和多少个男生处着玩,才能以最大的概率最终遇到到那个最合适的the one 假设先拒绝掉前k个男生,k取小了,可能还没等the one出现,游戏就结束了;k取大了,可能the one很不幸的成炮灰被刷掉了。 对于某个固定的 k,如果最适合的人出现在了第 i 个位置(k<in),要想让他有幸正好被 MM 选中,就必须得满足前 i1 个人中的最好的人在前 k 个人里,这有 k/(i1) 的可能
Pr(k)=ni=k+11nki1=knni=k+1ki1=kn(1k+1k+1++1n1)=kn1n(1kn+1k+1n++1n1n)
kn=x,n+,上式可化为积分x1x1tdt=xlnx. 求导, kn=x=1e

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

Thursday, March 27, 2014

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(nlogbaϵ) for some constant ϵ>0, Then T(n)=Θ(nlogba)
  2. If f(n)=Θ(nlogba), Then T(n)=Θ(nlogbalgn)
  3. If f(n)=Ω(nlogba+ϵ) for some constant ϵ>0, and if af(n/b)cf(n) for some constant c1 and all sufficiently large n, then T(n)=Θ(f(n))