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

1、第二次习题课算法基础17.1-2 证明：在k位计数器的例子中，如果包含一个DECREMENT操作，n个操作可能花费(nk)的时间。计数器初始状态为全0.假设有以下操作序列：DECREMENTINCREMENTDECREMENTINCREMENT.每次操作都会有k次的翻转，一共进行n次操作即可。 17.1-3 对某个数据结构执行n个操作的序列。如果i为2的整数幂，则第i个操作的代价为i，否则为1.请利用聚集分析来确定每次操作的平摊代价。从而得到每个操作的平摊代价为O(1)17.3-2 用势能方法重做练习17.1-3设i = 2j + k(j0,k0且j取值尽可能大)，势能函数 = 2k。如果k=

2、0，则：否则17.2-1 对一个大小始终不超过k的栈上执行一系列的栈操作。在每k个操作之后，复制整个栈的内容以作备份。证明：在对各种栈操作赋予合适的平摊代价之后，n个栈操作的代价为O(n)。对PUSH操作征收3元即可。每个元素入栈时消耗1元，每个在栈里的元素都有2元存款，足够支付复制操作（出栈一次+进栈一次，各消耗1元）或者出栈操作（消耗1元）注：复制操作和出栈操作不会连续发生，即一个元素出栈之后就不会再被复制；复制之后就不会再被出栈（因为已经被留作备份）每个操作的平摊代价为1，故n次操作的代价为O(n)设数组为A，新增一个域：maxA。对每次INCREMENT操作征收4元，RESET操作征收

3、1元即可。具体来说，数组里的每个1都会有3元的存款（由0变为1消耗1元）。这3元存款里预留出1元作为以后该位翻转为零时用；再留出1元作为维护max1的费用（每个1都会有一次机会作为maxA）；再留出1元作为RESET时使用（此时maxA被置为-1，只需要1元的代价）。这样就可以满足所有的操作需求。因此每个操作的平摊代价为O(1)，从而包含n个操作的序列需要时间为O(n)17.2-3 假设我希望们不仅能使一个计数器增值，也能使之复位至零。请说明如何将一个计数器实现为一个数组，使得对一个初始为零的计数器，任一个包含n个INCREMENT和RESET操作的序列的时间为O(n)。17.3-6 说明如何

4、使用两个普通的栈来实现一个队列，使得每个ENQUEUE和DEQUEUE操作的平摊代价都为O(1)。设有两个栈S1，S2ENQUEUE：往S1里pushDEQUEUE：如果S2不为空，则直接pop S2；否则popall S1，接着全部push S2，再pop S2。平摊分析：每次ENQUEUE收费4元，1元用于PUSH入S1，剩下3元存款：在最坏的情况下，其中2元用于从S1转移到S2，1元用于POP。平摊代价为O(1)22.2-4 证明在广度优先搜索算法中，赋给顶点u的值du与顶点在邻接表中的次序无关。利用图22-3作为例子，说明由BFS计算出来的广度优先树与邻接表中的顺序是有关的。第一问：B

5、FS的伪代码里没有任何关于邻接顶点访问次序的信息，因而是次序无关的。第二问：当BFS算法运行到w节点的时候，如果程序先访问t节点，则t就是x的前驱；反之如果先访问到x节点，则x就是t的前驱。22.2-6 题目略过，见书中329页（第二版）第一步：做尽可能多的BFS（为了访问到每个节点）= O(n+r)第二步：把所有d值为偶数的节点标记为好选手，把d值为奇数的节点标记为差选手 = O(n)第三步：检查所有的边，如果都满足边上的两个顶点分别是好选手、差选手，则可以做出这样的指定；否则就是不可以 = O(r)22.3-5 证明：在一个无向图中，如果是根据在深度优先搜索中，(u,v)和(v,u)哪一个

6、先被遇到作为标准来将(u,v)归类为树边或者反向边的话，就等价于根据边分类方案中的各类型的优先级来对它进行分类。如果访问到边一端是白的，另一端是灰的，一定是访问灰色到白色方向的边，这是一条Tree edge。 如果访问到边两端都是灰的，一定是Back edge。 不可能有其他情况。这等价于根据边分类方案中的各类型的优先级来对它进行分类。22.3-8 对于“在一个有向图G中，如果有一条从u到v的路径，则任何深度优先搜索都必定能否得到dvfu”这一推测，给出它的一个反例。22.4-3 给出一个算法，用它来确定一个给定的无向图G=（V,E）中是否包含一个回路。所给出算法的运行时间应为O(V)，这一时

7、间独立于E。根据引理22.11即可得到一个合适的算法：对图G做DFS，如果在循环里找到一条反向边，则说明有环。如果循环次数达到V次，则说明有环（无环图的边数EV-1），否则无环。22.4-4 证明或者反证：如果一个有向图G包含回路，则TOPOLOGICAL-SORT(G)能产生一个顶点的排序序列，它可以最小化“坏”边的数目。所谓“坏”边，即那些与所生成的顶点序列不一致的边。不正确。例如下图，从0运行DFS生成序列0-1-2，有1条bad edge (2,0)；而从1运行DFS生成序列1-2-0，有2条bad edge (0,1),(0,1)。22.5-3 Deaver教授声称，用于强连通分支的

