Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1
Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v) 第二章算法入门 由于时间问题有些问题没有写的很仔细,而且估计这里会存在不少不恰当之处。另,思考题2-3 关于霍纳规则,有些部分没有完成,故没把解答写上去,我对其 c 问题有疑问,请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题,没有做优化,请见谅,等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort 算法导论复习资料 一、选择题:第一章的概念、术语。 二、考点分析: 1、复杂度的渐进表示,复杂度分析。 2、正确性证明。 考点:1)正确性分析(冒泡,归并,选择);2)复杂度分析(渐进表示O,Q,?,替换法证明,先猜想,然后给出递归方程)。 循环不变性的三个性质: 1)初始化:它在循环的第一轮迭代开始之前,应该是正确的; 2)保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确; 3)当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。 插入排序算法: INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 ?Insert A[j] into the sorted sequence A[1,j - 1]. 4 i ←j - 1 5 while i > 0 and A[i] > key 6 do A[i + 1] ←A[i] 7 i ←i - 1 8 A[i + 1] ←key 插入排序的正确性证明:课本11页。 归并排序算法:课本17页及19页。 归并排序的正确性分析:课本20页。 3、分治法(基本步骤,复杂度分析)。——许多问题都可以递归求解 考点:快速排序,归并排序,渐进排序,例如:12球里面有一个坏球,怎样用最少的次数找出来。(解:共有24种状态,至少称重3次可以找出不同的球) 不是考点:线性时间选择,最接近点对,斯特拉算法求解。 解:基本步骤: 一、分解:将原问题分解成一系列的子问题; 二、解决:递归地解各子问题。若子问题足够小,则直接求解; 三、合并:将子问题的结果合并成原问题的解。 复杂度分析:分分治算法中的递归式是基于基本模式中的三个步骤的,T(n)为一个规模为n的运行时间,得到递归式 T(n)=Q(1) n<=c T(n)=aT(n/b)+D(n)+C(n) n>c 附加习题:请给出一个运行时间为Q(nlgn)的算法,使之能在给定的一个由n个整数构成的集合S 和另一个整数x时,判断出S中是否存在有两个其和等于x的元素。 Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort 重写为按非递减顺序排序 2.1.3 计算两个n 位的二进制数组之和 2.2 Analyzing algorithms 当前n-1个元素排好序后,第n 个元素已经是最大的元素了. 最好时间和最坏时间均为2()n Θ 2.3 Designing algorithms 2.3.3 计算递归方程的解 22()2(/2)2,1k if n T n T n n if n for k =?=?+ = >? (1) 当1k =时,2n =,显然有()lg T n n n = (2) 假设当k i =时公式成立,即()lg 2lg 22i i i T n n n i ===?, 则当1k i =+,即12i n +=时, 2.3.4 给出insertion sort 的递归版本的递归式 2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描,是否可以将算法的时间提高到(lg )n n Θ? 虽然用二分查找法可以将查找正确位置的时间复杂度降下来,但 是移位操作的复杂度并没有减少,所以最坏情况下该算法的时间复杂度依然是2()n Θ 2.3-7 给出一个算法,使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内,是否存在两个元素之和为x 首先利用快速排序将数组排序,时间(lg )n n Θ,然后再进行查找: Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j]≠x and i 8.2-4 :在O(1)的时间内,回答出输入的整数中有多少个落在区间[a...b]内。给出的算法的预处理时间为O(n+k) 算法思想:利用计数排序,由于在计数排序中有一个存储数值个数的临时存储区C[0...k],利用这个数组即可。 #include Chapter35 Michelle Bodnar,Andrew Lohr April12,2016 Exercise35.1-1 We could select the graph that consists of only two vertices and a single edge between them.Then,the approximation algorithm will always select both of the vertices,whereas the minimum vertex cover is only one vertex.more generally,we could pick our graph to be k edges on a graph with2k vertices so that each connected component only has a single edge.In these examples,we will have that the approximate solution is o?by a factor of two from the exact one. Exercise35.1-2 It is clear that the edges picked in line4form a matching,since we can only pick edges from E ,and the edges in E are precisely those which don’t share an endpoint with any vertex already in C,and hence with any already-picked edge. Moreover,this matching is maximal because the only edges we don’t include are the ones we removed from E .We did this because they shared an endpoint with an edge we already picked,so if we added it to the matching it would no longer be a matching. Exercise35.1-3 We will construct a bipartite graph with V=R∪L.We will try to construct it so that R is uniform,not that R is a vertex cover.However,we will make it so that the heuristic that the professor(professor who?)suggests will cause us to select all the vertices in L,and show that|L|>2|R|. Initially start o?with|R|=n?xed,and L empty.Then,for each i from 2up to n,we do the following.Let k= n i .Select S a subset of the vertices of R of size ki,and so that all the vertices in R?S have a greater or equal degree.Then,we will add k vertices to L,each of degree i,so that the union of their neighborhoods is S.Note that throughout this process,the furthest apart the degrees of the vertices in R can be is1,because each time we are picking the smallest degree vertices and increasing their degrees by1.So,once this has been done for i=n,we can pick a subset of R whose degree is one less than the rest of R(or all of R if the degrees are all equal),and for each vertex in 1算法导论第二章答案
算法导论复习资料
算法导论习题答案
算法导论 第八章答案
算法导论 第三版 第35章 答案 英
算法导论第三版答案