Cloud computing Books

http://blog.sina.com.cn/s/blog_6edef4580100t0oy.html

The Boost C++ Libraries

 The Boost C++ Libraries
http://en.highscore.de/cpp/boost/

http://www.boost.org/

How to use Boost in Visual Studio 2010
 http://stackoverflow.com/questions/2629421/how-to-use-boost-in-visual-studio-2010

1. Unzip the latest version of boost (1.48.0 12/11/2011) into a directory of your choice (e.g. d:\boost_1_48_0).
2. Create a new empty project in Visual Studio 2010.
3. Open the Property Manager and expand one of the configuration for the platform of your choice.
4. Select & right click Microsoft.Cpp..user, and select Properties to open the Property Page for edit.
5. Select VC++ Directories on the left.
6. Edit the Include Directories section to include the path to your boost source files.
7. Repeat steps 3 - 6 for different platform of your choice if needed.

Boost Image Processing (GIL) http://stlab.adobe.com/gil/presentation/index.htm Boost Graph Library http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/index.html

Big Data --Petabyte

http://en.wikipedia.org/wiki/Petabyte
giga tera peta

Pigs Get Fat, Hogs Get Slaughtered!

Pigs get fat, Hogs get slaughtered!

I love this proverb, it tells me the most important business rule.

How to design a parking lot?

how to fit data into two probability density functions?

tic-tac-toe OOD design

How to post source code in blogspot

http://vivianningyang.blogspot.com/2009/05/how-to-post-source-code-in-blogspotcom.html

Correlation does not imply causation

http://en.wikipedia.org/wiki/Correlation_does_not_imply_causation

smart_ptr vs weak_ptr

http://stackoverflow.com/questions/4984381/in-c-shared-ptr-and-weak-ptr-differences

Suffix tree

http://en.wikipedia.org/wiki/Suffix_tree



http://mila.cs.technion.ac.il/~yona/suffix_tree/

Rectangle overlap

From Crack a google interview lecture notes.

Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and
returns any pair of rectangles that overlaps, if there is such a pair. Axis‐aligned
means that all the rectangle sides are either parallel or perpendicular to the x‐ and
y‐axis. You can assume that each rectangle object has two variables in it: the x‐y
coordinates of the upper‐left corner and the bottom‐right corner.

Good Answer:
1. Create a sorted array of the x coordinates of the left and right edges of
the rectangles.
2. Then, use a "scanline" to move from left to right through the
rectangles.
3. Keep a binary search tree containing the y coordinates of the top and
bottom edges of the rectangles that overlap the scanline.
     For each element of the array, check whether it is a left or right edge.
      -If it is a right edge, remove the corresponding top and bottom edges from the BST.
      -If it is a left edge, search the BST for rectangles that overlap the current rectangle;
                                   if there is one, return the overlap.

Then, add the y coordinates of the top and bottom edges of the rectangle to the BST.
The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles
and each of the 2n iterations takes O(log n) time.

Linear programming: maximal sum of subsequence

maxim_subsequence( int num_arr[]; int size)

