算法基础习题课2 助教：刘倩玉.

Presentation on theme: "算法基础习题课2 助教：刘倩玉."— Presentation transcript:

1 算法基础习题课2 助教：刘倩玉

2 主讲部分 Page210 15.1-1（DP） Page226 15.4-1, 15.4-2, 15.4-5;（LCS）
Page ; （Huffman） Page , , ; （BST） Page ; （RB-Tree） Page , ; （RB-Tree） Page ; （disjoint-set） Page , , , ; （KMP） 2019/10/29

3 Page210 15.1-1 。证明 数学归纳法 2019/10/29 T(0)成立 假设T(k)成立，推导T(k+1)成立
𝑻 𝒏 =𝟏+ 𝒋=𝟎 𝒏−𝟏 𝑻(𝒋) 𝑻 𝟎 =𝟏 𝑻 𝒏 =𝟐 𝒏 数学归纳法 T(0)成立 假设T(k)成立，推导T(k+1)成立 2019/10/29

4 Page 。求<1, 0, 0, 1, 0, 1, 0, 1>和<0, 1, 0, 1, 1, 0, 1, 1, 0>的一个LCS LCS：<1, 0, 0, 1, 1, 0> <0, 1, 0, 1, 0, 1> 2019/10/29

5 Page 。设计伪代码，利用完整的表c及原始序列X = <x1, x2, …, xm>和Y=<y1,y2,…,yn>重构LCS，要求运行时间为O(m+n),不能使用表b。 解： PRINT-LCS(c,X,Y,i,j)       if i == 0 or j == 0           return       if X[i] == Y[j]           PRINT-LCS(c,X,Y,i-1,j-1)           print X[i]       else if c[i-1,j] >= c[i,j-1]           PRINT-LCS(c,X,Y,i-1,j)       else           PRINT-LCS(c,X,Y,i,j-1)   2019/10/29

6 Page 。设计伪代码，利用完整的表c及原始序列X = <x1, x2, …, xm>和Y=<y1,y2,…,yn>重构LCS，要求运行时间为O(m+n),不能使用表b。 解： PRINT-LCS(c,X,i,j)       if i == 0 or j == 0           return       if c[i-1,j-1] == c[i,j] - 1           PRINT-LCS(c,X,i-1,j-1)           print X[i]       else if c[i-1,j] == c[i,j]           PRINT-LCS(c,X,i-1,j)       else           PRINT-LCS(c,X,i,j-1)   举例：X = Y = c[8, 3] = 3 即 1 0 0 c[9, 4] = 4 即 c[9, 4] – 1 = c[9-1, 4-1] = c[8, 3] = 3 但X[9]的‘0’并不是LCS的构成元素 2019/10/29

7 Page226 15.4-5 。设计一个O( 𝑛 2 )时间的算法，求一个n个数的序列的最长单调递增子序列（LIS）。 2019/10/29
思路1：类比LCS，使用数组A保存原始序列，数组B记录LIS长度，辅助数组C记录前驱下标 思路2：将LIS问题转换为LCS问题 LIS(A)       n = A.length       Initialize new array B[n] and C[n] //B[i]:以A[i]结尾的LIS长度     for i = 1 to n   //C[i]:以A[i]结尾的LIS中A[i]的上一跳的下标         B[i] = 1           C[i] = -1       for i = 2 to n           for j = i-1 downto 1               if A[j] < A[i] and B[j] >= B[i]                   B[i] = B[j] + 1                   C[i] = j       return B and C                2019/10/29

8 Page226 15.4-5 。设计一个O( 𝑛 2 )时间的算法，求一个n个数的序列的最长单调递增子序列（LIS）。 2019/10/29
思路1：类比LCS，使用数组A保存原始序列，数组B记录LIS长度，辅助数组C记录前驱下标 思路2：将LIS问题转换为LCS问题 方法2： 原序列记为S1，S1单调递增排序后的序列记为S2，则求解S1的最长单调递增子序列问题可以转换成求解S1和S2的最长公共子序列问题。 其中，公共子序列保证了最后的序列 1. 是S1的子序列 2.是S2的子序列（单调递增） 2019/10/29

