ADS

只是随便写写，给自己复习用的。

Exercise and Homework

1.假设有势函数Φ，使得对所有的i都有\(Φ(D_i)>=Φ(D_0)\)，但是 \(Φ(D_0)≠0\) 。证明：存在一个势函数Φ'使得 \(Φ'(D_0)=0\)，\(Φ'(D_i)>=0\) ，对所有i>=1，且用Φ'表示的平摊代价与用Φ表示的平摊代价相同。

解法：令 $ Φ'(D_i)=Φ(D_i)-Φ(D_0) $ 即可。

势能方法：势函数Φ将每个数据结构Di映射为一个实数 \(Φ(D_i)\) ，即与数据结构Di相联系的势。第i个操作的平摊代价 \(c'_i=c_i+Φ(D_i)-Φ(D_{i-1})\)

n个操作总的平摊代价为 \(∑c'_i=∑c_i+Φ(D_n)-Φ(D_0)\)

想要证明一个算法的平摊代价是常数时间复杂度，选取的势能函数要保证每次操作的平摊代价为一个常数。

如果定义一个势函数使得 \(Φ(D_n)>=Φ(D_0)\) ，则总的平摊代价 \(∑c'_i\) 就是总的实际代价 \(∑c_i\) 的一个上界。

通常定义 \(Φ(D_0)\) 为0，证明对所有的i，有 \(Φ(D_i)>=0\) 。

最坏情况时间复杂度可能大于平摊时间复杂度。worst−case bound ≥ amortized bound ≥ average−case bound。

2.AVL树高上下界的推导（同节点数目）。

最小树高：满二叉树，\(n=2^{h+1}−1\)

最大树高：此时左子树的树高为n-1，右子树的树高为n-2，递推关系为\(A_n=A_{n-1}+A_{n-2}+1\)，其中\(A_0=1,A_1=2\)。Depth从0开始（假设空树的高为-1），对应最少节点数分别为1,2,4,7,12,20,33等。

如30个节点的AVL树的树高可以是5。

3.Splaying not only moves the accessed node to the root, but also roughly halves the depth of most nodes on the path.

4.The root of B+ tree is not always has between 2 and M children.

因为如果根同时是叶子的话就没有children了。（文字游戏~）

(1) The root is either a leaf or has between 2 and M children. (2) All nonleaf nodes (except the root) have between \(⌈M/2⌉\) and \(M\) children. (3) All leaves are at the same depth.

5.Term-partitioned index按单词分区，Document-partitioned index按文档分区。

• Data Retrieval Performance Evaluation: 包括响应时间、索引空间
• Information Retrieval Performance Evaluation: 包括结果的相关性（the relevancy of the answer set）

6.Red-Black Tree：

A red-black tree with N internal nodes has height at most \(2ln(N +1)\) .

一个黑高为h的红黑树的最多internal nodes数为 \(2^{h+1}-1\) ，最少为 \(2^h-1\) ，前者红色节点数最多，后者红色节点数最少（0）。Internal nodes是指除了叶子节点以外的节点。

黑高：从某个结点 x （不包含该结点）到达一个叶结点的任意一条简单路径上黑色结点的数量成为该结点的黑高。

In a red-black tree, an internal red node cannot be a node of degree 1.因为红色节点的两个孩子必须是黑色的，如果只有一个孩子，那么高度不平衡。

插入操作：

插入操作

• Case 0：默认插入红色节点，如果父节点是黑色，不需要调整。
• Case 1: 父节点是红色，叔叔节点是红色，将父节点和叔叔节点变为黑色，祖父节点变为红色，递归调整祖父节点。
• Case 2: 父节点是红色，叔叔节点是黑色，当前节点是右孩子，父节点是左孩子，左旋父节点，变为Case 3。
• Case 3: 父节点是红色，叔叔节点是黑色，当前节点是左孩子，父节点是左孩子，把父节点变为黑色，祖父节点变为红色，右旋祖父节点。

删除操作：

删除操作

• 如果删除的是叶子节点，直接删除。
• 如果删除的节点有一个孩子，用孩子节点替代删除节点。
• 如果删除的节点有两个孩子，找到后继节点，用后继节点替代删除节点，删除后继节点。后继节点是右子树的最左节点。

从以上调整过程可以看出，最终都是在叶子节点上进行调整，颜色调整的方法为：

颜色调整

• 兄弟节点是红色，那么父节点和侄节点必为黑色，若当前节点是左孩子，把父节点变为红色，兄弟节点变为黑色，左旋父节点，变为兄弟节点是黑色的情况。此时兄弟节点是黑色，父节点也是黑色，可以继续向下调整。
• 兄弟节点是黑色，兄弟节点的两个孩子都是黑色，父节点是红色，把父节点变为黑色，兄弟节点变为红色，结束。
• 兄弟节点是黑色，兄弟节点的两个孩子都是黑色，父节点是黑色，把兄弟节点变为红色，此时父节点的黑高减少1，继续向上调整。
• 兄弟节点是黑色，当前节点是左孩子，兄弟节点的左孩子是红色，右孩子是黑色，把兄弟节点变为红色，兄弟节点的左孩子变为黑色，右旋兄弟节点，变为兄弟节点的右孩子是红色的情况。此时兄弟节点的右孩子是红色，转换成下一种情况。
• 兄弟节点是黑色，当前节点是左孩子，兄弟节点的右孩子是红色，把父节点的颜色赋给兄弟节点，父节点变为黑色，兄弟节点的右孩子变为黑色，左旋父节点，结束。

这鬼东西哪里记得住（逃

7.The result of inserting keys 1 to \(2^{k−1}\) for any k>4 in order into an initially empty skew heap is always a full binary tree.

Leftist Heaps：The leftist heap property is that for every node X in the heap, the null path length of the left child is at least as large as that of the right child.

\[ Npl(X) = min ( Npl(C) + 1 \ for \ all \ C \ as \ children \ of \ X ) \]

而skew heap在插入的时候，每次都交换左右孩子。（最后的结果是所有原右路径上的节点都变成了合并后的左路径上的节点）

8.主定理：

\[ T(n) = aT(n/b) + f(n) \]

\[ 即n^{log_ba}与f(n)进行比较 \]

对于递归关系

\[ T(n) = 2T(\sqrt{n}) + \log n \]

我们可以通过主定理来求解其渐进上界。

令 $ n = 2^m $ ，则 $ \sqrt{n} = 2^{m/2} $ 。

将递归关系变为关于 $ m $ 的函数：$ T(2^m) = 2T(2^{m/2}) + m $ ，其中 $ m = \log n $ 。

转换 $$ T(2^m) = 2T(2^{m/2}) + m $ 为 $ S(m) = 2S(m/2) + m $ ，其中 $ S(m) = T(2^m) $

则

\[ S(m) = \Theta(m \cdot \log m) \]

所以

\[ T(n) = \Theta(\log n \cdot \log \log n) \]

9.DP问题：

动态规划并不保证多项式时间复杂度。

10.Insert { 1, 2, 5, 3, 8, 4, -1, 10, 128, 34, 15, 63, 18, -24, 186 } into an initially empty binomial queue, the resulting roots are 186, -24, 15 and -1.

一共十五个数，二进制表示为1111，因此在二项队列中有四个树。四棵树的根分别是前八个数中最小的、中间四个数中最小的、后面两个数中最小的和最后一个数。

11.A B+ tree of order 3 with 21 numbers has at least __ nodes of degree 2.

答案是2。（？）

12.哈夫曼树中的节点的度数是0或2。

13.The potential function used for Fibonacci heaps is Φ(H)=t(H)+2m(H).

14.For red-black trees, the total cost of rebalancing for m consecutive insertions in a tree of n nodes is O(n+m).

15.斜堆的每个轻节点的右子树小于以该节点为根的子树大小的一半，所以每次子树规模至少缩减一半，右路径上的轻节点数目为O(logn)的。

16.P和NP：

若L₁ ≤ₚ L₂，表明L₁ 可以在多项式时间内规约到 L₂，前者的难度小于等于后者。

SAT, Vertex Cover, Hamiltonian Cycle, Clique, Knapsack, Bin Packing, and Domination Set problems are all NP-completeness problems.

1. 顶点覆盖问题 (Vertex Cover)

2. 近似比：2

3. 方法：贪心选择边的两个端点（任意选择，而非选择最大度）

4. TSP问题 (带三角不等式)

5. 近似比：1.5

6. 方法：Christofides算法

7. 背包问题 (Knapsack)

8. 近似比：1 + ε

9. 方法：FPTAS (完全多项式时间近似方案)

10. 装箱问题 (Bin Packing)

11. 近似比：1.5

12. 方法：First Fit Decreasing (FFD)算法

13. K-center问题

14. 近似比：2

15. 方法：2r greedy

There are inputs that force any on-line bin-packing algorithm to use at least 5/3 the optimal number of bins.

Let M be the optimal number of bins required to pack a list I of items. Then first fit decreasing never uses more than 11M / 9 + 6/9 bins. There exist sequences such that first fit decreasing uses 11M / 9 + 6/9 bins.

f : {0, 1} → {0,1} such that for all x {0, 1}, x ∈L1 iff* f (x)∈L2.（一定是当且仅当）

17.哈夫曼树可以用于生成optimal prefix code。

哈夫曼树生成的一定是满二叉树（除叶子节点外每个节点都有两个孩子）。

18.连通图是无向图中任意两个顶点之间都能连通的图，强连通图是有向图中任意两个顶点之间都能互相连通的图。

19.找零问题的贪心求解：

1. 美元系统中贪心总是最优的，因为每个面额都能被更大面额整除或接近整除（人民币系统也是）
2. 幂次系统中，每个面额都是下一个的倍数，保证贪心最优
3. 任意面额系统中，如[1,3,4]就是一个反例，证明贪心不一定最优

20.特殊分治推导：

21.pruning: