After finished <Basic Engish> course & <engineering mathimatics> course, we started <Design and analysis of algorithms>.
Frankly, I don’t familiar with most of them, although I’m a programmer with over ten years of experiences. I believe the reason of this is I’m not an algorithm researcher, but IMHO most of the programmers in the world are not involved in algorithms everyday.

But I say, it’s better to learn(or review) more if you do have the time.

Here is my first stage exercise, only for chapter 1 & chapter 2. (which you can find I’m really not so familiar with the algorithms, XDXD)

韦国华(五期跟读学员) Email: jacky@rg4.net phone: 18601760035

习题一

1. 求下列函数的渐近表达式

渐近顺序：1 < sqrt(n) < log(n) < n < nlog(n) <n^2 <n^3…<2^n < ….n! <n^n

3n² + 10n <= 13n^2 à O(n^2)
n²/10+2ⁿ  à O(n^2)
21+1/n à 1
logn^3 = 3logn à log(n)
10log^3n = 30n à n

2. 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由

1. f(n) = logn²; g(n) = logn+5

解：
f(n) = logn²= 2 logn = 2(g(n)-5) = 2(g(n)) -10
所以f(n) = O(g(n)), f(n) =Ω(g(n))
所以f(n)=θ(g(n))

2. f(n) = logn²; g(n) = 根号n

解：
f(n) = 2 log(n) = 2*log((g(n))^2) = 4 log(g(n))
所以f(n) = O(log(g(n)))

3. f(n) = n; g(n) = log²n

解：
f(n) = n = 1/2(log²n) = 1/2(g(n))
所以f(n) =Ω(g(n))

4. f(n) = nlogn+n ;  g(n) = logn

解：
f(n) = nlogn + n = n(g(n)) + n
所以f(n) = O(g(n))

5. f(n) = 10; g(n) = log10

解:
f(n) = 10 = 10(log10) = 10(g(n))
所以：f(n) = O(g(n))= 1，且 f(n) =Ω(g(n)) = 1，即：f(n) = θ(g(n))

6. f(n) = log²n; g(n) = logn

解：
f(n) = log²n <= g(n)
所以：f(n) =Ω(g(n))

7. f(n) = 2ⁿ; g(n) = 100n²

解：
2ⁿ < 100n²
所以f(n) =Ω(g(n))

8. f(n) = 2ⁿ; g(n) = 3ⁿ

解：
2 ⁿ <= 3 ⁿ
所以f(n) =Ω(g(n))

3. 证明：如果一个算法在平均情况下的计算时间复杂性为θ(f(n))，则该算法在最坏的情况下所需的计算时间为Ω(f(n))

由于θ(g(n)) <= 0(g(n)), f(n) = θ(g(n)) è f(n) = O(g(n)), 当n à 无穷大时，f(n) / g(n) = C，C为大于0的常数。
于是θ(f(n)) =θ(C*g (n)) èθ(g(n))
根据θ(f(n))的定义（讲义P10~11）可得，f(n) = θ(g(n)), 表示 f(n) = O(g(n)) 并且f(n) =Ω(g(n))
f(n) =Ω(g(n)) =Ω(g(n)/C) è Ω(f(n))

习题二

1. 设a[0 : n-1]是已排好序的数组。请改成二分搜索算法，使得当搜索元素x不在数组中时返回小于x的最大元素位置i和大于x的最小元素j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

解：

/**
* 习题二 1
* 1. 设a[0 : n-1]是已排好序的数组。请改成二分搜索算法，使得当搜索元素x不在数组
* 中时返回小于x的最大元素位置i和大于x的最小元素j。当搜索元素在数组中时，i和j相
* 同，均为x在数组中的位置。
**/

#include <stdio.h>
#include <stdarg.h>

/**
* function name
* return:
*    1: input number exists, return with the seq index id in pointer seqid1 and seqid2
*    2: input number does not exist, return with the smaller number’s seq index id pointer seqid1, and larger number’s seq index id in seqid2
**/
int binary_search(int a[], int x, int n, int* seqid1, int* seqid2)
{
int low, high, mid;
low = 0, high = n -1;

while(low < high)
{
mid = (low + high)/2;
if (a[mid] == x)
{
*seqid1 = *seqid2 = mid;    //only happens while n is even, and right in the middle of the array
return 2;
}
if (x > a[mid])
low = mid + 1;
else
high = mid – 1;
}

if (low == high)
{
if (a[low] > x)             //happens input number index is smaller than the value in the array’s middle(index)
{
*seqid1 = low – 1;
*seqid2 = low;
}
else if (a[low] == x)  //happens when array length is even, and input number exists.
{
*seqid1 = *seqid2 = low;
return 2;
}
else if (a[low] < x)   //happens input number index is larger than the value in the array’s middle(index)
{
*seqid1 = low;
*seqid2 = low + 1;
}
return 1;
}

//will never happen
return -1;
}