9 Page249 16.3-1 。解释：在引理16.2的证明中，为什么若x.freq = b.freq， 2019/10/29
则有a.freq = b.freq = x.freq = y.freq。 引理16.2提供的条件：a.freq <= b.freq and x.freq <= y.freq x.freq <= a.freq and y.freq <= b.freq 推导出： x.freq <= a.freq <= b.freq x.freq <= y.freq <= b.freq 当 x.freq = b.freq， a.freq = b.freq = x.freq = y.freq 2019/10/29

10 Page 。二叉搜索树性质与最小堆性质区别？是否可以使用最小堆性质在O(n)时间内按序输出有n个结点树的关键字？ 性质区别：见定义 按序输出相当于堆排序，不可以。 2019/10/29

11 Page162 12.1-3 2019/10/29 。设计执行二叉搜索树中序遍历的非递归算法。 INORDER-TREE-WALK(T)
Initialize an empty stack s.   temp = T   while(!s.empty() or temp != NULL){       while(temp != NULL){           s.push(temp)           temp = temp.left       }       temp = s.pop()      print temp.val      temp = temp.right   }   2019/10/29

12 Page177 13.2-2 2019/10/29 。证明：在任何一棵有n个结点的二叉搜索树中，恰有n-1种可能的旋转。
解：直观解释or 递归证明都可以。 直观解释 每个结点均可以和parent结点进行一次旋转，共有n-1个结点存在parent结点，共n-1种可能的旋转 递归证明 n=1 ,一个root结点无法旋转（0） 假设k个node有k-1种旋转，现插入一个新node，若为其parent结点的left子节点，则增加一种右旋，若为right子节点，增加一种左旋，即k+1个结点有k种旋转 2019/10/29

13 Page182 13.3-1 2019/10/29 。在RB-INSERT中，为什么将新插入的点着红色而非黑色？ 解： RB-Tree性质：
结点red or black 根结点为black NIL叶节点均为black 红结点的子节点均为黑 每个节点到所有后代叶节点的简单路径上，均包含相同数目的黑结点 新插入结点着黑色，不违反性质4，必违反性质5 新插入结点着红色，不违反性质5，可能违反性质4 2019/10/29

14 Page330 21.3-2 2019/10/29 。写出使用路径压缩的FIND-SET过程的非递归版本。 解： 递归查找root
/* 递归版本 */ FIND-SET(x)   if x != x.p      x.p = FIND-SET(x.p)   return x.p  递归查找root 将路径中所有节点直接指向root，即node.p = root return root 思路1： 循环查找并记录root结点；循环更新每个结点的parent指向。（更新x.p前需先记录x.p） 思路2： 使用stack模拟递归过程 2019/10/29

15 Page330 21.3-2 2019/10/29 方法1：循环更新 方法2：使用stack FIND-SET(x) FIND-SET(x)
root = x   while(root != root.p)       root = root.p   while(x != root)       temp = x.p       x.p = root       x = temp   return root   方法2：使用stack FIND-SET(x)   Initialize an empty stack s.   while(x != x.p)       s.push(x)       x = x.p   while(!s.empty())       y = s.pop()       y.p = x   return x    常见错误： FIND-SET(x)   ...   while(x != root)       x.p = root       x = x.p   return root   2019/10/29

16 Page593 32.4-1 2019/10/29 。计算对应于模式ababbabbabbababbabb的前缀函数𝜋。 i 1 2 3 4
6 7 8 9 10 11 12 13 14 15 16 17 18 19 P[i] a b 𝝅 𝒊 2019/10/29

