算法分析与设计考试样卷

1. Based on what we have discussed in class, state the best asymptotic running time for each of the problems below, using the ”big Oh” notation. It is assumed that T(1) =d for some constant din all the recurrences. If you think the problem is NP-complete, state so (no running time should be given in this case). Just state the answers- you do not need to justify them.(1) Determining the 葺-th largest element in an iinsorted set of size n.(2) In a directed, weighted graph G = (V; E) with positive weights and |V| = n and E = m, determine the shortest path between a given pair of vertices. T(n) = 4T(J) + cn2. Describe the main ideas of the following strategies, and briefly describe the differences between them. divide-andconquer; dynamic programming； branch and bound3. During the course we have studied some important classes of algorithms. Three of these are Divide and Conquer Algorithms, Greedy Algorithms and Dynamic Programming Algorithms. Give non-trivial examples of each of these three types of algorithms and describe them in detai. For each example, explain what makes it such an algorithm. (That is, for your example of a greedy algorithm you should explain exactly what makes it a greedy algorithm, and so on.)Solution: There are lot of possible solutions. Natural examples would be: Divide and Conquer: Mergesort Greedy: Kruskals algorithm. Dynamic Programming: Dijkstras algorithm or Bellman-Fords algorithm.4. (30 points) Choose T or F for each of the following statements.1) The best case running time for quicksort to sort an element array is O(nlogn).2) By the master theorem, the solution to the recurrence T(n)=3T(n/3)+3n is T(n)=O(nlogn).3) Every binary search tree on n nodes has height O(logn).(4) Given a boolean formula in conjunctive normal form (i.e., Ci A C2 A . A Ck, where every Ci contains an arbitrary number of literals V-ed together), determine whether there exists a truth assignment to the variables satisfying the formula.(5) Given a boolean formula in disjunctive normal form (i.e., Ci V C2 V . V Ck, where every Ci contains an arbitrary number of literals A-ed together), determine whether there exists a truth assignment to the variables satisfying the formula.(6) In an n-node rooted tree T, determine the number of leaves whose parent has more than one child.4) By using path compression (Union- Find) technique to analyze Kruskal algorithm, the algorithms running time is O(mlog*n+nlog*n).5) Depth-first search of a graph is asymptotically faster than breadth-first search.6) Kruskals algorithm for finding a minimum spanning tree employs dynamic programming.7) The backtrack technique uses the idea of breath first search to get the optimal value.8) n!=O(2n).9) In the worst case, merge sort runs in O(n2)time.10) In computer science, all the problems are either in P or NP.11) Kruskals algorithm is faster Prims algorithm.12) Divide-and-Conquer is a bottom-up algorithm and Dynamic Programming is a top-down algorithm.13) For an unweighted graph G, Depth-first search algorithm can be used to find the shortest paths from a given vertex to other vertices.14) For two decision problems Q1 and Q2, if Q1 is polynomial time reducible to Q2, then Q1 and Q2 have the same difficulty.15) The problems solvable by Dynamic Programming can also be solved by Divide-and-Conquer algorithm.16) A (n2)algorithm always takes longer to run than a 0 (logn)algorithm.16) BFS is a linear time algorithm.17) Given n numbers a1, . . . ,an, the median of the smallest ten numbers and the largest ten numbers among them can be computed inO(n) time. T18) Every undirected connected graph on n vertices has exactly n-1 edges. F19) Given n numbers al, . ,an, where for every 1 Wi Wn, ai w 5, 9, 100; their sortedborder can be output in O(n) time. TRUE20) If a problem is NP-complete, it must also be in NP. T21) f a problem is not in P, it must be NP-complete. F22) Given an undirected unweighted graph G in n vertices and m edges and two distinct vertices sh t, the shortest st path can be computed in O(m+n) time. TRUE23) If an algorithm runs in timeO(2logn)it actually runs in polynomial time. T24) If we have a 3-SAT formula with 5 clauses, we can decide in polynomial time if it is satisfiable. T25) Every directed acyclic graph has exactly one topological ordering.26) Given a graphG= (V;E)with positive edge weights, the Bellman-Ford algo-rithm and Dijkstras algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.Solution: True. Both algorithms are guaranteed to produce the same shortest-path weight, but if there are multiple shortest paths, Dijkstras will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.27) For all positivef(n), g(n)andh(n), if f(n) =O(g(n)andf(n) = Q(h(n),then g(n) +h(n) =n (f(n).Solution: True. This follows fromf(n) =O(g(n)g(n) =Q(f(n).5. Algorithm Design(1) Given a graph G=(V, E), use Depth-First-Search to count the number of connected components in G.(2) A maximum spanning tree in a weighted graph G is a spanning tree in G with the largest weight over all spanning trees. Give an efficient algorithm that constructs a maximum spanning tree for a weighted graph G=(V, E), and analyze the running time of your algorithm.(3) Based on Quick Sorting ，please write an algorithm to find the k-th smallest element in a list.6. Find the minimal number of multiplications needed to compute the product of four matrices Al x A2 x A3 x A4. Matrix Al has the size 3x2, matrix A2 has the size 2x5,matrix A3 has the sisze 5x4, matrix A4 has the size 4x3.7.The Master Theorem applies to recurrences of the following form:T (n) = aT (n/b) + f(n)where a 1 and b 1 are constants and f(n) is an asymptotically positive function. There are 3 cases:1) . If there is a constant e 0, such that f(n) = O(nio&l,a), then T(n) = 0(7?logfta ).2) . If there is a constant k 0, such that f (w) = 0(w86 a log* n) with k 0, then Tn) = O(d劭logi+1 n).3) . If there arc small constants e 0 and 8 1 such that f(n) = Q.(n0Sha+) and af(n/b) d, then 7(n) - (/().(a) T(n)= 4T(n/2)+n2严”=严4 = n2 J) g疋=0, then f(n) is 0(w2 log* w). Case 2 applies.Thus, Tn) is 0(n2 logn)(b) T(n)= 4T(n/2)+n硼片甩4 = n2 , f(n) = n. Let =0.5, is then f(n)(?(w2_e). Case 1 applies.Thus, T(n) is 冶)(c) T(n)= 4T(n/2)+n3严口 =产4 = n2 , /5)=沖 Let =0.5, then f(n) is Q(严)-qf(n/b) = 4 f(n / 2) = 4(/2)3) = 3/2Let, then 3-/2Jn) for all nl. Case 3 applies.Thus, T(n) is 0(n3)a. T(n) = 2T (n / 2) + log nni og n。多壬 n , f(n)=logn. Let 8=0.5 , f(n) is O(n.5), that is, f(n)is O(nigba-)Thus, we are in case 1. This means T(n) is 0(n) by the master method.b. T(n) 8T(n /2) + n2nlog n。多n , f(n)=n2. Let8 1, n2is O(n38) , that is, f(n)isO(nlogha8).Thus, we are in case 1. This means T(n) is 0(n3)by the master method.c. T(n) 16T(n /2) + (n log n)4nlobga nlo2g 16 n4. F(n)= (nlogn)4. Letk4, (nlogn)4 is 0(n4 logk n) , that is,f (n) 0(n logb a log k n). Thus we are in case 2.This means T(n) is 0(n4 log5 n)d. T(n) 7T(n/3) + nnlog n l3o g,7 f(n)=n. Let 8 log3 7 1 , then n is O(nlog37-8) , that is,f(n)is O(n logba- ). Thus, we are in case 1.This means T(n) is 0(nlog37)e. T(n)二 9T(n /3) + n3 log nni o g = n 驭尸 9 n, f(n)=n3logn. lete = 1, then, n3 log n is 0(n2+) , that is f(n) isQ(n Quickselect has very poor worst-case performance. What can we do about this? Quickselect has linear-time average-case performance, but quadratic-time worst-case performance. The standard solution is to keep track of the recursion depth, and switch to a linear-time worst-case selection algorithm if this depth exceeds some limit.gba+e ).af (n / b)二 9 f (n /3)二 9(n /3) 3 log(n /3)二(n3 /3)log( n /3)let 5 二 1/3, d=1, then, af (n / b)二(n3/3)log( n/3) =d. Thus, we are in case 3.This means T (n) is 0(n3 log n)8. You have an algorithm that takes as input integers a1; . an. The running time of youralgorithm isO(a1+a2+an) Is this a polynomial time algorithm? Explain your answerNO EXPONTENTIAL ALGORITHM9. You are given an undirected graph G= (V,E).a. Show how to modify the BFS algorithm so that it decides whether G contains a cycle.b. What is the running time of your algorithm?Solutiona. We run BFS, and whenever we encounter an already seen vertexv from a node u, we stop and state that there exists a cycle in the graph (in fact, the edge (u,v) closes this cycle). If we do not encounter an already seen vertex,we terminate the execution of BFS and report thatGdoes not contain a cycle.b. The running time isO(n). Indeed, if the graph does not contain a cycle then it is a tree, and then|E| =|V| - 1,which implies that the running time of BFS in this case isO(|V| +|E|) = O(|V|). If there is a cycle in G , then wetraverse onlyO(|V|) edges ofG. In this case each vertex, except for the last one v, is being traversed at most once.We can thus uniquely charge each edge that we traverse to an unseen vertex, except the last vertexv, which is charged twice. Thus the overall number of charges is at most |V| + 1 =O(|V|), which is also the bound on the running time11. Follow LCS algorithm to find the longest common subsequence of two words ABGKMR, BCGHM. The initial matrix is given below:YjABXi000B0C0G0H0M0GKMR000012. Is the Knapsack problem, with integer capacityWand integer weights and values, fixed-parameter tractable in the parameterW?Yes, already because of the time boundO(nW).13. For a 0/1 knapsack problem, given n items, where each item has weight W and value V, find a set of items that could be put into the knapsack without over the capacity W of the knapsack. Assume that n=4，W=10,8,6,4，V=5,4,3,2，W=12。(1) give the recursive relation used in the Dynamic Programming process (5 points) (2) give the specific process of obtaining optimal value using Dynamic Programming, and give the optimal value. (10 points)(3) give the specific process of obtaining optimal value using branch-and-bound. Note: upper bound function ub=V+(W-w)(vi+1/wi+1) (10 points)14.Give an example of a graph such that running Dijkstra on it wouldgive incorrect distances.15. To design an algorithm to determine whether a simple polygon isconvex or not. Also analyze the running time of your algorithm. (notice that the input is a sequence of vertices along the polygon in a counter-clockwise fashion. A polygon is simple if its edges do not intersect. A polygon is called convex if it is the case that taking arbitrary two points p and q inside (or along the boundary of )the polygon,the segment p-q is entirely contained in the polygon.递归算法时间复杂度的计算方程式一个递归方程:丁 5) = iPnn./m) +f(n) n在引入递归树之前可以考虑一个例子：T(n) = 2T(n/2) + n2迭代2次可以得：T(n) = n2 + 2(2T(n/4) + (n/2) 2)还可以继续迭代，将其完全展开可得：T(n) = n2 + 2(n/2) 2 + 2(n/22)2 + 2(n/23) 2 + 2(n/24) 2 +.+2(n/2i) 2 +2T(n/2i + i).)而当n/2i+i = 1时，迭代结束。将(1)式小括号展开，可得：T(n) = n2 + 2(n/2)2 + 22(n/22) 2 + + 2i(n/2i)2 + 2i+iT(n/2i+i)这恰好是一个树形结构，由此可引出递归树法。图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n2 留在其中，而将两个递归项T(n/2) + T(n/2)分别摊给了他的两个子节点，如此循环。图中所有节点之和为：1 + 1/2 + (1/2)2 + (1/2)3 + + (1/2) i n2 = 2n2可知其时间复杂度为0(n2)可以得到递归树的规则为：(1) 每层的节点为T(n) = kT(n / m) + f(n)中的f(n)在当前的n/m下的值;(2) 每个节点的分支数为k；(3) 每层的右侧标出当前层中所有节点的和。再举个例子：T( n) = T(n/3) + T(2n/3) + n其递归树如下图所示：慈# 0(n loan?可见每层的值都为n,从根到叶节点的最长路径是:旳=_ 旳=(_) 2 母一 . 1因为最后递归的停止是在(2/3)如=1则 = log3/2于是k-(疋 + 1)兀=川(log 和 2 兀 +1)1=0即 T(n) = O(nlogn)总结，利用此方法解递归算法复杂度:f(n) = af(n/b) + d(n)1.当d(n)为常数时：= 12. 当 d(n) = cn 时:O(n)nb3.当d(n)为其他情况时可用递归树进行分析。由第二种情况知，若采用分治法对原算法进行改进，则着重点是采用新的计算方法缩小 a值。一般方法用递归树猜复杂度表达式并用数学归纳法证明在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n)，本文针对形 如T(n)=aT(n/b)+f(n)的递归方程进行讨论，以期望找出通用的递归方程的求解 方式。算法设计教材中给出的 Master 定理可以解决该类方程的绝大多数情况，根 据Mas ter定理：o-渐进上界、w-渐进下界、0-渐进确界。设a$l, bl为常数，f(n)为函数，T(n)=aT(n/b)+f(n)为非负数，令 x=loga：b1. f(n)=o(nx-e)， e0，那么 T(n)=0(nx)。2. f(n)=0(nx) ，那么 T(n)=0(nx logn) 。3. f(n)=w(nx+e)，e0且对于某个常数cVl和所有充分大的n有 af(n/b)Wcf(n),那么 T(n)=O(f(n)。然而，Mas ter定理并没有完全包括所有的f(n)的情况。注意到条件1和3 中的e总是大于0 的,所以在条件1和2、条件2和3之间存在所谓的“间隙”， 使得某些f(n)在该情况下不能使用该定理。因此，我们需要找到在Mas ter定理 不能使用的情况下如何解递归方程的比较通用的办法递归树。经过分析，递归树解法包含了 Mas ter定理，但是Mas ter定理可以方便的判 断出递归方程的解。产生这种结果的原因关键在于f(n)的形式，显然，当f(n) 是n的多项式p(n)形式的话必然满足Mas ter定理的要求，但是f(n)不是多项式 就需要另当别论了。下面就题目所列出的递归方程形式进行分析。一、f(n)是 n 的多项式 p(n)=f(n)因为f(n)是多项式，设p(n)=0(nk)，k$0。根据递归树计算方式，有：T(n)= aT(n/b)+nk 。T(n/b)= aT(n/b2)+(n/b)k 。T(n/b2)= aT(n/b3)+( n/b2)k 。于是得到：T(n)二 nk (1+ a/ bk + (a/ bk) 2 + (a/ bk)3 + (a/ bk)h), h=logn。b1：log a=kb这种情况下a/ bk= 1,显然T(n)= 0(n log n) ob2： log aHkb此时等比数列公比不是1,根据等比数列求和公式化简得到：T(n) = ( nk - nx)/(la/bk), x=log a。b如果 log ak，则 T(n)=0(nx)。x=log a。bb通过以上的计算表明，在Mas ter定理的条件中，针对f(n)为多项式的情况 可以使用递归树的方法进行证明和计算。同样，在f(n)不是多项式的时候也可 以通过的这种方式得到方程的解。二、f(n)是一般函数当f(n)不是n的多项式的时候，计算就会变得比较复杂，有时可能会也找 不到最终的解。但是递归树的方法给我们一种更好使用的解决办法。下面根据一 个简单的例子说明这一点：当a二b=2、f(n)=nlgn时候(lgn:logn的简记)，计算递归方程的解。2T(n)= 2T(n/2)+nlgn。T(n/b)= 2T(n/22)+(n/2)lg(n/2)。T(n/b2)= 2T(n/23)+ (n/22)lg(n/22)。于是得到：T(n)= nlgn+(nlgn-lg2)+ (nlgn-2lg2) + (nlgn-22lg2)+(nlgn-2hlg2)，h=lgn。根据等差、等比数列求和公式化简有：T(n)二n(lgn)2 一 (nT)lg2，所以 T(n)= O( n(lgn)2)，而不是 O( nlgn)。通过这个例子可以看出，当f(n)不是多项式的时候计算就有可能变得比较 复杂，甚至无法计算。但是通过递归树以及具体的数学变换技巧在某些情况下还 是可行的。综上所述，可以得出以下结论：在针对形如T(n)=aT(n/b)+f(n)的递归方程 求解方法里，使用递归树是一种比较可行的通用办法。将规模为n的问题划分为a个子问题，并且每个子问题的规模是n/b,这里a和b是正 常数。划分原问题和合并结果的代价有函数f(n)描述。主定理有三种情况，不同的情况有不同的用法设去王1和为常数，设f(n)为一函数，T(X)由递归式T(n) = aT (半)+ f(n)其中彳指和可以证明，略去上下去整不会对结果造 成影响口那么T(n)可能有如下的渐进界 若f(n) Oj 有 f(n) = O(nlog_E) t 则 T(n) = 0(nlog)若 f(n) = nlofiS t 则 T(n) = 0(nlofiSlogn)若f(n) ,且是多项式的大于二即3 e 0,有f(n) = Q(rJ嘟+号,且对C?, = 2frf thenT(2m) = T(2 苛)十 1so wc can change the var label againlet S (m) = T (2nt) n we can get a new formula21 =子(77)= S (m) = 0 ( logm)S (m) = S ( j +1, now we can use the Master Methodalso T (n) = T(2m) = 0 (loglogn)而对于某些式子，如上面所说，看着似乎可以用MM求解，但是实际上不满足3条中的任何一条，比如下面的:a 2 b 2, f (n) nlogn nl = n f (n) but n is not polynomially less than f (n) so any ease of the master method can not apply the fomular递归算法的时间复杂度分析在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析会 转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问 题，而递归方程的形式多种多样，其求解方法也是不一而足，比较常用 的有以下四种方法：方法一：代换法代换法主要需要以下两个步骤1、猜答案，不需要完全猜出来，不需要知道常熟系数的准确值，而 只需要猜出它的形式，比如猜一个递归式的时间复杂度大概是0(n2), 即它的运行时间应该是一个常熟乘以岸，可能还会有一些低阶项。方法二：递归树法递归树法主要是通过递归树将递归式展开来找到答案，然后再用代换法证明它，因为递归树法是不严谨的。例如，用递归树法求T(n) = T(n/2) + n2 ,用递归树法将该递归式展开Tg像这样将递归树展开并延伸下去，最终到叶子节点就只剩下T(1),那么 该递归树的高度就是logn,因为从顶点n出发，到n/2倒n/4,最后 到1,那么从n到1的折半次数是logn,即高度是logn (应该是一个常 数乘以logn，不过没多大关系)。而最下面叶子节点的数目是n,因为 从第一层往下，节点数变化为1,2,4,8，如果树的高度是h,那么就 会有2h个叶节点，而高度是logn，那么2|ogn=n。那么，整体所做的工 作加起来就是T(n) 了T(n) = 1+1/2+1/4+n2 = 2岸，于是可知时间复杂度为T(n) = 0(岸)。 再例如，用递归树法求T(n) = T(n/4)+T(n/2)+n2，下面用递归树的方法将 该递归式展开jodTj 铮比數列11 最后，求叶子节点的数目有点麻烦，因为分支的递归速度是不一样的， 左边降低到n/16的时候，右边才降低到n/4,左边子树的高度将会比右 边子树的高度要小。可以看到叶子节点的数目必然小于n,因为最开始 的问题大小是n,然后递归成一个n/4和n/2的两个子问题，直到最后 递归到1停止，而n/4+n/2 1和为常数设f(n)为一函数，T(n)由递归式 T(n) = aT (罟)+ f(n) 其中舟指自和即 可以证明，略去上下去整不会对结果造 成影响口那么T(n)可能有如下的渐进界若f(n) Oj 有 f(n) = O(nk,fit_E)则 T(n) = 0(1?墟)若 f(n) = nlofiS f 则 T(n) = 0(nlofitlogn)若f(n) t且是多项式的大于.即3e 0,有f(n)=。(卅唏x),且对甘c 1与所有足够大 的 m 有就住)无穷时，f(n)0(我觉得上图中第 2,3中少了个logn,具体请参考算法导论一书中对时间复杂度的讨论) 例如：T(n)=4T(n/2)+n，则 a=4,b=2,f(n)=n,计算 ng(b,a)=n2f(n)5 满足模式 一，因此 T(n) = ng(b,a)=O(n2)T(n)=4T(n/2)+n2，则根据上面计算，满足模式二，因此T(n)=O(n2logn) T(n)=4T(n/2)+n3,满足模式三，T(n)=O(n3)对于该方法的正确性，可以通过递归树的方法证明，懒的画了，可以在 大脑里构思出这样一个草图：在第一层，f(n)分解为a个子问题，每个子问题都是f(n/b),第二层每个 子问题又分解为a个子问题，每个问题都是f(n/b2) 这样递归分解下 去，最后的叶子还是0(1),整个树的高度就是log以b为底n的对数， 整个的叶子节点数目为a的log以b为底n的对数次方(agbn)，即 nog(b,a)个叶子节点。每个分支的递减速度是一样的，将每层都加在一起 便得到T(n)，此时就需要对f(n)的情况进行讨论(于是就是上面的 1,2,3)。