{

  int sum=0;

  int sum_max = 0;



  for(int i=0; i

 {

    sum +=num_arr[i];

    if(sum>sum_max)

      sum_max = sum;

   else if(sum<0) //sum will not contribute to new maximum subsequence.

         sum=0;

}

  return sum_max;

}

Array rearranging algorithm

/*Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an algorithm to change

this array to a1, b1, a2, b2, ..., an, bn.*/
a1, b1   ok

a1, a2, b1, b2-> a1, a2<->b1, b2-> a1, b1, a2, b2 ok

a1,a2,a3,a4,b1,b2,b3,b4 -> a1 a2 (b1 b2), (a3,a4), b3, b4-> it becomes 2 subproblems of the above



//size of arr_num must be even number

void rearrange(int arr_num[], int p, int q)

{



if ( p == q || g == p+1) return;

int r = (q+p)/2;



//Exchange: (p+r)/2........r<----> r+1......(r+q)/2

for(int i = (p+r)/2; i

{

int temp= arr_num[i];

arr_num[i]=arr_num[r+1+i];

arr_num[r-1+i] = temp;

};



rearrange(arr_num, p, r);

rearrange(arr_num, r+1, q);

return;



}

贪吃蛇走法

给一个吸地毯的irobot，和一个长方形的屋子，四面有墙，四个指令：
Bool moveForward（）//向前走一格，走不了的话返回false
Void Rotate（int degree）//就是左拐右拐
Bool isClean（）//当前单元格是否干净
Void clean（）
把irobot 扔在屋子任意位置，写代码让irobot清理房间，每一格都要走过（单元格没有坐标）。

Stack and Queue

Can we implement a Queue using stack(s)?


Can we implement a minimum stack using stacks?


minimum stack has the following operation:
1. push, pop
2. get minimum.

What is a good OOD design answer?

1. Classes, subclasses.

2. relationship: is-a, has-a, 1->n, n->n

3. design pattern: singleton, observer, MVC.

4. flexible, extendable, reusable.

i.e. How to design a Parking lot?

Property of bitwise XOR

Can we prove?
number = number XOR number XOR number

This kind of property is useful some problems: odd man out.

Find Two Numbers in an Array that Sum to a Particular Value

//array of integer and a given value, a function to tell if the array contains 2 elements whose sum is equal to the value

bool is_sum_num( int num_arr[], int size, int sum)


quicksort(num_arr, size);
 //This part can be optimized in O(n).
 //Question for reader: how to do it? 
 for ( int i = 0; i

How can we check whether a BT is a BST?

const int MIN_VALUE = -50000;
const int MAX_VALUE = 50000;

bool isValidBST( node *root) {
return isvalidHelper(root, MIN_VALUE, MAX_VALUE);
}

bool isvalidHelper(node *root, int min, int max) {
  if(root == null) return true;
if ( root->value < min || !isvalidHelper(root->left, min, root->value)
return false;
if ( root->value > max || !isvalidHelper(root->right, root->value, max)
return false;

return true;

}

25 horses problem

http://www.youtube.com/watch?v=oaePKvHhUEA

把BT 同一层的sibling 连起来，constant 内存

struct Node {
    int value;
    Node *left;
    Node *right;
    Node *sibling; 
};


//把BT 同一层的sibling 连起来，constant 内存.
//
//                  1  -->null
//               /     \
//              2   -->  3  -->null
//            /       /    \
//          7     --> 8   -> 4  -->null
//
//
//开始没要求constant, 用queue记录每层的结点 O(n)即可. 后来要求constant，在提示下才搞定。
//先让不知道答案的xdjm想想吧。回头贴我的做法。
void connect_sibling( Node *root ) {
    root->sibling = null;
    Node *cur, *dummy;
    dummy = new Node;

    while( root ) {  //dummy->slibling是指向上次下一层的最左节点。
        cur = dummy;  //这样保证dummy->slibling总指向最左节点
        while( root ) {   // 找上一层的最右边节点， 假设当前层sibling已连好。

            if( root->left ) {
                cur->sibling = root->left;
                cur = root->left;
            }

            if(root->right){
                cur->sibling = root->right;
                cur = root->right;
            }

            root = root->sibling; //上一层的下一个姐妹，直到最右边。
        } //end of while second loop
        //此时，下一层已串好。

        cur->sibling = null; //最右边下一层填空。
        root = dummy->sibling; //上层的右一个节点。
    }
    delete dummy;
}

TopCoder Tutorial

http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static

String permutation

// Stringpermutation.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include 
#include 
#include 
using namespace std;


void swap(char* a, char* b) 
{
 if (*a == *b ) return;

 char temp;
 temp = *a;
 *a = *b;
 *b = temp;
}

void permutate( char* Str, int index )
{
    int i = 0;
    if( index == strlen(Str)-1 )
    { 
       // We get a permutation, print it
        printf("%s \n",Str);
        return;
    }

 permutate(Str, index+1);

    for( i = index+1; i < strlen(Str); i++ )
    {

        int j;
        for( j = index;j < i;j++ )
            if( Str[j] == Str[i] )
                     break;
        if(j==i) 
        {
          swap( Str+index, Str+i ); 
          permutate( Str, index + 1 );
          swap( Str+index, Str+i );
        };

    }
}


int _tmain(int argc, _TCHAR* argv[])
{
 char str[] = "Abc";
 permutate( str, 0 );
 system("pause");

 char str2[] = "aabc";
 permutate( str2, 0 );
 system("pause");

 
 char str3[] = "acadc";
 permutate( str3, 0 );
 system("pause");

 return 0;
}

First nonrepeated character in a string

//First nonrepeated character in a string
char first_unique_char_in_string(const string a)
{
  //suppose string is composed of alphabets only ( a~z).
    unsigned char count[26];
    for(int i=0; i<26; i++) count[i] = 0; //initialize
    for(int i=0; i        count[a[i]-'a']++;
    for(int i=0; i        if(count[a[i]-'a']==1)
            return a[i];

    return -1; //no unique char.

}

Movie tickets problem

/* You have two movie tickets and want to invite a friend to watch movie
together. You can invite several friends simultaneously. Each one of them
independently has probability p to accept your invitation. How many friends
should you invite to maximize the probability that exactly one friend
accepts your invitation?*/

Suppose we invite n persons.

P=n*(1-p)^(n-1)*p   //independently, sum

f(n)=ln(P)=ln(n)+(n-1)ln(1-p)+ln(p)   //log

df/dn=1/n + ln(1-p) = 0   //derivative to get local max,

n = -1/ln(1-p) = 1/p;  when x-->0,  -ln(1-x) = x+x^2/2 + x^3/3 + ...

function to reverse digits of an integer

//Write a function to reverse digits of an integer. E.g. 456 --> 654, -7800 --> -87.
int ReverseDigits (int n){
    int ret = 0;
    while (n){
        ret = ret * 10 + n % 10;  //mod 10.
        n /= 10;  //div
    }
    return ret;
}

Efficiently remove duplicate white space from a string

//输入一个字符串，把连续的空格合并成一个。
void remove_duplicate_space(char *p)
{
    char *r=p, *w=p; //r: read, w: write
    while (*r != '\0') {
      if (*r!=' ' || *(w-1) != ' ')
      { *w = *r; w++; r++;}
      else
        r++;
    }
    if (r!=w) *w = '\0';
}

Flood Fill

//http://www.mitbbs.com/article_t1/JobHunting/31909771_0_5.html
//白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡序
//列），上坡时：如果
//有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
//知道过完为止。
int water(int * a, int n){
  stack > mystack;
  int water = 0;
  for(int i = 0; i    while(!mystack.empty() && mystack.top().second <= a[i]){ //上坡
      int bottom = mystack.top().second; //底
      mystack.pop();
      if( mystack.empty())  //堆栈中只有一个元素，不能形成底。
        break;
      int top = mystack.top().second < a[i]?  mystack.top().second:  a[i];  //找到顶（次大数）

      int length = i - mystack.top().first - 1;  //长度
      water = water + (top-bottom)* length;  //填充
    }  //当前上坡处理完。
    mystack.push(make_pair(i, a[i]));  //下坡，进堆栈。

    //上坡无底的话，是什么都不做的，因为上次进堆栈的元素直接出堆栈了，只是查了一下底（至少两元素在堆栈）。
  }
  return water;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int value[10] = {5,5,1,7,1,1,5,2,7,6};


    int result=0;

    cout << result;

    result = water(value, 10);
    cout << result;

    return 0;
}

lambda function in C++0x

Lambda function in C++0x

1. Simplify code. good for simple predicate (i.e. a condition check);
[](//input parameters){ //lambda function body}

2. Anonymous call, function to be defined at the point it is needed.

3. Lambda function can only use global variable and passed parameters, just as a math function, i.e.
sin, cos, pow etc.

4. No local variable in the containing scope, special capture operation has to be defined, if you want to
use the local variables, i.e. [=] by value, [&] by reference.

C++ const: why and how-- a really messy feature

I was even asked during a job interview, const keyword can be put in 5 places, make it 5 meanings, pls refer to: http://duramecho.com/ComputerInformation/WhyHowCppConst.html

A nice data mining course handout

recommendation system, pagerank, mapreduce etc: http://i.stanford.edu/~ullman/mining/2009/index.html

Who is the greatest inventor ever since?

Someone asked me: who is the greatest scientist?
A name comes to my mind: Thomas Edison.
What's his contribution? I am asking myself. Light Bulb?
He has 1093 granted patents around the world (he applied much more than that).
Finally I see, his biggest invention is to massively produce patents/inventions.

Forming industrial lab to massively produce patents/inventions just
as his friend Henry Ford did to form a streamline to massively produce
cars.

C++ 11 (C++0x ) concurrency

the most important addition to C++11 is concurrency, here is an introduction
video:

http://www.corensic.com/Learn/Resources/ConcurrencyTutorialPartOne.aspx

an early book: C++ concurrency in Action.

The Biggest Changes in C++11 (and Why You Should Care):
http://www.codeproject.com/News/16244/The-Biggest-Changes-in-Cplusplus11-and-Why-You-Sho.aspx

C++11 - the recently approved new ISO C++ standard

http://www2.research.att.com/~bs/C++0xFAQ.html#lambda

Trie

Trie has wide application in "words": suggestion system,
phone book, spell check etc.

http://www.technicalypto.com/2010/04/trie-in-java.html


A lot of people was asked about Trie during interviews:
http://www.mitbbs.com/article_t/JobHunting/31926643.html

Point Cloud Library

http://www.ros.org/wiki/pcl

OpenKinect, OpenNI, and Skeleton Tracking

The image is from:
http://www.codeproject.com/KB/dotnet/KinectGettingStarted.aspx?display=Print

http://openkinect.org/wiki/Main_Page

Open Natural Interface:
http://openni.org/

Human Pose Estimation from a Depth Sensor
http://www.youtube.com/watch?v=Qca4qDspLyk&NR=1

Kinect for xbox360 spawn point:
http://research.microsoft.com/en-us/um/redmond/events/fs2010/presentations/Kudo_Fitzgibbons_Kinect_for_Xbox360_071210_FacSummit.pdf

Kinect for Xbox 360: The inside story of Microsoft's secret 'Project Natal'
http://www.wired.co.uk/magazine/archive/2010/11/features/the-game-changer

Key Kinect Technology Devised in Cambridge Lab
http://blogs.wsj.com/tech-europe/2010/11/08/key-kinect-technology-devised-in-cambridge-lab/

Research Papers:
http://openkinect.org/wiki/Research_Material

信念对一个人是多么地重要，一无所有的时候可以支撑一个人。

What's in the Microsoft XBox Kinect?

1. a video camera;
2. a scanning infra-red laser, the most interesting part; The kinect infra-red laserappears to project an infrared dot pattern all over the room:http://www.blogger.com/img/blank.gif
http://www.youtube.com/watch?v=dTKlNGSH9Po&feature=related

3. an infra-red camera;
patent: US20100118123 which explains how the 3D reconstruction works. The dots are grouped into sub-patterns, these patterns decrease in size with the distance. The 3x3 check board with different gray levels is used to calibrate the environment illumination.

(3x3 matrix of little dots with a reference dot in the middle of each matrix square. 3D is determined by the displacement of these dots, http://www.youtube.com/watch?v=vjYoNx-4KrU)

http://www.youtube.com/watch?v=_GSc3ptePTQ

IR Modded Canon Powershot A540 looks at Kinect IR output
http://www.youtube.com/watch?v=28JwgxbQx8w

You can see the check box pattern difference as the board moves far away from the IR emitter.

4. a motorized tilt mechanism;
5. a noise canceling microphone system: 4 mics in an array: one on the left, three on the right.

Hack Xbox Kinect:
http://www.makeuseof.com/tag/5-microsoft-xbox-kinect-hacks-blow-mind/

http://en.wikipedia.org/wiki/Kinect

kinect sdk will be released by MSR this summer.


http://www.makeuseof.com/tag/hack-kinect-kill-zombies/

http://www.makeuseof.com/tag/control-windows-pc-kinect/

Kinect™ for Xbox 360: Technology + Two Applications
http://www.cs.virginia.edu/~jfw3x/cs4501/

http://www.primesense.com

machine vision one person startup

Two completely technological background guy's one person startup:

http://www.3d3solutions.com/products/flexscan3d/


http://www.vrmesh.com/

没有天才，是下的功夫比别人大。

没有天才，是下的功夫比别人大。

怀念我的母亲

怀念我的母亲

四月的天气本是“芳菲尽”的季节，洛根（美国犹他北部的一个城市）的天仍飘着小雪
，远未到达“山寺桃花始盛开”的时候，从遥远的四川传来母亲过世的消息。
母亲已经与病痛奋斗好久了，求生意志很坚强，我知道这消息迟早会来，心理空落落的。

和母亲的生活点滴像电影一样浮现眼前，我去年年底几次去看母亲，母亲跟我很紧，眼
睛几乎没有离开过我。每当我茶杯里的茶稍微有点浅，母亲立马续上；吃饭时，母亲总
在关注我吃了什么，以便下顿的饭菜更合我的胃口；我一声轻轻的咳嗽，也会深深地揪
住母亲的心。母亲已经意识到此一别，会是永别。

回想母亲的一生，她卑微地就象路边的小草，有一滴露，她就会生长；才刚冒出尖尖头
，一只沉重的脚就压在了那雨后的嫩叶上，新叶立马碾作泥；但没关系，一片小芽又会
长出。日出日落，春夏秋冬，但母亲的倔强和勤劳终也没能改变她的命运。母亲病重时
常常讲起她小时候五几年发大水（母亲一辈子生活在汉江边），她的一个姐姐被洪水冲
走了，再也没找到；还有一个姐姐饿死了。言语之间无限感叹生命的不易。母亲小时候
也要过饭。母亲从来没向命运低过头，一生都在努力，辛劳一生的母亲晚年与癌症顽抗
地斗争，直到最后也没有放弃过。

母亲这一生最引以为傲的就是她的两个孩子，虽然家里很穷， 却养育了两个博士，这
是母亲最爱讲的故事，每每讲起就会一扫劳累的阴霾，疲惫的眼睛也会放光，脸上也会
露出一丝幸福的满足和自豪。母亲常唠叨她一辈子一无所有，就剩俩孩子。

母亲是文盲，连自己的名字也不会写，但母亲精于心算，中晚年以做小生意为生。母亲
常常提起，因为她的小儿子读到博士后，大儿子是留美博士，她在家乡小学门口卖点杂
货，别人也会敬她几分，不会撵她。

我小时候身体不好，支气管炎，经常气喘的上气不接下气，咳嗽。家里很穷，父亲母亲
经常背着我到处求医问药，我现在仍然回想起母爱温暖，宽厚的肩膀，母亲的气喘声。
我看过很多赤脚医生，也吃过各种各样、千奇百怪的偏方，病没看好，家倒是越来越穷
。后来听母亲说我因为身体不好吃奶到三岁，家里什么好吃的都留给了我。我还记得小
时候生产队，母亲晚上出工劳作后，集体食堂母亲带回来的白菜炖粉丝（母亲把自己的
一份省下的），长大后，我吃过各种各样的白菜炖粉条，但再也没有母亲带回来的美味。

母亲笃信佛教，我本有一个哥哥，听母亲说，不到三个月就走了，母亲一直以为是自己
命硬，克死了她的孩子，自此，母亲就再也没让我和弟弟叫过她一声妈妈，只叫阿姨，
直到她病故。母亲也曾带我要过饭，朴实的母亲相信，“吃百家饭”的孩子会得医治。

圣经上说，人本生于尘土，也归于尘土，母亲终于息了地上的劳苦，天堂里人人生而平
等，没有阶层，没有劳苦；人人生而得医治，没有痛苦，充满欢乐；愿母亲在天堂里获
得永生。

Technical Report< Paper < Patent < Project < Product

Technical Report< Paper < Patent < Project < Product

China: the new scientific superpower?

http://lemire.me/blog/archives/2011/02/07/china-the-new-scientific-superpower/

Country Rankings Computer science, Information system:

http://www.scimagojr.com/countryrank.php?area=1700&category=1710&region=all&year=2009&order=it&min=10&min_type=it