17 Page593 32.4-2 2019/10/29 。给出关于q的函数 𝝅 ∗ [𝒒]的规模的严格上界，并加以举例说明。 解：理解题意。
本题求解严格上界的对象是 𝝅 ∗ [𝒒]的规模，不是 𝝅 ∗ [𝒒]内元素值的上界。 𝝅 ∗ [𝒒] = {𝝅 𝒒 , 𝝅 (𝟏) [𝒒] , 𝝅 (𝟐) [𝒒] ,…, 𝝅 (𝒕) [𝒒] }，本身是一个集合，集合中的元素由前缀函数𝜋迭代生成。 当字符串中各字符均相同时,eg: aaa π ∗ [3] = {2, 1, 0}， 𝜋 ∗ [𝑞]的规模上界为q, 𝜋 ∗ [𝑞]内元素值的上界为q-1。 2019/10/29

18 Page593 32.4-7 2019/10/29 。写出一个线性时间的算法，以确定文本T是否是另一个字符串 𝑻 · 的循环旋转。
eg: ABC BCA CAB互为循环旋转。 解：对于任意文本串T： 𝐶 1 𝐶 2 𝐶 3 … 𝐶 𝑛−1 𝐶 𝑛 ，其循环旋转依次有 𝐶 2 𝐶 3 … 𝐶 𝑛−1 𝐶 𝑛 𝐶 1 𝐶 3 … 𝐶 𝑛−1 𝐶 𝑛 𝐶 1 𝐶 2 . 𝐶 𝑛 𝐶 1 𝐶 2 𝐶 3 … 𝐶 𝑛−1 𝐶 1 𝐶 2 𝐶 3 … 𝐶 𝑛−1 𝐶 𝑛 任意文本串T的所有循环旋转一定存在于TT字符串中。 将T1与T2是否互为循环问题转换为使用KMP算法在T1T1文本串中寻找模式串T2。 2019/10/29

19 算法基础第二次习题课 助教：张帆

20 主讲部分 Page124 9.3-5; Page231 15.5-2 Page244 16.2-3 Page535 30.2-2
2019/10/29

21 Page 解： 使用黑盒程序找到中位数，根据该中位数对数组进行分区。 如果i小于原始数组长度的一半，则在前半部分递归，如果i是数组长度的一半，则返回来自中位数查找黑框的元素。 最后，如果i超过数组长度的一半，则减去数组长度的一半，然后递归到数组的后半部分。 SELECT'(A, p, r, i) if p == r return A[p] x = MEDIAN(A, p, r) q = PARTITION(x) k = q - p + 1 if i == k return A[q] else if i < k return SELECT'(A, p, q - 1, i) else return SELECT'(A, q + 1, r, i - k) 2019/10/29

22 Page 解： e w i, j 1 2 3 4 5 6 7 0.06 0.28 0.62 1.03 1.34 1.83 2.44 3.12 0.30 0.68 0.93 1.41 1.96 2.65 0.32 0.57 1.04 1.48 2.13 0.24 1.01 1.55 0.05 0.72 1.20 0.78 0.34 8 i, j 1 2 3 4 5 6 7 0.06 0.16 0.28 0.42 0.49 0.64 0.81 1.00 0.18 0.32 0.39 0.54 0.71 0.90 0.20 0.27 0.59 0.78 0.13 0.45 0.05 0.37 0.56 0.22 0.41 0.24 8 2019/10/29

23 Page 解： 经过计算，构建表后，我们发现最优二叉搜索树的成本是3.12。 该树采用以下结构： 2019/10/29

24 Page 解： 将商品按重量有小到大排序，即按价值由大到小的顺序排列，按照排好的顺序依次将商品装入包中，得到的即为最优解。 正确性证明： 排序好后商品的重量为: 𝑤 1 ≤ 𝑤 2 ≤∙∙∙≤ 𝑤 𝑛 价值排序为： 𝑝 1 ≥ 𝑝 2 ≥∙∙∙≥ 𝑝 𝑛 假最后装入包中的商品为前k个，价值为 𝑝 1 + 𝑝 2 +∙∙∙+ 𝑝 𝑘 如果此算法解不是最优解，则必存在一个𝑖>𝑘，将 𝑤 𝑖 替换 𝑤 1 , 𝑤 2 ,∙∙∙, 𝑤 𝑘 中的某一个后，得到的解更优，假设替换的是某个 𝑤 𝑗 ，替换后的结果为： 𝑝 1 +∙∙∙ 𝑝 𝑖 +∙∙∙+ 𝑝 𝑘 又因为： 𝑖>𝑘>𝑗，所以 𝑝 𝑖 ≤ 𝑝 𝑗 则 𝑝 1 +∙∙∙ 𝑝 𝑖 +∙∙∙+ 𝑝 𝑘 ≤ 𝑝 1 +∙∙∙ 𝑝 𝑗 +∙∙∙+ 𝑝 𝑘 得出矛盾，则此算法解为最优解。 2019/10/29