int main()
{
int input_seq[] =
{
1, 3, 5, 7, 23, 34, 65, 100,
134,222,321,333,432,1234,13413
};
int input_key = 100;

int seqid1, seqid2, ret;
ret = binary_search(input_seq, input_key, sizeof(input_seq)/sizeof(int), &seqid1, &seqid2);

if (ret == 2)
{
printf(“case 1: input number %d exists in the position %d\n”, input_key, seqid1);
}
else if (ret == 1)
{
printf(“case 1: input number %d does not exist, its value is between %d and %d, which is %d, %d\n”, input_key, seqid1, seqid2, input_seq[seqid1], input_seq[seqid2]);
}

return 0;
}

2. 对任何非零偶数n，总可以找到奇数m和正整数k，使得n=m2^k。为了求出两个n阶矩阵的乘积，可以把一个n阶矩阵分成m*m个子矩阵，每个子矩阵有2^k*2^k个元素。当需要求2^k*2^k的子矩阵的积时，使用Strassen算法。设计一个传统方法与Strassen算法相结合的矩阵相乘算法，对任何偶数n，都可以求出两个n阶矩阵的乘积。并分析算法的计算时间复杂性。

解：
A和B分别代表两个input的矩阵，C代表输出的结果矩阵
N代表2^k的子矩阵

            N11 N12   …  N1m
N12 N22   …  N2m
A(m*m) =   …   …   …   ….
Nm1 Nm2  …  Nmm

            N11 N12   …  N1m
N12 N22   …  N2m
B(m*m) =   …   …   …   ….
Nm1 Nm2  …  Nmm

用传统方法求矩阵A*矩阵B

       C11     C12          A11    A12     B11    B12
C =                   =
C21     C22          A21    A22     B21    B22

C11 = A11*B11 + A12*B21
C12 = A11*B12 + A12*B22
C21 = A21*B11 + A22*B21
C22 = A21*B12 + A22*B22

所以此分治法的时间复杂度应满足：
T(2) = 1                                     m = 2      (8次乘法 + 4次加法)
T(m) = 8T(m/2) + O(m2)=O(m³)  m > 2      (8个m/2阶方阵的乘法 + 4个m/2阶方阵的加法)

Strassen求2^k阶方阵N的时间复杂度，直接套讲义P41结果
T(k) = 1                                     k=0
T(k) = 7T(k-1) = O(7^k)                k>0

即最终的时间复杂度为O(7^km³)

以下伪代码参考自网上，不过，我并没看出来哪儿对了, L
void strassen(int n, A, B, C)
{
if (n == 2)
MATRIX-MULTIPLY(A, B, C);
else
{
strassen(n/2, A11, B12 – B22, M1);
strassen(n/2, A11 + A12, B22, M2);
strassen(n/2, A21 + A22, B11, M3);
strassen(n/2, A22, B21 – B11, M4);
strassen(n/2, A11 + A22, B11 + B22, M5);
strassen(n/2, A12 + A22, B21 + B22, M6);
strassen(n/2, A11 – A21, B11 + B12, M7);

merge(C);
}
}

3. 设n个不同的整数排序后存于T【0 : n-1】中。若存在一个下标i, 0 <= i < n，使得T[i] = i，设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为O(logn)。

http://www.xinx.sdnu.edu.cn/sfzx/jpsykc/xlcad/xu02.html#%2865%29

解：

• 适用分治法求解问题的基本特征：
  • 该问题的规模缩小到一定的程度就可以容易地解决；
  • 该问题可以分解为若干个规模较小的相同问题;
  • 分解出的子问题的解可以合并为原问题的解；
  • 分解出的各个子问题是相互独立的。
• 很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。

/**
* Function name:
* Return:
*    search x in the array a, return the index id if exists, otherwise return -1                                                                     **/
int binary_search2(int [] a, int x, int n)
{
int left = 0; int right = n – 1;
while (left <= right)
{
int middle = (left + right)/2;
if (x == a[middle])
return middle;
if (x > a[middle])
left = middle + 1;
else
right = middle – 1;
}
return -1;
}

算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。

4. 设T[0 : n-1]是n个元素的数组。对任一元素x，设S(x) = {i|T[i]=x}。当|S(x)| > n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0 : n-1]是否有一个主元素。

解：
该算法的主要思想是确定数组中是否许多元素值是相同的，并且总共的元素总数超过n/2。
#include<iostream>
#include <ctime>

using namespace std;

#define SWAP(a,b) {int t;t=a;a=b;b=t;}

