Lecture 3（part 1）

Divide and conquer

1. the general paradim of algrithm as bellow:

1. divide the problem into subproblems;

2. conqure each subproblems recrusively;

3. combine solution

2. Some typical problem (part 1)

the matrix mutiplication(strassen's algorithm) and the vlsi layout problem will be in the note leceture part 2.

• binary search

/*-* MIT introduction of algrithm* Lecture 3: binary search* Fredric  : 2013-11-18*/#include
      
       #include
       
        typedef unsigned int uint;#define    MAX  11uint g_array[MAX] = {
    1,2,3,5,7,12,16,34,67,89,100};uint target = 100; //target numberint binarysearch(uint start, uint end);void main(void){        int n = 0;    printf("start to find the num:%d..\t\n", target);    if(-1 != (n = binarysearch(0, MAX-1))){        printf("the target %d has been found in num:%d", g_array[n],n);    }    system("pause");    return;}/*-* binary search recursive*/int binarysearch(uint start, uint end){    uint n   = (start + end)/2;    uint tmp = g_array[n];    if(target == tmp){        return n;    }else{        if(tmp > target){            return binarysearch(start, n);        }else{            return binarysearch(n+1,end);        }    }    return -1;}
       
      

• powering a number

/*-* MIT introduction of algrithm* Lecture 3: powering a number* Fredric  : 2013-11-17*/#include
      
       #include
       
        typedef unsigned int uint;//calculate the result of n^m, like n = 2, m = 3, result = 8uint n = 10;uint m = 7;// m > 1double power_number(uint n, uint m); /** main function*/void main(void){        double result    = 0.0;    result            = power_number(n,m);    printf("the result of %d^%d is %lf /t/n", n,m,result);    system("pause");    return;}/*-* powering a number* result = * n^(m/2) * n^(m/2)           if m is even* n^((m-1)/2) * n^((m-1)/2)*n if m is odd*/double power_number(uint n, uint m){    if(0 == m){        return 1;    }    if(0 == m%2){        return power_number(n,m/2)*power_number(n,m/2);    }else{        return power_number(n,(m-1)/2)*power_number(n,(m-1)/2)*n;    }}
       
      

• Fibonacci number（using matrix mutiplication）

/*-* MIT introduction of algrithm* Lecture 3: Fibonnaci,using the matrix method* Fredric  : 2013-11-17*/#include
      
       #include
       
        typedef unsigned int uint;/*-* Input:* pa00/01/10/11 according to the element of the Array Aij* n: the number of the fibonacci*/void fibonacci_number(uint *pa00, uint *pa01, uint *pa10,uint *pa11, uint n);void main(void){    uint a00 = 1;    uint a01 = 1;    uint a10 = 1;    uint a11 = 0;    uint num = 9;//num > 0    fibonacci_number(&a00,&a01,&a10,&a11, num);    printf("The num %d fibonacci number is:%d\t\n", num, a10);    system("pause");    return;}/*-* calculate the fibonacci number* f(n) = * 0 if n = 0;* 1 if n = 1;* f(n-1) + f(n-1) if n > 1* the divide and conquer algrithm is:*  fn+1 fn      1   1  *(        )  = (     )^n *  fn   fn-1    1   0*/void fibonacci_number(uint *pa00, uint *pa01, uint *pa10,uint *pa11, uint n){    uint tmp00 = *pa00;    uint tmp01 = *pa01;    uint tmp10 = *pa10;    uint tmp11 = *pa11;    if(1 == n){        return;    }else{        //Matrix mutiplication        *pa00 = tmp00 * tmp00 + tmp01 * tmp10;        *pa01 = tmp00 * tmp01 + tmp01 * tmp11;        *pa10 = tmp10 * tmp00 + tmp11 * tmp10;        *pa11 = tmp10 * tmp01 + tmp11 * tmp11;        if(0 == n%2){            fibonacci_number(pa00,pa01,pa10,pa11,n/2);        }else{            fibonacci_number(pa00,pa01,pa10,pa11,(n-1)/2);            uint tmp00 = *pa00;            uint tmp01 = *pa01;            uint tmp10 = *pa10;            uint tmp11 = *pa11;            *pa00 = tmp00 + tmp01;            *pa01 = tmp00;            *pa10 = tmp10 + tmp11;            *pa11 = tmp10;        }    }}