25 Page535 30.2-2 解： 2019/10/29 计算向量(0,1,2,3)的𝐷𝐹𝑇：
则向量(0,1,2,3)的𝐷𝐹𝑇为：𝑦=(6,−2−2𝑖,−2,−2+2𝑖) 2019/10/29

26 Page187 13.4-2 解： 2019/10/29 假设在RB-DELETE中x和x.p均为红色。
这只能在第9行的else-case中发生。由于我们要从红黑树中进行删除，y.p的另一个孩子在第14行的RB-TRANSPLANT调用中成为x的兄弟，必须是黑色的，所以 x是x.p的唯一红色的孩子节点。 RB-DELETE-FIXUP(T，x)的while循环条件立即被违反，因此我们只需设置x.color = black，即可恢复属性4。 2019/10/29

27 Page 解： 从红黑树中连续删除关键字8、12、19、31、38、41节点。 41 2019/10/29

28 Page 解： 斐波那契堆调用FIB-HEAP-EXTRACT-MIN后得到的斐波那契堆 2019/10/29

29 Page 解： 如何成为被标记的根： 堆中的根被标记，当x作为某个节点的孩子，且它的一个孩子被移除了，在之后的操作被移至root-list。 对分析有无影响： 无影响。 这是因为唯一一次检查标记是在级联切割的第3行。 但是，这仅在父节点为非NIL的节点上运行。 由于每个根都有NIL作为父节点，因此级联切割的第3行永远不会在此标记的根上运行。 2019/10/29

30 Page 解： 状态转移为： T的状态序列是0,1,2,2,3,4,5,1,2,3,4,2,3,4,5,1,2,3，共有两次串匹配成功，一次在s = 1，一次在s = 9。 2019/10/29

31 主讲部分-思考题 Page53 4.4-7, 4.4-8; Page55 4.5-4; Page112 8.3-4;
2019/10/29

32 Page 解： 递归式为： 𝑇(𝑛)=4𝑇( 𝑛 2 )+𝑐𝑛 可得递归树如下： 树的高度为：𝑙𝑔𝑛 整棵树的代价之和为： 𝑇 𝑛 =𝑐 𝑖=0 𝑙𝑔𝑛 𝑛 2 𝑖 4 𝑖 =𝑐 𝑖=0 𝑙𝑔𝑛 𝑛2 𝑖 =𝑂( 𝑛 2 ) 下面用迭代法进行验证，先证明上界成立，即证𝑇 𝑛 =𝑂( 𝑛 2 )，假设： 𝑇 𝑛 ≤𝑐 𝑛 2 +2𝑐𝑛 𝑇 𝑛 =4𝑇 𝑛 2 +𝑐𝑛 ≤4𝑐 𝑛 𝑐 𝑛 2 +𝑐𝑛 ≤4 𝑐 𝑛 𝑐 𝑛 2 +𝑐𝑛 = 𝑐𝑛 2 +2𝑐𝑛 同理可证下界成立，即证𝑇 𝑛 =Ω 𝑛 2 则由上可得： 𝑇 𝑛 =Ω( 𝑛 2 ) 2019/10/29

