中科大算法汪炀第二次作业

分布式算法作业

周锋 SA14011062

2.1 分析在同步和异步模型下，convergecast算法的时间复杂性。

解：（1）同步模型：最坏情况下，算法执行的每一轮中只有一个msg传递，而此时生成树汇聚最大值的算法最多执行n-1轮，也就是说同步情况下的时间复杂度为O(n-1)。

（2）异步模型：在异步模型的汇集算法的每个容许执行中，树中每个距离pr为t的处理器至多在时刻t接收消息M，因此对于每个节点而言，它到它所有子节点中t最大的路径决定了它本身时间花费。因此在最坏情况下，仍应该是同步模型下的最坏情况，即生成树中除了末端节点每一个节点只有一个子节点，此时时间复杂度仍为O(n-1)。

2.2 证明在引理2.6中，一个处理器在图G中是从P r可达的，当且仅当它的parent 变量曾被赋过值。

证明：必要性：因为图G是由parent和children确定的静态图，任一节点在收到M后才会加入到图中。即可达节点收到过M，执行了算法2.2的第五行。由于是容许执行的，所以第7行（parent:=j）也会执行。

充分性：若算法2.2的第7行执行过了，因为是容许执行，则必然有第5行也执行过了。即节点收到过M。而M又是从pr发出的，所以该节点是从pr可达的。

2.3 证明Alg2.3构造一棵以Pr为根的DFS树。

证明：连通性：假设构造的图G存在邻居节点Pj和Pi。Pj从Pr可达，但Pi从Pr是不可达的。则Pi的parent为nil或者Pi不为Pj的child。由于G里一结点从pr可达当且仅当它曾设置过自己的parent变量。所以：

1）Pj的parent必然设置过了；

2）Pi的parent为nil或者Pi属于Pj的unexplored集合。

而算法的第11和14行决定了Pj会向Pi发送M,使得Pi的parent成为Pj,Pi成为Pj的child。这与假设的结果矛盾。故Pi必然也是从Pr可达的。

无环：假设G中存在一个环，P1,P2,….,Pi,P1。令P1是该环中最早接收到M的节点。则Pi是从P1可达的，且P1的parent是Pi，P1是Pi的child。而Pi在收到M后，向P1发送M。因为P1的parent已经不为空，所以P1收到来自Pi的M时，根据第16行代码，P1会向Pi放回一个信息，不会将Pi设为parent。而Pi未收到P1返回的信息，也不会将P1设为child。与前面的出的结果矛盾。故G是无环的。

图G是一棵DFS树：只需证明在有子结点与兄弟结点未访问时，子结点总是先加入树中。

设有节点P1，P2和P3。P2和P3是P1的直接相邻节点。P1在第12~14行中先选择向P2

发送M，则P1当且仅当P2向其返回一个（第17行，第22行）时才有可能向P3发送M。而P2仅在其向所有的相邻节点发送过M后才会向P1返回。所以P2的子节点是永远先于P3加入树中的，即G是DFS树。

2.4 证明Alg2.3的时间复杂性为O(m)。

证明：

同步模型：每一轮中，根据算法，有且只有一个消息(M or Parent or Reject)在传输，从算法的第6 、14、16、20、25行发送消息的语句中可以发现：消息只发往一个处理器结点，除根结点外，所有的处理器都是收到消息后才被激活，所以，不存在多个处理器在同一轮发送消息的情况，所以时间复杂度与消息复杂度一致。

异步模型：在一个时刻内至多有一个消息在传输，因此，时间复杂度也与消息复杂度一致。消息复杂度：对任一边，可能传输的消息最多有4个，即2个M ，2个相应M 的消息（Parent or Reject），所以消息复杂度为O(m)

综上，该算法的时间复杂度为O(m)。

2.5 修改Alg2.3获得一新算法，使构造DFS树的时间复杂性为O(n)。

解：

（1）在每个处理器中维护一个本地变量，同时添加一个消息类型，在处理器Pi转发M时，发送消息N通知其余的未访问过的邻居，这样其邻居在转发M时便不会向Pi转发。

（2）在消息M和中维护一个发送数组，记录已经转发过M的处理器名称。

两种方式都是避免向已转发过M的处理器发送消息M，这样DFS树外的边不再耗时，时间复杂度也降为O(n)。

3.1 证明同步环系统中不存在匿名的、一致性的领导者选举算法。

