算法导论第三次习题课

算法导论第三次习题课16.1-1动态规划时间复杂度为，贪心算法时间复杂度为。16.1-2略16.1-3

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

16.3-1略16.3-2略16.3-5

用2n-1位表示树的结构，内部结点用1表示，叶子结点用0表示，以树的遍历为序。用nlog(n)位表示字母序列，每个字母的二进制编码长度为log(n)，总共需要nlog(n)位。17.1-1不能保持，如执行n次MULTIPUSH(s,n)17.1-3O(n)平摊开销为O(1)。17.2-2

每个操作都支付3元费用，若i不是2的幂次，则只用1元，剩下的2元用于支付那些是2的幂次的操作。17.2-3

当某位被置为1时，用1元支付置位的实际代价，2元作为存款，其中1元将来该位变为0时使用，另外1元RESET此位时使用17.3-2

总代价为O(n)，平摊代价为O(1)17.3-6

设有两个栈A，BENQUEUE操作为：pushADEQUEUE操作为：

ifBisempty

将A中元素导入B中

ifBisnotemptypopB

平摊代价为O(1)30.2-2略30.2-4对FFT算法作如下修改即可：用代替ω，并且将最后结果的每个元素除以n。30.2-522.2-2略22.2-5略22.2-7

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

先对图进行拓扑排序，然后从t到s依次计算Pu（以u为起点t为终点的路径数）

Pu=ΣPv，v∈Adj(u)Pt=1，

Pu=0，出度为0或在t的右边22.4-3方法很多，有些方法需要对每个连通片都进行计算。24.1-3m未知时，则某一轮循环没有执行relax操作时终止即可。24.1-6

修改Bellman-Food算法，先找到负环上的一个节点，再依次找到负环上的其他节点。24.2-2最后一个顶点没有出度24.2-4

先进行拓扑排序，然后从右往左依次计算Pu（以u为起点的路径数）

Pu=Σ（Pv+1）,v∈Adj(u)Pu=0，u的出度为0

最后对所有Pu累加就是路径总数。25.2-1略25.2-425.2-6检查Floyd_Warshall()输出矩阵主对角线上的元素，如果存在负数，则存在权为负的回路。25.3-1略25.3-3h(v)=0,h(u)=0,=w+h(u)-h(v)=w25.3-5第26章26.2-1

流：19，容量：3126.2-2题目要求写Edmonds-Karp算法的处理过程，注意读清