33 Page53 4.4-8 解： 2019/10/29 忽略上整符号 递归式为： = 𝑇 𝑛 =𝑇 𝑛−𝑎 +𝑇 𝑎 +𝑐𝑛
可得递归树如下： 树的高度为： 𝑛 𝑎 −1 整棵树的代价之和为： 忽略上整符号 = = Θ( 𝑛 2 ) 下面用迭代法进行验证，先证明上界成立，假设： 𝑇 𝑛 ≤𝑑 𝑛 2 即：𝑇 𝑛 =𝑇 𝑛−𝑎 +𝑇 𝑎 +𝑐𝑛 ≤𝑑 𝑛 2 −2𝑎𝑛+ 𝑎 2 +𝑑 𝑎 2 +𝑐𝑛 =𝑑 𝑛 2 −2𝑎𝑑𝑛+ 2𝑑𝑎 2 +𝑐𝑛 =𝑑 𝑛 2 −(2𝑎𝑑𝑛− 2𝑑𝑎 2 −𝑐𝑛) 当2𝑎𝑑𝑛− 2𝑑𝑎 2 −𝑐𝑛 ≥0时，挑选 𝑑= 𝑐+1 2𝑎 此时𝑇 𝑛 ≤𝑑 𝑛 2 −(𝑛−𝑐𝑎−𝑎) 当n足够大时，𝑇 𝑛 ≤𝑑 𝑛 2 ∴𝑇 𝑛 =𝑂 𝑛 2 同理，可证𝑇 𝑛 =Ω( 𝑛 2 ) 则𝑇 𝑛 =Θ( 𝑛 2 ) 2019/10/29

34 Page55 4.5-4 解： 2019/10/29 𝑓 𝑛 =𝑛 2 lg𝑛≠Ο( 𝑛 2−𝜀 ) ≠Ω( 𝑛 2+𝜀 )
由题意，𝑎=4, 𝑏=2 主定理的三种情况均不满足，则不能使用主定理。 由 ，在递归树中，树高为𝑙𝑔𝑛。则可得树的总复杂度为： 下面用迭代法进行验证，证明上界成立： 则原式的复杂度为 𝑓 𝑛 =𝑛 2 lg𝑛≠Ο( 𝑛 2−𝜀 ) ≠Ω( 𝑛 2+𝜀 ) 2019/10/29

35 Page112 8.3-4 解： 2019/10/29 将这些数字看成𝑛进制，使用𝑟𝑎𝑑𝑖𝑥−𝑠𝑜𝑟𝑡.
运行时间复杂度为：𝑂(6𝑛) = 𝑂(𝑛)  因为基数排序算法的时间复杂度为𝑂(𝑑 ∗ (𝑛 + 𝑘))，这里𝑑是数字的位数，总共有𝑛个，每个数字有𝑘个可能的取值。在这里，把 𝑛 3 个数看成是𝑛位数，每位数字的取值有𝑛个可能。 总的运行时间为：𝑂(3 ∗ (𝑛 + 𝑛)) = 𝑂(6𝑛) = 𝑂(𝑛) 2019/10/29