证明：在匿名系统中，每个处理器在系统中具有相同的状态机。由Lemma3.1可知，设算法A 是使环上某个处理器为leader的算法。因为环是同步的，且只有一种初始配置。在每轮里，各处理器均发出同样的message，所以在各轮里各个处理器接收到相同的message，则状态改变也相同。所以所有处理要么同为leader，要么同时不为leader。故同步环系统中匿名的、一致性的领导者选举算法的算法是不存在的。

3.2 证明异步环系统中不存在匿名的领导者选举算法。

证明：每个处理器的初始状态和状态机相同，除了接收消息的时间可能不同外，接收到的消息序列也相同。所以最终处理器的状态也是一致的。由于处理器处理一条消息至多需要1单位时间，若某时刻某个处理器宣布自己是leader，则在有限时间内，其它处理器也会宣布自己是

leader 。故异步环系统中匿名的领导者选举算法是不存在的。

3.9 若将环R rev 划分为长度为j(j 是2的方幂)的连续片段，则所有这些片段是次序等价的。

证明：对一个整数P(0≤P≤n?1),可以表示为：

P = a i ?2i?1m

i =1

其中m=lg n,则有rev(P)= a i ?2

m?1m i =1。 设P 、Q 在同一个片段上，P1、Q1在同一片段上，且设这两个片段时相邻的，由模运算的加法可得：P1=P+ l ；Q1=Q + l 。l 表示片段的长度，l=2k 。

又因为：

Q = b i ?2i?1m

i =1

且P 、Q 在同一个片段上，有

|P-Q|

所以存在r(0≤r≤k),满足 a r ≠ b r 。否则，|P?Q|≥l。这与P 、Q 在同一个片段上矛盾。 设s=min ?{r},则根据rev(P),rev(Q)的表示方法可得：

sign(rev(P)-rev(Q))=sign (a s -b s )

而

P1=P +1= a i ?2i?1+2k m

i =1

Q1=Q +1= b i ?2i?1+2k m

i =1

显然，P 与P1的前k 位相同，Q 与Q1的前k 位相同。由0≤s≤k得

sign(rev(P1)-rev(Q1))=sign (a s -b s )

这两个相邻片段是序等价的，根据等价的传递关系，可得所有的片段都是次序等价。

附1：“表面上，1-time 复杂性至少等于时间复杂性，因为T2假定下的最坏时间不会高于O2假定下的时间。但事实并非如此，而往往O1和O2假定之下的1-time 复杂性是前一种时间复杂性的一个下界。”为什么one-time 复杂性是时间复杂性的下界呢？

解：考虑运行在环上的分布式算法的1-time 时间复杂性和时间复杂性。

<1> 1-time 时间复杂性：

满足条件O2：发送和接收一个msg 之间的时间恰好是一个时间单位，每个阶段节点转发消息都是同步进行，从而1-time 时间复杂度仅与环直径相关，为O(D)。

<2> 时间复杂度：

满足条件T2：一个msg的发送和接收之间的时间至多为一个时间单位，即为O(1)。节点转发消息并非同步进行，消息转发轨迹可能呈链状结构，时间复杂性与环节点个数相关，为O(n)。

例如：echo协议，即应答协议，主要用于调试和检测中，是路由也是网络中最常用的数据包，可以通过发送echo包知道当前的连接节点有哪些些路径，并且通过往返时间能得出路径长度。echo算法的实现，如果转发消息同步进行，则对应1-time时间复杂性，为O(D)；如果不同步转发消息，网络路径可能呈链状结构，即对应时间复杂度O(N)。Note：考虑时间复杂度，任一节点可以在O(d)时间内将询问包发送到网络上的其它节点，但却可能需要O(N)的时间接收其它节点发来的响应包。

附2：算法3.2（同步Leader选举算法）为何非唤醒msg要延迟2^i -1轮？如何修改算法3.2来改善时间复杂性？

解：

<1> 降低消息复杂度（Id最小的节点被选举为Leader，Leader节点消息的转发速度最

快）。

<2> 方案1：添加Relay变量，保证消息在转发节点不延迟，时间复杂度由O(n*2^i)降

为O(N*2^i+n-N)，N为自发唤醒的节点数。

方案2：原算法延迟函数为f(id)=2^id，时间复杂度为O（n*2^i）。通过重新定义延迟函数来降低时间复杂度，如f(id)=c*id等。消息复杂度提高？

Note：思考方案2中消息复杂度和时间复杂度的关系！！！

中科大软件学院算法复习概念综合题

