搜档网
当前位置:搜档网 › 算法导论第十六章答案

算法导论第十六章答案

算法导论第十六章答案
算法导论第十六章答案

算法导论 第三版 第24章 答案 英

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(T[] Input) where T:IComparable { T key; int i; for (int j = 1; j < Input.Length; j++) { key = Input[j]; i = j - 1; for (; i >= 0 && Input[i].CompareTo(key)>0;i-- ) Input[i + 1] = Input[i]; Input[i+1]=key; } } 揑入算法的设计使用的是增量(incremental)方法:在排好子数组A[1..j-1]后,将元素A[ j]揑入,形成排好序的子数组A[1..j] 这里需要注意的是由于大部分编程语言的数组都是从0开始算起,这个不伪代码认为的数组的数是第1个有所丌同,一般要注意有几个关键值要比伪代码的小1. 如果按照大部分计算机编程语言的思路,修改为: INSERTION-SORT(A) 1 for j ← 1 to length[A] 2 do key ←A[j] 3 i ←j-1

算法导论 第三版 第十九章 答案 英

Chapter19 Michelle Bodnar,Andrew Lohr April12,2016 Exercise19.2-1 First,we take the subtrees rooted at24,17,and23and add them to the root list.Then,we set H.min to18.Then,we run consolidate.First this has its degree2set to the subtree rooted at18.Then the degree1is the subtree rooted at38.Then,we get a repeated subtree of degree2when we consider the one rooted at24.So,we make it a subheap by placing the24node under18. Then,we consider the heap rooted at17.This is a repeat for heaps of degree1, so we place the heap rooted https://www.sodocs.net/doc/b117623896.html,stly we consider the heap rooted at23,and then we have that all the di?erent heaps have distinct degrees and are done,setting H.min to the smallest,that is,the one rooted at17. The three heaps that we end up with in our root list are: 23 17 38 30 41 and 1

算法导论习题答案

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,()()b b n a n +=Θ 0a >时,()()2b b b b n a n n n +<+= 对于121,2b c c ==,12()b b b c n n a c n <+< 0a <时,()b b n a n +<

算法导论 第八章答案

8.2-4 :在O(1)的时间内,回答出输入的整数中有多少个落在区间[a...b]内。给出的算法的预处理时间为O(n+k) 算法思想:利用计数排序,由于在计数排序中有一个存储数值个数的临时存储区C[0...k],利用这个数组即可。 #include using namespace std; //通过改编计数排序而来,因为有些部分需要注释掉 void counting_sort(int*&a, int length, int k, int*&b, int*&c); int main() { const int LEN =100; int*a =newint[LEN]; for(int i =0; i < LEN; i++) a[i] = (i -50)*(i -50) +4; int* b =new int[LEN]; const int k =2504; int* c =new int[k +1]; counting_sort(a, LEN, k, b, c); //这里需要注释掉 //for(int i = 0; i < LEN; i++) //cout<>m>>n) { if(m >n) cout<<"区间输入不对"< k && m >0) cout<<"个数为"< k && m <=0) cout<<"个数为"<= 0; i--) { b[c[a[i]] - 1] = a[i]; c[a[i]]--; }*/ } PS:计数排序的总时间为O(k+n),在实践中,如果当k = O(n)时,我们常常采用计数排序,

算法导论 第三版 第35章 答案 英

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

算法导论 第三版 第十六章 答案 英

Chapter16 Michelle Bodnar,Andrew Lohr April12,2016 Exercise16.1-1 The given algorithm would just stupidly compute the minimum of the O(n) numbers or return zero depending on the size of S ij.There are a possible number of subproblems that is O(n2)since we are selecting i and j so that 1≤i≤j≤n.So,the runtime would be O(n3). Exercise16.1-2 This becomes exactly the same as the original problem if we imagine time running in reverse,so it produces an optimal solution for essentially the same reasons.It is greedy because we make the best looking choice at each step. Exercise16.1-3 As a counterexample to the optimality of greedily selecting the shortest, suppose our activity times are{(1,9),(8,11),(10,20)}then,picking the shortest ?rst,we have to eliminate the other two,where if we picked the other two instead,we would have two tasks not one. As a counterexample to the optimality of greedily selecting the task that con?icts with the fewest remaining activities,suppose the activity times are {(?1,1),(2,5),(0,3),(0,3),(0,3),(4,7),(6,9),(8,11),(8,11),(8,11),(10,12)}.Then, by this greedy strategy,we would?rst pick(4,7)since it only has a two con- ?icts.However,doing so would mean that we would not be able to pick the only optimal solution of(?1,1),(2,5),(6,9),(10,12). As a counterexample to the optimality of greedily selecting the earliest start times,suppose our activity times are{(1,10),(2,3),(4,5)}.If we pick the ear-liest start time,we will only have a single activity,(1,10),whereas the optimal solution would be to pick the two other activities. Exercise16.1-4 Maintain a set of free(but already used)lecture halls F and currently busy lecture halls B.Sort the classes by start time.For each new start time which you encounter,remove a lecture hall from F,schedule the class in that room, 1

算法导论第三版答案

Solution to Exercise2.2-2 S ELECTION-S ORT.A/ n D A:length for j D1to n 1 smallest D j for i D j C1to n if A?i

2-2Selected Solutions for Chapter2:Getting Started A?low::high contains the value .The initial call to either version should have the parameters A; ;1;n. I TERATIVE-B INARY-S EARCH.A; ;low;high/ while low high mid D b.low C high/=2c if ==A?mid return mid elseif >A?mid low D mid C1 else high D mid 1 return NIL R ECURSIVE-B INARY-S EARCH.A; ;low;high/ if low>high return NIL mid D b.low C high/=2c if ==A?mid return mid elseif >A?mid return R ECURSIVE-B INARY-S EARCH.A; ;mid C1;high/ else return R ECURSIVE-B INARY-S EARCH.A; ;low;mid 1/ Both procedures terminate the search unsuccessfully when the range is empty(i.e., low>high)and terminate it successfully if the value has been found.Based on the comparison of to the middle element in the searched range,the search continues with the range halved.The recurrence for these procedures is therefore T.n/D T.n=2/C?.1/,whose solution is T.n/D?.lg n/.

相关主题