36 Page231 15-2 解： 2019/10/29 维护一个二维数组𝑑𝑝，其中𝑑𝑝[𝑖][𝑗]表示字符串区间[𝑖, 𝑗]是否为回文串。
当𝑖=𝑗时，只有一个字符，肯定是回文串. 如果𝑗=𝑖+1，说明是相邻字符，此时需要判断𝑠[𝑖]是否等于𝑠[𝑗]. 如果𝑖和𝑗不相邻，即j−𝑖 >= 2时，除了判断𝑠[𝑖]和𝑠[𝑗]相等之外，𝑑𝑝[𝑖+1][𝑗−1]若为真，就是回文串. 通过以上分析，可以写出递推式如下 string longestPalindrome(string s) { if (s.empty()) return " "; int dp[s.size()][s.size()] = {0}, left = 0, right = 0, len = 0; for (int j = 0; j < s.size(); ++j) { for (int i = 0; i < j; ++i) { dp[i][j] = (s[i] == s[j] && (j - i > 2 || dp[i + 1][j - 1])); if (dp[i][j] && len < j - i + 1) { len = j - i + 1; left = i; right = j; } dp[j][j] = 1; return s.substr(left, right - left + 1); 2019/10/29

37 Page231 15-5 解： 2019/10/29 𝑥[1..𝑚] 𝑥[𝑖] 𝑦[1..𝑛] 𝑦[𝑗]
这道题让求从一个字符串转变到另一个字符串需要的变换步骤，共有六种变换方式，复制、替换、删除、插入、旋转、终止。 这道题我们需要维护一个二维的数组𝑐，其中𝑐[𝑖][𝑗]表示从𝑥[1..𝑚]的前𝑖个字符转换到𝑦[1..𝑛]的前j个字符所需要的步骤。 通过分析，可以写出递推式如下 𝑥[1..𝑚] 𝑥[𝑖] 𝑦[1..𝑛] 𝑦[𝑗] 2019/10/29

38 Page 解： 2019/10/29

39 算法基础第二次习题课 曾磊

40 主讲部分 Page210 15.1-2; Page222 15.3-1 15.3-2; Page261 17.1-2;
2019/10/29

41 主讲部分 Page177 13.2-1; Page201 14.3-2 14.3-3; Page583 32.2-1 32.2-3;
2019/10/29

42 Page210 15.1-2 2019/10/29 证明： 长度i 1 2 3 4 价格pi 5 8 9 密度pi/i 2.5 2.67
2.25 按照贪心策略的切割方案是4=3+1, 收益值为9。 但是实际的最优切割方案是4=2+2，收益值为10。 所以，“贪心”策略不能保证总是得到最优切割方案。 2019/10/29

43 Page 第二种方法更高效。书上212页已经给出了该穷举算法的时间复杂度为Ω( 4 𝑛 / 𝑛 3/2 )，而第二种方法的时间复杂度为O(n 3 𝑛−1 )。 证明：第一种方法的时间复杂度已经给出，只需要证明第二种时间复杂度。用代入法证明第二种方法的上界为O(n 3 𝑛−1 ) ： T 𝑛 <= 𝑐, 𝑛=1 𝑐+ 𝑘=1 𝑛−1 (𝑇 𝑘 +𝑇 𝑛−𝑘 +𝑐) , 𝑛≥2 n=1时显然成立 由于 𝑘=1 𝑛−1 𝑇 𝑘 +𝑇 𝑛−𝑘 = 2 𝑘=1 𝑛−1 T(𝑘) 故n>=2时： T(n)<=2 𝑘=1 𝑛−1 T(𝑘) +cn 2019/10/29

44 Page T(n)<=2 𝑘=1 𝑛−1 𝑐∗𝑘∗ 3 𝑘−1 +cn <=c*(2 𝑘=1 𝑛−1 𝑘∗ 3 𝑘−1 +𝑛 ) <=c(2( 𝑛∗ 3 𝑛−1 3−1 + 1− 3 𝑛 (3−1) 2 )+n) (因为：f(x) = 𝑖=1 𝑛−1 𝑥 𝑖 = 𝑥 𝑛 −1 𝑥−1 −1 , 𝑖=1 𝑛−1 𝑖∗𝑥 𝑖−1 = 𝑓 ′ (𝑥)= 𝑛∗ 𝑥 𝑛−1 𝑥−1 + 1− 𝑥 𝑛 (𝑥−1) 2 ) =cn 3 𝑛−1 +c( 1−3 𝑛−1 2 +n) (c( 1−3 𝑛−1 2 +n) <=0,当c>0,n>=1时成立) <=cn 3 𝑛−1 2019/10/29

45 Page 那么便证明了第二种方法的时间复杂度为O(n 3 𝑛−1 ) . 比较 4 n / 𝑛 3/2 𝑛∗ 3 𝑛−1 = 3* (4/3) 𝑛 𝑛 5/2 ,上面是指数时间，下面是多项式时间，而且第一种方法求的是下界，第二种是上界，是故第二种方法更高效。 2019/10/29

46 Page222 15.3-2 画出递归树调用树 由图可知，归并排序虽然把程序划分为子问题，但是子问题不重叠，备忘技术起不了效果。
2019/10/29

47 Page 证明：可能。当k位二进制数是 00…0 𝑘 时，接下来进行Decrement 1操作，再接着是Increment 1操作，如此交替进行n次，那么其运行时间就可以达到Θ(𝑛𝑘)。 2019/10/29

48 Page 证明： 为每个操作赋予如下摊还代价： PUSH： 2 POP：2 COPY：0 PUSH和POP操作中都有一个用于支付自身操作的实际代价，剩余一个用于存为信用，用于支付复制操作的代价。 由于操作的代价都是固定的常数，所以n个栈操作的代价上限为O(n)。 2019/10/29

49 Page 解：查找过程中是查找一次就往下走一层，也就是每次查找的节点都在不同层上。 1、序列c不是，因为节点240是节点911的左子树上节点，往下查找的节点值必定都小于911，但是接下来需查找的节点中912却大于911。 2、序列e不是，因为节点621是节点347的右子树上的节点，往下查找的节点值都应大于347，但是却出现了节点299。 2019/10/29

50 Page 证明：插入和查找的算法结构基本一样，区别在于查找需找到最终关键字后结束，而插入则只需要查找到最终关键字的父节点位置即停止查找。所以，查找关键字所检查过的节点数目比插入这个关键字所检查的节点数目加1。 2019/10/29

51 Page 红黑树的黑高为2： 2019/10/29

52 Page 红黑树的黑高为3： 2019/10/29

53 Page 红黑树的黑高为4： 2019/10/29

54 Page 第一步：画出插入节点36后的图 2019/10/29

55 Page176 13.1-2 第二步：插入节点被标记为黑色或红色都不是一棵红黑树
如果插入的是黑色节点，那么将违反性质5（对每个结点，从该结点到其他所有后代叶结点的简单路径上，均包含相同数目的黑色结点），节点35的左子树路径上的黑高度比右子树少1。 如果插入的是红色节点，则直接违反了性质4（如果一个节点是红色的，则它的两个叶子节点都是黑色的）。 2019/10/29

56 Page 解：写出RIGHT-ROTATE的伪代码： RIGHT-ROTATE(T,x) x.p.left = y y = x.left else x.left = y.right x.p.right = y if y.right != T.nil y.right =x y.right.p = x x.p =y y.p = x.p if x.p == T.nil T.root = y elseif x == x.p.left 2019/10/29

57 Page 解：INTERVAL_SEARCH_NEW(T,i) x = T.root while x != T.nil and i does not overlap x.int if x.left != T.nil an d x.left.max > i.low x = x.left else x = x.right return x 2019/10/29

58 Page 解：INTERVAL_SEARCH_MIN(T,i) x = T.root while x != T.nil and i does not overlap x.int if x.left != T.nil an d x.left.max >= i.low x = x.left else x = x.right while x.left != T.nil and i overlap x.left return x 2019/10/29

59 Page 解：共3个伪命中点。 3 1 4 5 9 2 6 8 7 9 3 8 4 10 2 1 5 2019/10/29

60 Page 解： 直接在582页的RABIN_KARP-MATCHER算法的第3到第4行代码中加入一个for循环：for j = 1 to k, 也就是针对每一个模式独立执行该算法，同时，接下来的代码中需要修改的地方： 第7行：p= (dp+P[j][i]) mod q 第11行：if P[j][1..m] == T[s+1..s+m] 最后需要注意代码的缩进。 2019/10/29

61 算法基础第二次习题课 张宇翔

62 主讲部分 Page ， Page ， Page ， Page ， Page ， Page ， Page ， Page ， Page 2019/10/29

63 Page123 9.2-3 RANDOMIZED-SELECT(A, p, r, i) 本题即用循环将递归具体展开，算法如下：
while p < r do //p != r则不断用i修正p和r的位置 q = RANDOMIZED -PARTITION(A, p, r) k = q - p + 1 if i <= k r = q else p = q + 1 i = i – k return A[p] 2019/10/29

64 Page215 15.2-1 2019/10/29 照m[i,j]的递推公式，从m[1,1]演绎到m[1,6]即可
l=0: m[1,1] = m[2,2] = …… = m[6,6] = 0 l=1: m[1,2] = m[1,1] + m[1,2] + p0p1p2 = 150 …… m[5,6] =1500 . 每步注意记录最佳分割点位置s阵，最终需要得到如下的m矩阵和s矩阵： 2019/10/29

65 Page 最小乘法次数为2010，最优链乘次序为(A1A2)((A3A4)(A5A6)) 2019/10/29

66 Page 于是命题得证 2019/10/29

67 Page215 15.2-5 2019/10/29 l = 2 to n i = 1 to n-l+1 k = I to j-1
所以总查表次数等于 2019/10/29

68 Page215 15.2-2 if i == j then Return Ai else
Return MATRIX-CHAIN-MULTIPLY(A,s,i,s[i,j]) · MATRIX-CHAIN MULTIPLY(A,s,s[i,j]+1,j) 本题相当于要求大家会查s表，将其具体对应到最优解，算法如下： 2019/10/29

69 Page264 17.3-1 2019/10/29 我们只需将 的基准点拉回0即可，从而容易想到定义 从而我们有 且 0 此时新摊还代价为：
我们只需将 的基准点拉回0即可，从而容易想到定义 从而我们有 且 此时新摊还代价为： 和原势函数摊还代价相同。(类比一元函数沿y轴平移不影响任何两点函数值的差值。) 2019/10/29

70 Page 方案：在二维各自补0，到最接近的2的次幂大小 时间：不要说什么量级相同之类的，用数字说明。 2019/10/29

71 Page 按公式来，不多说： 2019/10/29

72 Page 2019/10/29

73 Page196 14.1-1 算法即不断考察x.left+1和rank的关系决定下一步方向，具体步骤为： 2019/10/29
OS-SELECT(T:root， 10) OS-SELECT(T:root:left， 10) OS-SELECT(T:root:left:right， 2) OS-SELECT(T:root:left:right:left， 2) OS-SELECT(T:root:left:right:left:right， 1) 返回关键字为20。 2019/10/29

74 Page 用r记录当前节点序，最外层用循环控制目标序i与r接触则停止： 2019/10/29

75 Page 显然针对每个节点的左右旋操作的操作后黑高度，都可以由其自身信息和其左右子节点信息所维护，故由定理14.1知我们可以在不影响其渐进性能的情况向对黑高度域进行维护。 对深度的维护则不同，首先深度是一个从根到叶子节点传递的信息，改变一个节点的深度会影响到其子孙节点深度，从而可能会产生Θ(n)的修改代价。删除根节点是比较明显的例子。 注意到两者差别是属性的传递方向，由于左右旋操作对节点左右子树结构保护比较完整，所以由下至上传递的属性比较容易在Θ(高度)内完成。 2019/10/29

76 Page328 21.2-2 所有Union执行完以后，最终结果是所有元素都属于同一个集合：
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} 自然FIND-SET(x2)与FIND-SET(x9)都返回代表元素x1 2019/10/29

77 Page328 21.2-3 定理21.1的证明中说明了，每个元素的指针修改必然导致该元素存在
于一个至少外之前集合2倍大小的新集合里。所以n次UNION操作的总代 为O(n·lgn)即每次union的摊还代价为O(lgn)。而MAKE-SET和FIND-SET操作 修改变量为常数次，所以摊还代价为O(1)。 2019/10/29

78 Page579 32.1-1 朴素匹配算法的终止是，所有位置都能匹配成功或者找不到匹配为止。
所以begin = 1, 5, 11三处的匹配都要给出。 2019/10/29

79 Page579 32.1-2 由于P中任意两字符不同，所以之前部分匹配的前缀在紧接着下一个
字符的匹配失败之后都会变为“坏前缀”，于是我们可以在Ps(P的第s 个字符)匹配失败时直接向后移动s-1个字符。 O(n)的时间是T1中每个字符最多失败两次导致的。 T1 这一段不可能在T1内其他地方再匹配，P1是相对于T1的“坏前缀” P1 Ps 2019/10/29