一、概念题： （1）排序算法时间复杂度： 排序算法最好最坏平均 插入O(n)O(n2)O(n2) 归并O(nlogn)O(nlogn)O(nlogn) 快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度： 1、所有简单排序和堆排序都是0(1) 2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间 3、归并排序和基数排序所需辅助空间最多，为O(n) （2）渐近记号 1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n>= n0，都有0<=c1g(n)<=f(n)<=c2g(n)}。大Θ记号给出函数的渐进确界。 2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=cg(n)<=f(n)}。大Ω记号给出函数的渐进下界。 3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=f(n)<=cg(n)}。大O记号给出函数的渐进上界。 （3）二叉查找树： 执行基本操作的时间与树的高度成正比。搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表） （4）红黑树： 1、时间复杂度： 基本动态集合操作：O(log n)，n是树中元素的数目。 2、性质： 1)节点是红色或黑色。 2)根节点是黑色。 3)每个叶节点（NIL节点）是黑色的。 4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续 红结点） 5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。 3、相关概念，定理： 1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。红黑树的黑高度定义为其根节点的黑高度。 2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。(用2-3-4树理解) 3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点

中科大研究生算法试卷

2015年 7.在异步环上，一个O(n^2)的leader选举算法按顺时针单向发送消息，假设只有最大的标识符节点可以当选为leader,则当环上标识符次序为_________时该算法发送的消息数量最多。 A 0,1, … , n-1 随机 b逆时针 n-1,n-2,…,0 C 顺时序 0,1，…, n-1 d 顺时针 n-1,n-2,…,0 8.设正整数d1,d2,…,dn是n个结点的标识符集合，x = min(d1,d2,…,dn),y = max(d1,d2,…,dn)，则同步环上非均匀的leader选举算法的时间复杂性是_______ A O(n) b O(xn) c (yn) d O(nlogn) 9.在下述因素中，已知有3个阻碍分布式系统了解系统全局状态，与全局状态无关的是____ A 非及时的通信b 相对性影响c中断d算法的正确性 10. 下述说法错误的是___ A 异步系统中的消息延迟是不确定的 B 分布式算法的消息复杂性是指在所有合法的执行上发送消息总数的最大值 C 在一个异步算法中，如果不存在错误，则算法的执行只取决于初始配置 D 分补水系统终止是指系统中所有结点处于终止状态，且没有消息在传输 二．简要回答下述问题（55分） 1 构造一个16节点的环，使其高度对称，并给出所有序等价的连续片段。 2 已知事件e1,e2,e3和e4的向量时戳分别为（2,3,0,0），（1,2,0,0），（0,0,1,1），（3,6,4,2），请找出所有因果关系的事件对。

3若将消息复杂度为O(nlgn)的异步环选举算法（在阶段1向节点的2邻居发送Prob消息）修改为只向其中一个方向发送Prob消息，请问修改后算法的消息复杂度是多少？如何对其做进一步的修改使得消息复杂度仍然为O(nlgn)。 4.对于一个优化问题π，最佳可达性能比为Rmin(π)（定义如下）分别为何值时，问题π易于近似和难于近似？ 5 装箱问题是将n件物品放入尽可能少的若干个容量为1的箱子中。不妨设实例I中，物品item，（i<= j <=n ,n = 6）的大小依次为：0.4，0.3，0.6，0.7，08，0.2，请分别给出实例I 的最优解和采用首次适应（first fit）策略得到的近似解的值OPT(I)和A(I)，并给出解得构造，以及近似比Rff(I)。 6. 说明为什么用MST启发解△TSP时，其近似比是2。 三算法题（25分） 1.设一个同步匿名的单向环有n个结点，每个结点均知道n，每个节点的初始均状态相同， 每个结点上的程序相同且开始于同一时刻。 （1）请问是否存在一个确定的算法选出一个leader？简述理由。 （2）试设计一个概率的leader选举算法。 （3）请问你设计的概率算法属于哪一类算法？

中科大研究生算法试卷

