USTC-算法基础课-2013-第二次习题课.ppt

课堂测试 30.1-2 求一个次数界为n的多项式A(x)在某已知点x0的值也可以用一下方法获得：把多项式A(x)除以多项式(x-x0)，得到一个次数界为N-1的商多项式q(x)和余项r，并满足：A(x) = q(x)*(x-x0) + r显然A(x0) = r。试说明如何根据x0和A的系数，在θ(n)的时间计算出余项r以及q(x)中的系数 解：设A(x)和q(x)的系数分别为Ak,Bk. 30.1-7考察两个集合A和B，每个集合包含取值范围在0到10n之间的n个整数，要计算出A与B的笛卡尔和，它的定义如下：C = {x+y:x∈A y∈B} 注意，C中整数的取值范围在0到20n之间。我们希望计算出C中的元素，并且求出C的每个元素可为A与B中元素和的次数。证明：解决这个问题需要θ(nlgn)的时间（提示：用10n次多项式来表示A和B。） 解：用10n次多项式A10n和B10n来表示A和B。Ai=1当且仅当i在集合A中出现，0=i=10n，Bi同Ai。 则多项式C10n=A10n*B10n可用DFT在O(nlgn)时间算出，对应集合C。 30.2-2计算向量（0,1,2,3）的DFT。 解： W= DFT（0,1,2,3）T=W*（0,1,2,3）T=（6,-2-2i，-2,-2+2i）T 30.2-5试把FFT过程推广到n是3的幂的情形，写出其运行时间的递归式并求解该式。 解： 运用分治策略，定义三个次数界为n/3的多项式A[0](x),A[1](x),A[2](x): A[0](x) = a0+a3x+a6x2+…+an-3xn/3-1 A[1](x) = a1+a4x+a7x2+…+an-2xn/3-1 A[2](x) = a2+a3x+a8x2+…+an-1xn/3-1 则有下式 A(x) = A[0](x3) + xA[1](x3) + x2A[2](x3) …… T(n) = 3T(n/2) + θ(n) = θ(nlgn) 30.2-7已知一组值z0,z1,…,zn-1（可能有重复），说明如何求出仅在z0,z1,…,zn-1（可能有重复）处值为0的次数界为n的多项式P(x)的系数。所给出的过程的运行时间应该是O(nlg2n)。(提示：当且仅当P(x)是(x-zj)的倍数时，多项式P(x)在zj处值为0。) 解： 不妨设P(x) = a(x-z0)(x-z1)…(x-zn-1) 有P(x) = a*A*B 其中A = (x-z0)…(x-zn/2-1) ，B = (x-zn/2)…(x-zn-1) 故T(n) = 2*T(n/2) + O(lgn) = O(nlg2n) 30.3-1试说明如何利用过程ITERATIVE-FFT计算出输入向量（0,2,3,-1,4,5,7,9）的DFT 解： 位反序：(0,4,3,7,2,5,-1,9) 第一级FFT结果：(4, -4, 10, -4, 7, -3, 8, -10) 第二级FFT结果：(14，-4-4i,-6,-4+4i,15,-3-10i,-1,-3+10i) 第三级FFT结果： 30.3-2试说明如何把位反转置换放在计算过程的最后而不是开始处，以实现FFT算法。（提示：考虑逆DFT。） 解： 32.1-2 假设模式P中的所有字符都是不同的。试说明如何对一段n个字符的文本T加速过程NAIVE-STRING-MATCH的执行速度，使其运行时间达到O(n)。 解：当比较过程进行到P[j+1]和T[i+1]时，必有P[1...j]=T[i-j+1...i]。 因为模式P中的所有字符均不同，所以T[i-j+1...i]中的字符也均不同，即 for every char c in T[i-j+2...i], c != T[i-j+1] = P[1]。 若T[i+1]!=P[j+1]，下一步比较只需从T[i+1]和P[1]开始比较，而不是从T[i-j+2]和P[1]开始。 代码如下，只需执行O(n)次循环。 第二次习题课 算法基础 17.1-2 证明：在k位计数器的例子中，如果包含一个DECREMENT操作，n个操作可能花费θ(nk)的时间。 计数器初始状态为全0.假设有以下操作序列： DECREMENT INCREMENT DECREMENT INCREMENT ...... 每次操作都会有k次的翻转，一共进行n次操作即可。 17.1-3 对某个数据结构执行n个操作的序列。如果i为2的整数幂，则第i个操作的代价为i，否则为1.请利用聚集分析来确定每次操作的平摊代价。 从而得到每个操作的平摊代价为O(1) 17.3-2 用势能方法重做练习17.1-3 设i = 2j +