/************************************************************************/
/* P42                                                                  */
/************************************************************************/
int partition3(int R[], int low, int high)
{
int x = R[low];
int i = low, j = high + 1;
while (1)
{
while (R[–j] >= x); //can not see why this can not work in VS2008 with SP1 installed
while (R[++i] < x);
if (i >= j)
break;
SWAP(R[i], R[j]);
}
R[low] = R[j];
R[j] = x;

return j;
}

int partition(int R[], int low, int high)
{
int x = R[low];
int i = low, j = high;
while (1)
{
while (R[j] >= x)
j –;
while (R[i] < x)
i ++;
if (i >= j)
break;
SWAP(R[i], R[j]);
}
R[low] = R[j];
R[j] = x;

return j;
}

/************************************************************************/
/* It seems there are bugs in the code of function QuickSort() which is */
/* listed in P43, at least it can be improved. Try run the test code I’ve*/
/* marked in main() */
/************************************************************************/
void QuickSort(int R[],int low,int high)
{
if(low<high)
{
//int q = partition_2(R,low,high,R[low]);
int q = partition(R,low,high);
if (q <= 0) return;
QuickSort(R,low,q-1);//对左半段排序
if (q < high)
QuickSort(R,q+1,high);//对右半段排序
}
}

int find_major_element(int *R,int low,int high, int length)
{
QuickSort(R, low, high);
int t = R[length/2];

int count = 0;

for(int i=low;i<=high;i++)
{
if(R[i]==t)
count++;
}

if(count > length/2)
return 1;
else
return 0;
}

int main()
{
int n=0;
cout<<“Please input the random array length you want to generate:”;
cin>>n;
int *R=new int[n];
srand((unsigned)time(0));
for(int i=0;i<n;i++)
{
R[i] = rand()%2;
cout<<R[i]<<” “;
}
cout<<endl;

//test array
/*
n = 5;
R[0] = 1;
R[1] = 0;
R[2] = 1;
R[3] = 1;
R[4] = 1;
*/

int result = find_major_element(R,0,n-1, n);
if(result==0)
printf(“this array does not have major element\n”);
else
printf(“this array has a major element:%d”, R[n/2]);

delete[] R;

return 0;
}

5. 试用栈栈来模拟递归，消去算法QuickSort中的递归，并证明所需的栈空间为O(logn)。

需整个重写QuickSort，代码参考网上资料，有待修改完善

#include “stdlib.h”

//#define MAXNODE 20
//#define ISIZE 8
//#define NSIZE0 7
//#define NSIZE1 8
//#define NSIZE3 15
#define SHOWCHAR 1

//binary tree
typedef struct BTNode
{
int data;
BTNode *rchild;
BTNode *lchild;
}BTNode;

typedef struct ABTStack
{
BTNode *ptree;
ABTStack *link;
}ABTStack;

static pCounter = 0;//计数器,记录节点个数

//前序遍历函数，非递归算法
void pre_Order_Access(BTNode *head)
{
BTNode* pt;
ABTStack *ps,*top;
pt = head;
top = NULL;
printf(“二叉树的前序遍历结果《非递归》:\n”);

while (pt != NULL || top != NULL) //遍历未结果，或堆栈非空
{
while (pt != NULL)
{
if (SHOWCHAR)
printf(“%c    “, pt->data);//visit root node
else
printf(“%d    “, pt->data);
ps = (ABTStack*)malloc(sizeof(ABTStack));//根节点进栈
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild;//遍历节点右子树，经过的节点依次进栈
pCounter ++;
}
if (top != NULL)
{
pt = top->ptree; //栈顶节点出栈
ps = top;
top = top->link;
free(ps);     //释放栈顶节点空间
pt = pt->rchild;   //遍历节点右子树
}
}

}

//中序遍历函数《非递归算法》
void mid_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps, *top;
int counter = 1;
pt = head;
top = NULL;
printf(“二叉树的中序遍历结果《非递归》：”);

while (pt != NULL || top != NULL)
{
while (pt != NULL)
{
ps = (ABTStack*)malloc(sizeof(ABTStack));
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild;//遍历节点右子树，经过的节点依次进栈
pCounter ++;
}
if (top != NULL)
{
pt = top->ptree;//栈节点出栈
ps = top;
top = top->link;
free(ps);
if (SHOWCHAR)
printf(“%c    “, pt->data);
else
printf(“%d    “, pt->data);
pt = pt->rchild;
}
}

}

//后序遍历函数《非递归算法》
void last_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps, *top;
int counter = 1;
pt = head;
top = NULL;
printf(“二叉树后序遍历结果《非递归》：”);

while (pt != NULL || top != NULL)
{
while (pt != NULL)
{
ps = (ABTStack*)malloc(sizeof(ABTStack));
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild;
pCounter ++;
}
if (top != NULL)
{
pt = top->ptree;
ps = top;
top = top->link;
free(ps);
printf(pt->data);
pt = pt->rchild;
}
}
}