算法分析 一、单选(11*3) 1、下列描述正确的是_______ A、概率算法的期望执行时间是指反复解同一输入实例所花的平均执行时间 B、概率算法的期望执行时间是指所有输入实例上所花的平均执行时间 C、概率算法的平均期望时间是指算法执行时间的上界 D、概率算法的最坏期望时间是指算法执行时间的上界 2、当问题只有一个正确的解，不存在近似解时，某概率算法总是给出一个未必正确的 解，但是随着调用该算法次数的增加，可将错误的概率控制在任意给定的范围，该算法属于_______ A、数字概率算法 B、Las Vegas算法 C、Monte Carlo 算法 D、Sherwood算法 3、Las Vegas算法的一般形式是_______ Obstinate(x){ Repeat LV(x,y,success) Until success; Return y } 设p(x)是LV成功的概率，s(x)和e(x)分别是LV成功和失败的期望时间，t(x)是算 法obstinate得到一个正确解的期望时间，则t(x)的表达式应该是_______ A、t(x)=s(x)+e(x)(1-p(x))/p(x) B、t(x)=p(x)t(x)+(1-p(x))(e(x)+t(x)) C、t(x)=p(x)s(x)+(1-p(x))(e(x)+s(x)) D、t(x)=p(x)s(x)+(1-p(x))(t(x)+s(x)) 4、若一个一致的、p-正确的MC算法是有偏的，则p至少应该满足_______ A、p<0 B、p>0 C、p>=1/2 D、p>1/2 5、若A是一个偏真的MC算法，则下列陈述正确的是_______ A、只有A返回true时解正确 B、A以较大的概率返回true C、A返回true时解必正确，A返回false时解必错误 D、A返回true时解必正确，A返回false时有可能产生错误的解。 6、用Las Vegas算法求解某问题，已知obstinate(x)找到正确的解的期望时间是288。其 中LV成功的概率为p(x)=0.2，成功时的期望s(x)是8，则失败的期望时间e(x) 是_ _____ A、70 B、102 C、210 D、280 7、一个MC算法是一致的、3/5-正确的，偏y0的，若要求出错概率不超过ε，则重复 调用MC至少为_______ A、 B、

中科大软件学院算法实验报告

算法实验报告 快速排序 1. 问题描述： 实现对数组的普通快速排序与随机快速排序 (1)实现上述两个算法 (2)统计算法的运行时间 (3)分析性能差异，作出总结 2. 算法原理： 2.1快速排序 快速排序是对冒泡排序的一种改进。它的基本思想是：选取一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准元素小，另外一部分的所有数据都要比基准元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 设要排序的数组是A[0]……A[N-1]，首先选取一个数据（普通快速排序选择的是最后一个元素, 随机快速排序是随机选择一个元素）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。 一趟快速排序的算法是： 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]； 4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]； 5）重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这

一过程一定正好是i+或j-完成的时候，此时令循环结束）。 2.2随机快速排序 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个或者最后一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。 3. 实验数据 本实验采用对80,000个随机数据进行十次排序，并取出平均值。分别用普通快速排序和随机快速排序对数据排序。用毫秒作为运行计数单位，观测两种算法所用的时间的不同。 4. 实验截图 如下图所示的时间，普通快速排序所用的平均时间为181毫秒，而随机化版本的快速排序所用时间仅仅为119毫秒。 5. 结果分析 5.1 时间分析 从实验截图得到的结果来看，随机化版本的快速排序所用时间比普通快速排序所用的平均时间少。 快速排序的平均时间复杂度为O(nlogn)，最坏时间时间可达到O(n^2)，最坏情况是当要排序的数列基本有序的时候。根据快速排序的工作原理我们知道，

中科大软件学院第一学期总结

