算法导论第三次习题课 2009-12-22.

Presentation on theme: "算法导论第三次习题课 2009-12-22."— Presentation transcript:

1 算法导论第三次习题课

2 15.2-1 略 15.2-2 15.2-3 略。需要注意： MATRIX-CHAIN-MULTIPLY(A, s, i, j)
if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1, j) return MATRIX-MULTIPLY(x, y) else return Ai 略。需要注意： 1 应先给出猜测解 2 c应为常数

3 15.3-1 枚举复杂度 ，递归复杂度 。 递归的稍微好一点。 没有重叠子问题 略

4 略 15.4-2 PRINT_LCS(c,x,y,i,j) if x[i]=y[j] PRINT_LCS(c,x,y,i-1,j-1) print x[i] else if c[i –1]>=c[i,j-1] PRINT_LCS(c,x,y,i-1,j) else PRINT_LCS(c,x,y,i,j-1)

5 15.4-4

6 15.5-3 这个改变不影响时间复杂度，但是影响系数。 15.5-4 第九行替换为： if i=j root[i,j]<-j e[i,j]<-pi+qi-1+qj else for r<-root[i,j-1] to root[i+1,j] 时间复杂度为

7 16.1-1 动态规划时间复杂度为 ，贪心算法时间复杂度为 。

8 略 16.1-3 用两个链表分别存放空闲教室和繁忙教室，把活动按开始时间递增排序，依次调度教室，就可以获得最少教室数。调度方案是在繁忙教室队列中寻找是否有教室已经空闲，再在空闲教室队列中寻找空闲教室，如果都没有，就再增加一个教室。 说明：本题直接调用书上的算法GREDDY-ACTIVITYSELECTOR( )来求是不对的，如下实例，按GREDDYACTIVITY-SELECTOR( )求得需要3个教室，实际上只要2个教室 i 1 2 3 4 5 6 7 s 8 f 9

9 略 略 16.3-5 用2n-1位表示树的结构，内部结点用1表示，叶子结点用0表示，以树的遍历为序。用nlog(n)位表示字母序列，每个字母的二进制编码长度为log(n)，总共需要nlog(n)位。

10 17.1-1 不能保持，如执行n次MULTIPUSH(s,n) 17.1-3 O(n) 平摊开销为O(1)。

11 17.2-2 每个操作都支付3元费用，若i不是2的幂次，则只用1元，剩下的2元用于支付那些是2的幂次的操作。 17.2-3 当某位被置为1时，用1元支付置位的实际代价，2元作为存款，其中1元将来该位变为0时使用，另外1元RESET此位时使用

12 17.3-2 总代价为O(n)，平摊代价为O(1) 17.3-6 设有两个栈A，B ENQUEUE操作为：push A DEQUEUE操作为： if B is empty 将A中元素导入B中 if B is not empty pop B 平摊代价为O(1)

13 略 30.2-4对FFT算法作如下修改即可：用 代替ω，并且将最后结果的每个元素除以n。

14 30.2-5

15 略 略 22.2-7 先对T 中任意一顶为根做BFS，记录最后遍历的顶点u，再以u 为根做BFS，记录最后遍历的顶点v，d(u,v)为T 的直径。时间复杂度O(V+E)。

16 略 略

17 略 22.4-2 先对图进行拓扑排序，然后从t到s依次计算Pu（以u为起点t为终点的路径数） Pu=ΣPv，v∈Adj(u) Pt=1， Pu=0，出度为0或在t的右边 22.4-3 方法很多，有些方法需要对每个连通片都进行计算。

18 24.1-3 m未知时，则某一轮循环没有执行relax操作时终止即可。
24.1-6 修改Bellman-Food算法，先找到负环上的一个节点，再依次找到负环上的其他节点。

19 最后一个顶点没有出度 24.2-4 先进行拓扑排序，然后从右往左依次计算Pu（以u为起点的路径数） Pu=Σ（Pv+1） , v∈Adj(u) Pu=0 ，u的出度为0 最后对所有Pu累加就是路径总数。

20 略 25.2-4 检查Floyd_Warshall( )输出矩阵主对角线上的元素，如果存在负数，则存在权为负的回路。

21 略 h(v)=0, h(u)=0, =w+h(u)-h(v)=w 25.3-5