Design and Analysis of Algorithms (12 Spring) Due: Apr. 24, 20121. Arrange the following functions in ascending asymptotic order of growth rate:，.解：因为f1=O(n2.5)，f2=2logn*2loglogn=n*logn=O(nlogn)，f3=n1.75=O(n1.75)，f4=22n=4n=O(4n)，f5=3n=O(3n)。所以可得：f2f3f1f50）maxfind(p,x); /find(p,x)从p中找出小于x的最大面值,找不到返回p0xx-max，kk+1，Cmax；4) if(x=0) 输出C，k，否则输出impossible。分析：贪心算法并不一定总能找到最优的解，在某些情况下甚至不能找到一个解（例如：由面值3，5，9面值的币组成10），当然在本例下总能找到解，但并不保证是最优的。方法2（使用动态规划）：表达式：mincoin(pi,x,result,record)=minmincoin(pi-1,x-t*pi, result,record)+t, mincoin(pi-1,x, result,record)/resultij用于保存从面值为p0-pi的硬币中选取凑成钱数j+1的最少硬币/数，recordij保存需要面值为pi的硬币的数量。1) n硬币种类数， p 1,5,10,25,100; /初始化（p中数值从小到大排序）2) resultnxx+1，recordnx0; /对数组中的每个元素初始化3) for（i=0 to n）for（j=0 to x） /均左闭右开if(存在从面值为p0-pi的硬币中选取凑成钱数j+1的最少硬币数m)resultijm, recordijtemp; /temp为需要pi的数量4) if(resultn-1x-1x) 则表示不能凑成x，退出，否则接着执行5) 输出resultn-1x-1；/ 输出最少钱币数6) while(x0) /输出面值7) 如果recordn-1x-1大于0，输出recordn-1x-1个pn-1,否则转9；8) x=x- recordn-1x-1*pn-1, n=n-1;9) n=n-1;分析：该方法可以找到最优解，但是时间复杂度和空间复杂度都要比方法一大。3. An algorithm solves problems of size n by dividing it into three subproblems of size n/2, recursively solving each subproblems, and then combine the solutions in time. Can you analyze the running time of this algorithm?解：假设用T(n)表示解决size为n的问题所用的时间，那么解决三个size为n/2的子问题所用的时间为3*T(n/2)，由于分治之后组合结果所用的时间为n2，所有分治后所用的时间(假设为F(n) F(n)= 3*T(n/2)+ n2=MAXO(T(n/2), O(n2)4. Please using dynamic programming to solve the following knapsack problem. We are given 7 items and a knapsack. Each item i has weight of wi 0 kilograms and value of vi 0 dollars (given in table 1). The capacity of the knapsack is 14 kilograms. Then how to fill the knapsack to maximize the total value?ItemsWeightValue132243323421576653765Table 1解：用到的数据：n-物体数量，pn3-存储n个物体的重量(pi0),价值pi1和宝石号(pi2)(说明:下文中用的的数组p均指已经排过序，按物体重量从小到大排序，重量相同的按价值从小到大排序)，ck-背包容量，resultn ck-p00+1，recordn ck-p00+1-用到的辅助数组。result和record第一维为n，第二维为ck-p00+1,即在有宝石p0-pi的情况下，resultij存放背包重量为j+p00时取得的最大价值，recordij为取得最大价值时最后放进去的宝石号所在数组的组号。表达式： maxvalue(p, ck, result, record)=maxmaxvalue(p-pi, ck-pi0, result, record)+pi1, maxvalue(p-pi, ck, result, record)，即意思为在背包容量为ck中放入最大价值的宝石等于从下面两种放法中选取最大值：1.在背包中不放入某个宝石时获取的最大价值；2.在背包中放入某个宝石时获取的最大价值。(c+实现见附件)1) n宝石种类数，ck背包容量，p 宝石数据; /初始化2) sort p, if(ck=p00) /输出宝石信息7) 如果recordn-1 ck-p00大于0，输出precordn-1 ck-p00对应的宝石重量，宝石号，宝石价值,否则转9；8) ck=ck- precordn-1 ck-p000, n=n-1;9) n=n-1;5. Find a minimum s-t cut in the following directed graph (the number beside the edge is the capacity of the edge). You are required to give the computation steps and show the size of the cut.15945831S1T111111152030530205178710105解：寻找上图(假设为G)一个最小割等价于寻找一个最大流，假设对图中的任意一条有向边e=，c(e)表示该有向边的容量，f(e)表示流经该边的流量，对G如下处理得到图G1，f1(e)=c(e)-f(e),f1()=f(e) ,即使用Ford-Fulkerson算法。15945831S1T111111152030530205178710105原始图 （0）1545831S1T1111191152030515155178710105找到增广链：s-1-5-9-t，处理后得到的图 （1）1551545831S1T111119115203051515578710105找到增广链：s-3-8-t，处理后得到的图 (2)155101545831S1T111119115202551515578210105找到增广链：s-4-8-5-t，处理后得到的图 (3)1551055至此，再也找不到一条从s到t的增广链，此时所有流入s的边的流量之和(15+5+10=30)即为最大流,所一图的一个最小割即为30。6. Please answer the following questions:(a) What is polynomial reduction?(b) What is the relation among P, NP and EXP?(c) What are the main steps of proving the NP-Completeness of a problem?解：(a)多项式归约需要满足两个条件：1.一个问题（假设为X）可以经过多项式个步骤转化为另一个问题（假设为Y）；2.多项式次调用解决问题Y的算法可以解决问题X。这个过程就是多项式归约。(b)P是指存在多项式时间的算法解决的一类问题；对于给定的解，存在一个多项式时间的验证算法可以验证其是否是给定问题的解，这一类问题称为NP；EXP是指存在指数时间的算法解决的一类问题。P是NP的子集，NP是EXP的子集。(c) NPC定义：同时满足下面两个条件的问题就是NPC问题。1）.它是一个NP问题；2）.所有的NP问题都可以多项式归约到它。若证明一个问题是NPC问题可以通过两