考研究生调剂到了中科大软件学院，现在看来是一件让我觉得十分幸运的事情。中科大的学习气氛非常的浓，课程的内容也十分有新意，虽然有新意，但是又都是很基础的内容，让我收获很大，很多课程给我带来了很大的启发。直到过年时候，才腾出时间来写上一篇总结，记录我这一学期的生活和学习。我一直是一个地地道道的北方人，生在北京，长在北京，却跑到哈尔滨读了四年书。哈工大学习负担不轻，假期也很短，一直没有时间到处玩玩，再加上自己比较懒，大学期间也就去了趟长春。这次考到了中科大苏州研究院，心中对于南方的风土人情很是期待，内心中也不乏有些忐忑。 开学前，我直接跑到了南京玩了一周，玩的十分痛快，题外话暂且不提，然后从南京坐高铁到了苏州。中科大苏州研究院地处独墅湖高教园区，正巧高铁有工业园区一站，我就在工业园区站下了车。人生地不熟找不到合适的公交，直接拦下一辆出租车奔着学校这边就来了。苏州的出租车司机素质感觉比较高，礼让行人等做的都很不错，开车也很规矩。出租车司机还很健谈，就像北京的老师傅一样，听说我是来上学的，给我说了很多苏州的情况。我是提前一天前来报道的，物业态度很不好，不过好在顺利办理了入住手续，搬进了宿舍。宿舍两人寝，上床下桌，屋子不小，但是什么都没有，不过比较干净，我开学前几天都在置备东西。苏州的空气很好，略显湿润但却不潮湿，气温跟北京差不多，略高3℃左右，我很适应。住宿的地方离学校不近，走路30分钟左右，不过每天都有班车。中科大开的课程都很有意思，很多课程我遗憾的没有抢到，不过幸好没有全抢到我喜欢的课程，不然估计得累到爆。曾经我很不理解哈佛的学生为什么一学期只有8门课程还累得要死，知道我来到了号称不要命的来科大的中科大，才彻底理解了原因。中科大的课很有意思，难度也颇高，想要学好，就要付出150%的努力，而且基本上我学的所有的课都需要这种程度的努力。 下面说说我都上了些什么课，都有什么好玩的内容。英语免修过关考试侥幸水过，让我能够选一些其他我感兴趣的课程。一开始我选的是实用算法设计一课，第一节课时，老师负责任的指出此课程针对于没有算法基础的同学，恰巧此时算法分析与设计一课有一个空位，我就改选了算法分析与设计。实用算法设计一课使用的是《程序员实用算法》一书，说实在的，里面的例子都是经过精心编写的算法，非常优美，很多细节处理的十分精妙，可惜我还是更喜欢算法分析与设计一课。算法分析与设计使用的教材是经典的《算法导论》一书，整个课程跳过了一些简单的章节，但是覆盖到了算法导论中的大部分章节(不含第七部分和第八部分)。这课说实在的，超赞啊!我本科学的算法课用的是《算法概论》一书，比较偏重于算法设计，《算法导论》则是设计与分析并重。自己看《算法导论》的时候真心看不进去，这门课程一口气跟下来觉得并不吃力，而且有一种融会贯通的感觉。发现很多的时候，一个算法的时间复杂度暗示了其设计思想。上这门课的感觉还是很多问题都似曾相识，比如说经典的八皇后问题，这些问题以前在遇到的时候都是采用一些固定的策略来进行处理，并不知道为什么要采用这样的策略。这门课程让我认识到了三类基本问题：组合计数、组合优化、组合设计，每一类问题都有很多数学工具来对其进行分析和解决。顺便说一下，书中对于如何构造GF(pk)讲解的实在是让人有点稀里糊涂的，恰巧我另一门课程密码学及其应用中讲到了这些内容，让我在这点上没有稀里糊涂的跳过去。随机过程是一门神奇的课，说实在的，我一直都挺怕概率论的，我觉得概率论十分的违反直觉，很多时候得出的答案都令我十分费解，也不能够肯定是否正确。这有助于我们抛弃一些不必要的tricks，在关键的时候进行优化。(这也是CSAPP所需要达到的一个目标之一) 说完这两门课程，不妨看看上面提到过的密码学及其应用一课。在上这门课程以前，我一直认为密码学领域主要是一些数学问题，程序员需要关注的内容很少;上了这门课程后，我发现，所有的程序员都应该学习一下密码学的基本知识，走出密码学的误区。在这门课程上，我了解了，即便是有了安全的加密方式，如果使用不当的话，仍然可能会泄密或收到被攻击者伪装成正常消息而受到欺骗，非对称加密并不比对称加密更安全，反而，非对称加密方式由于加密速度较慢，使用范围会受到限制。有些不

北京航空航天大学 《算法导论》期末参考题(有一部分考到了)

一、选择题 1.算法分析中，记号O表示（B），记号?标售（A）,记号Θ表示（D） A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界 2.以下关于渐进记号的性质是正确的有：（A） A f(n) =Θ(g(n)),g(n) =Θ(h(n))?f(n) =Θ(h(n)) B f(n) =O(g(n)),g(n) =O(h(n)) ?h(n) =O(f(n)) C O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D f(n) = O(g(n)) ?g(n) = O(f(n)) 3. 记号O的定义正确的是（A）。 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }； B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤ f(n) }； C O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 4. 记号?的定义正确的是（B）。 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }； B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；

