首页 C&C++ 数据结构与算法分析

# 完成在 10.2.3 节末尾描述的抽样算法的分析，并解释δ\delta 和ss 的值如何选择

让Rt,xR_{t,x} 成为样本XX 中元素tt 的秩，如果样本S′S' 的元素来源于SS, 则有
E(Rt,s)=N+1s+1Rt,s′E(R_{t,s})=\frac{N+1}{s+1}R{t,s'}
如果tt 是五分项中第三大的的元素，则有
E(Rt,s)=(Rt,s)(s−Rt,s(N+1)N−s)(s+1)2(s+2)=O(N/s)E(R_{t,s})=\sqrt{\frac{(R_{t,s})(s-R_{t,s}(N+1){N-s})}{(s+1)^2(s+2)}} = O(\sqrt{N/\sqrt{s}})
我们选择v1v_1 和v2v_2 以便于得到下式
E(Rv1,s)+2dV(Rv1,s)≈k≈E(Rv2,s)−2dV(Rv2,s)E(R_{v_1,s})+2dV(R_{v_1,s})\approx k \approx E(R_{v_2,s})-2dV(R_{v_2,s})
当dd 允许有许多方差后，则有
2∫d∞erf(x)=O(e−d2/d)2\int_{d}^{\infty}erf(x) = O(e^{-d^2}/d)
如果d=log⁡1/2Nd=\log^{1/2}{N}, 化简得
δ=ds=slog⁡1/2N\delta = d\sqrt{s} = \sqrt{s}\log^{1/2}{N}
最终得到N+k+O(s)+O(Nδ/s)N+k+O(s)+O(N\delta/s)
又因为s=Nδ/ss=N\delta/s, 最终δ\delta 和tt 选择
s=N2/3log⁡1/3Ns=N^{2/3}\log^{1/3}{N},δ=N1/3log⁡2/3N\delta = N^{1/3}\log^{2/3}N.

# 为什么 Strassen 算法在 2×2 短阵的乘法不使用可交换性是重要的

因为矩阵乘法没有交换性。

# 证明下列贪婪算法均不能进行链式短阵乘法。在每一步

# 计算最节省的乘法。

假设三个矩阵，分别是1×A1\times A,A×BA\times B,B×1B\times 1, 如果A<BA<B, 则使用贪心算法可以，但反之贪心算法则没法成功。

# 计算最昂贵的乘法。

# 计算两个矩阵MiM_i 和Mi+1M{i+1} 之间的乘法使得在MiM_i 中的列数最小，使用上面法则之一

上面两个问同理。

# 编写一个程序计算矩阵乘法的最佳顺序。注意，程序要显示具体的顺序

回溯算法技巧的典型应用。

计算矩阵乘法的最佳顺序
/*
* Compute optimal ordering of matrix multiplication.
* C contains number of columns for each of the N matrices.
* C[0] is the number of rows in matrix 1.
* Minimum number of multiplications is left in M[1][N].
* Actual ordering is computed via.
* another procedure using LastChange.
* M and LastChange are indexed starting at 1, instead of 0.
* Note: Entries below main diagonals of M and LastChange are
* meaningless and uninitialised.
*/
void OptMatrix(const long C[], int N, long M[][MaxSize], long LastChange[][MaxSize]) {
    long ThisM;
    for (int Left = 1; Left <= N; Left++) {
        M[Left][Left] = 0;
    }
    for (int K = 1; K < N; K++) {
        for (int Left = 1; Left <= N -K ; Left++) {
            // for each position    
            int Right = Left + K;
            M[Left][Right] = Infinity;
            for (int i = Left; i < Right; i++) {
                ThisM = M[Left][i] + M[i + 1][Right]
                        + C[Left - 1] * C[i] * C[Right];
                if (ThisM < M[Left][Right]) {
                    // update min
                    M[Left][Right] = ThisM;
                    LastChange[Left][Right] = i;
                } 
            }
        }
    }
}
# 编写个例程从 10.3.4 节中的算法重新构造那些最短路径。
依旧使用的是 Dijkstra 算法。
# 编写在跳跃表中执行插入、删除以及查找的例程
删除很麻烦，还有删除。
插入
// Insert a new element node
void Skiplist_Insert(Skiplist S, int Data) {
    /* First step: find the insertion position of each layer */
    // last[i]: The predecessor node of the insertion position at level i
    Skiplist_Node last[MAX_LEVEL];
    Skiplist_Node pos = S->Head;
    for (int i = S->Level - 1; i >= 0; i--) {
        while (pos->Next[i] != NULL && pos->Next[i]->Data < Data)
            pos = pos->Next[i];
        last[i] = pos;
    }
    /*Second step: generate new nodes and layers*/
    // int level = RandLevel(); // The number of layers of the new node
    int level = RandInt(1, 16);
    // if number of layers of the new node is larger than 
    // layers of the original node.
    // It is necessary to supplement the high bits of the last array,
    // and the head will point to this node
    if (level > S->Level) {
        for (int i = S->Level; i < level; i++)
            last[i] = S->Head;
        S->Level = level;
    }
    /*Third step: each layer performs insertion*/
    Skiplist_Node Node  = Skiplist_NewNode(Data, level);
    for (int i = 0; i < level; i++) {
        Node->Next[i] = last[i]->Next[i];
        last[i]->Next[i] = Node;
    }
    // Update number of nodes
    S->Num++;
}
查找
// Return whether Data is in the skip list.
// Actually find data in the skip list
static bool Skiplist_IsHas(Skiplist S, int Data) {
    Skiplist_Node pos = S->Head;
    for (int i = S->Level - 1; i >= 0; i--) {
        while (pos->Next[i] != NULL && pos->Next[i]->Data < Data)
            pos = pos->Next[i];
    }
    pos = pos->Next[0];
    return pos != NULL && pos->Data == Data;
}
删除
// Delete one node from the skip list 
bool Skiplist_Delete(Skiplist S, int Data) {
    /* First step: Find the predecessor node of 
    *  the deletion position of each layer.
    */
   Skiplist_Node last[MAX_LEVEL];
   Skiplist_Node pos =S->Head;
   for (int i = S->Level - 1; i >= 0; i--) {
        while (pos->Next[i] != NULL && pos->Next[i]->Data < Data)
            pos = pos->Next[i];
        last[i] = pos; 
   }
   // The node will be deleted
   pos = pos->Next[0];
   if (pos != NULL && pos->Data != Data) return false;
   /*Second step: each layer performs deletion*/
   for (int i = S->Level - 1; i >= 0; i--) {
        if (last[i]->Next[i] == pos)
            last[i]->Next[i]  = pos->Next[i];
   } 
   /*Third step：remove the invalid layers 
   * that may be caused by deleting nodes
   */ 
  Skiplist_Node tmp = S->Head; 
  while (S->Level > 1 && tmp->Next[S->Level - 1] == NULL) 
    S->Level--; 
  S->Num--; 
  Skiplist_FreeNode(pos);
  return true;
}
# 给出跳跃表操作的期望时间为O(log⁡N)O(\log{N}) 的正式证明
大致证明见跃表的推导和数学证明。
# 实现收费公路重建算法
// x[] is a collection of points.
// Dset[] is a collection of distance of point to point.
// N is the number of point.
int turnPike(int X[], int Dset[], int N) {
    // Include the largest and smallest points into the vertices.
    X[1] = 0;
    X[N] = Dset[N * (N - 1) / 2];
    // Set the maximum distance to -1, which means empty.
    Dset[N * (N - 1) / 2] = -1;
    return Place(X, Dset, N, 2, N-1);
}
# 写出三连游戏棋剩下的步骤。
直接看 tic-tac-toe 源码吧，实在太多行了。