8、算法可以这样简化，即在第二次深度优先搜索中使用原图，并按完成时间递增的顺序来扫描各顶点。这位教授的说法正确吗？以图22-9为例（书中338页，第二版），如果按照Deaver教授的说法做，则我们会依次访问f、g和h节点。显然它们不属于同一个强连通分量。22.5-5 给出一个O(V+E)时间的算法，以计算一个有向图G=(V,E)的分支图。注意在算法产生的分支图中，两个顶点之间至多只能有一条边。算法根据书339页（第二版）SCC算法下面的内容得到：STEP1：求强联通分量，结果用sccu表示，即顶点u属于第sccu个强联通分量，O(V+E)STEP2：按照sccu从小到大对顶点排序(计数排序)，O(

9、V)STEP3：把每个强联通分量的第一个顶点加入到VSCC中，O(V)STEP4：计算集合S=(x, y)|edge(u, v)E,x=sccu,y=sccv,x!=y，O(E)STEP5：对S做基数排序，即两次计数排序，O(V+E)STEP6：把每个不同的(x, y)加入到ESCC中，O(E)总时间O(V+E)23.1-4 给出一个连通图的例子，使得边集(u,v):存在着一个割(S,V-S),使得(u,v)是一条通过(S,V-S)的轻边不会形成一颗最小生成树。每条边都是一条轻边（对于任意一个割来说），但是该图不是一个MST11123.1-7 论证：如果图中所有边的权值都是正的，那么，任何连接

10、所有顶点、且有着最小总权值的边的子集必为一棵树。请给出一个例子来说明如果允许某些权值非正的话，这一结论就不成立了。证明：1）此图不包含回路，反之，若包含回路，那么可以选择构成回路的边集合中权重最大的边，将这条边从边集中删除。经过变换之后，此图连通性不改变，而且总权重减少。所以总权重最小的连接所有结点的一个边集，必然不包含回路，所以形成一棵树。2）画个三角形即可，3条边权重是-1，那么如果边集只有2个边，总权重是最少是-2。边集如果是3边，那么权重是-3。-3-2但是3边是圈，2边是树，所以不成立。23.2-4 假设在某个图中，所有边的权值均为1到|V|之间的整数。在这一条件下，Kruskal算

11、法的运行时间能达到多快？如果各边的权值都是1到W之间的常数，情况又怎样呢？如果所有边的权值均为1到|V|之间的整数，那么可以采用计数排序，时间为O(V+E)。又因为图是连通的，所以V=O(E)，因而排序时间又可以表示为O(E)。除此之外，Kruskal算法的初始化时间为O(V)，不相交集合操作时间为O(E(V)。所以总的运行时间为O(E(V)。如果各边的权值都是1到W之间的常数，答案也是相同的。23.2-6 假设在某个图中，所有边的权值都分布在1,0)之间。对于Kruskal算法和Prim算法，你可以让哪一个运行的更快一些？Kruskal排序能更快。边长分布在0,1)，排序可以使用桶排序，期望

12、运行时间O(E)。总时间O(E)+O(E(V)=O(E(V)课堂测试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:xA & y

13、B 注意，C中整数的取值范围在0到20n之间。我们希望计算出C中的元素，并且求出C的每个元素可为A与B中元素和的次数。证明：解决这个问题需要(nlgn)的时间（提示：用10n次多项式来表示A和B。）解：用10n次多项式A10n和B10n来表示A和B。Ai=1当且仅当i在集合A中出现，0=i1），以#为分隔符把P分为k个部分P1,P2,.,Pk,然后先后在文本T中使用NAIVE算法查找这k个部分（当查找到Pi时，就从查找所在位置的后一位开始查找Pi+1）。时间复杂度为（假设k个部分的长度为a1,a2,.,ak）O(n-a1+1)*a1) + O(n-a1-a2)*a2) + . + O(n-m-

14、k+1)*ak) O(n+1)*a1) + O(n+1)*a2) + . + O(n+1)*ak) O(m*(n+1)代码见下页。32.2-1如果取模q=11，那么当Rabin-Karp匹配算法在文本T=3141592653589793中搜寻模式P=26时，会遇到多少伪命中点？ 解：26模11为4，文本中模11为4的两位数字包括：15, 59, 92, 26，其中15、59、92是伪命中点，共三个。32.2-3试说明如何扩展Rabin-Karp方法以处理下列问题：在一个nXn二维字符组成中搜寻一个给定的mXm模式。（可以使该模式在水平方向和垂直方向移动，但不可以把模式旋转。） 解：1.对mXm

15、模式矩阵的每行计算模q的结果，得到一个m维向量P(mX1)；2.对以nXn文本矩阵1.n-m行、1.n-m列的位置为(0,0)元素的mXm矩阵，同样分别计算得到一个m维向量T(mX1)；3.在文本矩阵中寻找能匹配P的位置；4.对匹配位置显式测试以决定是否为真正的有效位置，类似一维情况。32.4-1当字母表为=a, b时，计算相应于模式ababbabbabbababbabb的前缀函数。 解：32.4-3试说明如何通过检查字符中PT的函数，来确定模式P在文本T中的出现位置（由P和T并置形成的长度为m+n的字符串）。 解：假设(k) = P.length，则模式P在文本T中的出现位置是k-2*P.length。（可以参考32.4-1，假设P=ababbabb，T=abbababbabb）32.4-5写出一个线性时间的算法，以确定文本T是否是另一个字符串T的循环旋转，例如：arc和car是彼此的循环旋转。 解：文本T是另一个字符串T的循环旋转 KMP-MATCH(T, T+T) = TRUE时间复杂度为O(length(T)附加题已知：T1.30 = ACGCTDAGAAGDCAGADGTDAGCDGDAGCAP1.10 = DAGCDGDAGC 1. 计算Shift Or算法中