C (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 5. T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是( C ) A T（n）= T（n – 1）+1，T（1）=1 B T（n）= 2n2 C T（n）= T（n/2）+1，T（1）=1 D T（n）= 3nlog2n 6. 动态规划算法的基本要素为（C） A 最优子结构性质与贪心选择性质 B 重叠子问题性质与贪心选择性质 C 最优子结构性质与重叠子问题性质 D 预排序与递归调用 7.下列不是动态规划算法基本步骤的是（ A ）。 A 找出最优解的性质 B 构造最优解 C 算出最优解 D 定义最优解 8.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A 最优子结构性质与贪心选择性质 B 重叠子问题性质与贪心选择性质 C 最优子结构性质与重叠子问题性质

中科大算法导论实验报告

实验一常见排序算法的实现与性能比较 一、实验环境 操作系统：Windows XP操作系统 编程语言：C语言 开发工具：Microsoft Visual C++ 6.0 二、问题描述 实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法 三、实验要求 A．在随机产生的空间大小分别为 N = 10， 1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。 B．结果输出: 1） N=10时，排序结果。 2） N=1000，10000，100000时，对同一个样本实例，不同排序完 成所需的时间。 3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。 四、各种排序算法的原理及算法语言描述 （1）合并排序算法 1）合并排序的原理： 采用分治法。分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括n/2 个元素。治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。合并: 合并两个排好序的子序列,生成排序结果。 2）合并排序算法语言描述： void Merge(float A[],int p,int q,int r){ int n1,n2,i,j,k; float L[10],R[10]; n1=q-p+1; n2=r-q; for(i=1;i<=n1;i++){ L[i]=A[p+i-1]; } for(j=1;j<=n2;j++){ R[j]=A[q+j]; } L[n1+1]=MAX; R[n2+1]=MAX; i=1; j=1;

算法实验_中科大

实验部分 一、要求 1.算法设计与分析班实验课统一上课分为三次，分别在2013年10月9号（第六周周三）、2013年11月27号（第十三周周三）和2014年1月1号（第十八周周三）晚上19:00-22：00. 2.实验要求独立完成，发现抄袭则实验为0分（包括网上的代码），没有分组。 3.要求提交实验源码，可执行程序以及实验报告。实验报告包括程序的输入，输出，结果，演示界面，算法语言描述，原理等。要求把所有实验打包成一个rar文件后提交到软件学院教学辅助系统，并且命名文件格式为学号+姓名（eg. 学号_NAME），不符合命名格式的一律不批改。 4.程序语言不做特别要求，C、C++、JAVA均可 5.实验提交截止时间：2014/ 01/ 12 23:59:00 之前

二、题目 题目主要包括两部分：练手题（2道）和正式题目（2道）。对于练手题目，均来自ACM程序设计比赛中的常见预热题目，在实验报告中请给出详细的解题思路，并给出两个输入数据样例对应的数据输出。对于正式题目，实验报告请根据每个题目后面红色字体给出的提示完成，请重视代码编写完成以后的性能分析部分。 <一> 练手题 1.整数划分类 输入： 每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n) 输出： 对于每组输入，请输出六行。 第一行：将n划分成若干正整数之和的划分数。 第二行：将n划分成k个正整数之和的划分数。 第三行：将n划分成最大数不超过k的划分数。 第四行：将n划分成若干奇正整数之和的划分数。 第五行：将n划分成若干不同整数之和的划分数。 第六行：打印一个空行。 Sample Input 5 2 Sample Output 7 2 3 3

中科大软院算法导论区间树实验报告

区间树实验报告 1.区间树的实验源码见另外一个文件 2.区间树实验分析 2.1 需求分析 基础数据结构选择红黑树，每个结点x 包含一个区间域int[x]，x 的关键字为区间的低端点low[int[x]]，对树；进行中序遍历就可按低端点的次序列出个区间，结点还包含一个max[x]，即以x 为根的子树中所有区间的端点的最大值。如： 实验要求：将红黑树扩展为区间树 (1)区间的端点为正整数，随机生成； (2)内部节点数为n：2^4，2^6,2^8,2^10,2^12； (3)测试插入，删除，查找的时间并绘出曲线，运行次数为10 次； 2.2 程序设计 区间树的操作基本和红黑树的相同，在其基础上增加了一个新方法： INTERVAL_SEARCH(T,i）；它用来找出树中覆盖区间i 的那个结点。如果树中不存在，则返回nil[T]指针。代码如下： ITNode* IntervalTree::Interval_Search(Interval i){ ITNode* x=root; while(x!=Nil && !x->Overlap(i)){ // x != nil and i doesn't overlap int[x] if (x->left!=Nil && x->left->max>=i.low) x=x->left; else x=x->right; } return x; } 区间树的插入、删除除了有可能改变红黑树性质，还有可能改变结点的max 值。前者向红黑树那样处理就可以了，又 max[x] = max(high[int[x]], max[left[x]], max[right[x]]) 为解决后者，增加一方法Nodemax（），让它来维护结点的max 值。Nodemax()如下：void ITNode::NodeMax(ITNode* xl, ITNode* xr){ Type tp=this->interval->high;

中科大算法汪炀第二次作业

分布式算法作业 周锋 SA14011062 2.1 分析在同步和异步模型下，convergecast算法的时间复杂性。 解：（1）同步模型：最坏情况下，算法执行的每一轮中只有一个msg传递，而此时生成树汇聚最大值的算法最多执行n-1轮，也就是说同步情况下的时间复杂度为O(n-1)。 （2）异步模型：在异步模型的汇集算法的每个容许执行中，树中每个距离pr为t的处理器至多在时刻t接收消息M，因此对于每个节点而言，它到它所有子节点中t最大的路径决定了它本身时间花费。因此在最坏情况下，仍应该是同步模型下的最坏情况，即生成树中除了末端节点每一个节点只有一个子节点，此时时间复杂度仍为O(n-1)。 2.2 证明在引理2.6中，一个处理器在图G中是从P r可达的，当且仅当它的parent 变量曾被赋过值。 证明：必要性：因为图G是由parent和children确定的静态图，任一节点在收到M后才会加入到图中。即可达节点收到过M，执行了算法2.2的第五行。由于是容许执行的，所以第7行（parent:=j）也会执行。 充分性：若算法2.2的第7行执行过了，因为是容许执行，则必然有第5行也执行过了。即节点收到过M。而M又是从pr发出的，所以该节点是从pr可达的。 2.3 证明Alg2.3构造一棵以Pr为根的DFS树。 证明：连通性：假设构造的图G存在邻居节点Pj和Pi。Pj从Pr可达，但Pi从Pr是不可达的。则Pi的parent为nil或者Pi不为Pj的child。由于G里一结点从pr可达当且仅当它曾设置过自己的parent变量。所以： 1）Pj的parent必然设置过了； 2）Pi的parent为nil或者Pi属于Pj的unexplored集合。 而算法的第11和14行决定了Pj会向Pi发送M,使得Pi的parent成为Pj,Pi成为Pj的child。这与假设的结果矛盾。故Pi必然也是从Pr可达的。 无环：假设G中存在一个环，P1,P2,….,Pi,P1。令P1是该环中最早接收到M的节点。则Pi是从P1可达的，且P1的parent是Pi，P1是Pi的child。而Pi在收到M后，向P1发送M。因为P1的parent已经不为空，所以P1收到来自Pi的M时，根据第16行代码，P1会向Pi放回一个信息，不会将Pi设为parent。而Pi未收到P1返回的信息，也不会将P1设为child。与前面的出的结果矛盾。故G是无环的。 图G是一棵DFS树：只需证明在有子结点与兄弟结点未访问时，子结点总是先加入树中。 设有节点P1，P2和P3。P2和P3是P1的直接相邻节点。P1在第12~14行中先选择向P2

中科大黄刘生算法第一次作业

算法实验报告 Ex.1 若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？ 实验结果如下： 可见结果趋近于2*sqrt(2) Ex.2 在机器上用1 20 4 1x dx -? 估计π值，给出不同的n 值及精度。 计算方法就采用课上讲到的HitorMiss 算法，伪代码如下： f ←sqrt(1 – x*x) HitorMiss (f, n) { k ← 0; for i ← 1 to n do { x ← uniform(0, 1); y ← uniform(0, 1); if y ≤ f(x) then k++; }//endfor return 4*k/n; } 实验结果如下：

从总的趋势来看，n的值越大，给出的pai的精度越高。但对应到两次实验结果未必n 大的精度一定高，这是概率算法的特点。 EX.3 采用算法类似HitorMiss算法，不过加入了一些特殊处理，以便能够正确计算穿越x 轴、周期函数等的积分。 算法伪代码如下： f ← x^2 / - sqrt(x) / sin(x) MyCalc(f , minx, maxx, miny, maxy, n) { k ← 0; for i ← 1 to n do { x ← uniform(minx, maxx); y ← uniform(miny, maxy); if f(x) >= 0//函数在x轴上方，积分是f与x轴之间的部分，积分值为正 then if y <= f(x) && y >=0 k++; else//函数在x轴下方，积分是f与x轴之间的部分，积分值为负 if y >= f(x) && y <= 0 k--; }//endfor if miny > 0//函数在x轴上方 then return k / n * (maxx - minx) * (maxy - miny) + miny * (maxx - minx)); else if maxy < 0//函数在x轴下方 then return k / n * (maxx - minx) * (maxy - miny) + maxy * (maxx - minx);

中科大研究生算法试卷

算法分析 1、单选(11*3) 1、下列描述正确的是_______ A、概率算法的期望执行时间是指反复解同一输入实例所花的平均执行时间 B、概率算法的期望执行时间是指所有输入实例上所花的平均执行时间 C、概率算法的平均期望时间是指算法执行时间的上界 D、概率算法的最坏期望时间是指算法执行时间的上界 2、当问题只有一个正确的解，不存在近似解时，某概率算法总是给出一个未必正确的 解，但是随着调用该算法次数的增加，可将错误的概率控制在任意给定的范围，该算法属于_______ A、数字概率算法 B、Las Vegas算法 C、Monte Carlo 算法 D、Sherwood算法 3、Las Vegas算法的一般形式是_______ Obstinate(x){ Repeat LV(x,y,success) Until success; Return y } 设p(x)是LV成功的概率，s(x)和e(x)分别是LV成功和失败的期望时间，t(x)是算 法obstinate得到一个正确解的期望时间，则t(x)的表达式应该是_______ A、t(x)=s(x)+e(x)(1-p(x))/p(x) B、t(x)=p(x)t(x)+(1-p(x))(e(x)+t(x)) C、t(x)=p(x)s(x)+(1-p(x))(e(x)+s(x)) D、t(x)=p(x)s(x)+(1-p(x))(t(x)+s(x)) 4、若一个一致的、p-正确的MC算法是有偏的，则p至少应该满足_______ A、p<0 B、p>0 C、p>=1/2 D、p>1/2 5、若A是一个偏真的MC算法，则下列陈述正确的是_______ A、只有A返回true时解正确 B、A以较大的概率返回true C、A返回true时解必正确，A返回false时解必错误 D、A返回true时解必正确，A返回false时有可能产生错误的解。 6、用Las Vegas算法求解某问题，已知obstinate(x)找到正确的解的期望时间是288。其中LV成功的概率为p(x)=0.2，成功时的期望s(x)是8，则失败的期望时间e(x)是_ _____ A、70 B、102 C、210 D、280 7、一个MC算法是一致的、3/5-正确的，偏y0的，若要求出错概率不超过ε，则重复调用MC至少为_______ A、 B、

中科大算法导论课程实验 正式题目二最长递增子序列

算法导论 课程实验 正式题目二最长递增子序列 学号：SG13225146 姓名：张添程 日期：2013.11.28

目录 实验要求： (3) 实验设计与实现 (4) 方案一——使用最长公共子序列算法 (5) 算法描述 (5) 数据预处理 (6) 最长公共子序列（LCS）算法与实现 (7) 构造最长公共子序列（即最长递增子序列） (9) 方案二——改进最长公共子序列算法 (10) 算法描述 (10) 数据预处理 (11) 最长公共子序列（LCS）改进算法与实现 (12) 构造最长公共子序列（即最长递增子序列） (14) 方案三——动态规划方法计算最长递增子序列算法 (15) 算法描述 (15) 动态规划方法的设计与实现 (15) 构造最长递增子序列 (17) 方案四——改进的动态规划方法计算最长递增子序列算法 (18) 算法描述 (18) 动态规划方法的设计与实现 (19) 构造最长递增子序列 (21) 实验结果 (22) 实验总结 (26) 附录——程序源代码 (27) 最长递增子序列.cpp (27) Link.h (29) 快速排序.cpp (29) LCS.cpp (30) LIS.cpp (34)

最长递增子序列 学号：SG13225146 姓名：张添程 实验要求： 随机生成小于等于n的自然数的一个序列，输出其最长递增子序列（任意一个即可）。 n 分别取1000，3000，10000。 例：n=5 随机序列为5 1 4 2 3，正确输出为1 2 3，即长度为3的递增子序列。 提示：参考LCS，思考能否达到时间复杂度（O(nlogn)） 实验报告要点：描述动态规划思想，总结时间和空间复杂度。