嵌入式工程师必读100本专业书籍 ——从小白到大牛你只差这100本书《大话数据结构》 《鸟哥的linux私房菜》 《疯狂android讲义》 《第一行代码》 《linux内核设计与实现》 《驱动设计开发》 《linux内核解密》 《unix环境高级编程》 《linux内核设计与实现》 《essential C++》 《嵌入式linux》 《linux设备驱动》 《c语言深度解剖》 《linux下的c编程》 《C Primer Plus（第五版）》 《ARM体系结构与编程（第二版）》 《lINUX设备驱动开发详解（第三版）》 《android开发艺术探讨》 《c++plus》 《Unix环境高级编程》 《与大数据同行——学习和教育的未来》 《用户体验的要素》 《编程与艺术》 《ARM嵌入式体系结构与接口技术》 《cortex-m0接口编程》 《C语言程序设计:现代方法》 《C++ Primer》
《数据结构》(严蔚敏) 《算法导论》 《Linux设备驱动开发》 《代码大全》 《深入理解计算机系统》 《UNIX环境高级编程》 《计算机安全原理》 《UNIX网络编程》 《HeadFirst设计模式》 《linux驱动》（宋保华） 《C++ primer4》 《qt5精彩实例》 《ldd3》 《C++高级编程》 《c语言教程》 《实战linux编程精髓》 《ARM教程》 《JAVA编程思想》 《HTML+CSS网页设计与布局从入门到精通》《C语言深度解剖》 《深度实践嵌入式Linux系统移植》 《unix高级编程》 《c嵌入式一站式教学》 《编译原理》 《深度实践嵌入式Linux系统移植》《UNIX环境高级编程》 《linux网络编程》 《C语言程序设计》 《unix环境高级编程》 《嵌入式linuxc语言程序设计基础教程》
Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1
Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1
Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1
Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i] 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) 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.doczj.com/doc/c114900486.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 Chapter10 Michelle Bodnar,Andrew Lohr April12,2016 Exercise10.1-1 4 41 413 41 418 41 Exercise10.1-2 We will call the stacks T and R.Initially,set T.top=0and R.top=n+1. Essentially,stack T uses the?rst part of the array and stack R uses the last part of the array.In stack T,the top is the rightmost element of T.In stack R, the top is the leftmost element of R. Algorithm1PUSH(S,x) 1:if S==T then 2:if T.top+1==R.top then 3:error“over?ow” 4:else 5:T.top=T.top+1 6:T[T.top]=x 7:end if 8:end if 9:if S==R then 10:if R.top?1==T.top then 11:error“over?ow” 12:else 13:R.top=R.top?1 14:T[T.top]=x 15:end if 16:end if 1 Algorithm2POP(S) if S==T then if T.top==0then error“under?ow” else T.top=T.top?1. return T[T.top+1] end if end if if S==R then if R.top==n+1then error“under?ow” else R.top=R.top+1. return R[R.top?1] end if end if Exercise10.1-3 4 41 413 13 138 38 Exercise10.1-4 Algorithm3ENQUEUE if Q.head==Q.tail+1,or Q.head==1and Q.tail==Q.length then error“over?ow” end if Q[Q.tail]=x if Q.tail==Q.length then Q.tail=1 else Q.tail=Q.head+1 end if Exercise10.1-5 As in the example code given in the section,we will neglect to check for over?ow and under?ow errors. 2 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 多线程算法（完整版） ——算法导论 第3版新增第27章 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Ste in 邓辉译 原文：https://www.doczj.com/doc/c114900486.html,/sites/products/documentation/cilk/boo k_chapter.pdf 本书中的主要算法都是顺序算法，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。 并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些 PC 级的电脑）组成的集群，通过专用的网络连 接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。 多处理器计算机已经以各种形态存在数十年了。计算社团早在计算机科学形成的初期就选定采用随机存取的机器模型来进行串行计算，但是对于并行计算来说，却没有一个公认的模型。这主要是因为供应商无法在并行计算机的架构模型上达成一致。比如，有些并行计算机采用共享内存，其中每个处理器都可以直接访问内存的任何位置。而有些并行计算机则使用分布式内存，每个处理器的内存都是私有的，要想去访问其他处理器的内存，必须得向其他处理器发送显式的消息。不过，随着多核技术的出现，新的笔记本和桌面电脑目前都成为共享内存的并行计算机，趋势似乎倒向了共享内存多处理这边。虽然一切还是得由时间来证明，不过我们在章中仍将采用共享内存的方法。 对于片上多处理器和其他共享内存并行计算机来说，使用静态线程是一种常见的编程方法，该方法是一种共享内存“虚拟处理器”或者线程的软件抽象。每个线程维持着自己的程序计数器，可以独立地执行代码。操作系统把线程加载到一个处理器上让其运行，并在其他线程需要运行时将其换下。操作系统允许程序员创建和销毁线程，不过这些操作的开销较大。因此，对于大多数应用来说，在计算期间线程是持久存在的，这也是为何称它们为“静态”的原因。 遗憾的是，在共享内存并行计算机上直接使用静态线程编程非常的困难且易于出错。原因之一是，为了使每个线程所承担的负载大致相当，就需要动态地在线程间分配工作，而这是一项极其复杂的任务。除了那些最简单的应用之外，程序员都得使用复杂的通信协议来实现调度器以对工作进行均衡。这种状况导致了并发平台的出现，并发平台就是一个用来协调、调度、管理并行计算资源的软件平台。有些并发平台被构建成运行时库，有些则提供了具有编译器和运行时支持的全功能的并行语言。 Chapter17 Michelle Bodnar,Andrew Lohr April12,2016 Exercise17.1-1 It woudn’t because we could make an arbitrary sequence of MULT IP USH(k),MULT IP OP(k). The cost of each will beΘ(k),so the average runtime of each will beΘ(k)not O(1). Exercise17.1-2 Suppose the input is a1followed by k?1zeros.If we call DECREMENT we must change k entries.If we then call INCREMENT on this it reverses these k changes.Thus,by calling them alternately n times,the total time isΘ(nk). Exercise17.1-3 Note that this setup is similar to the dynamic tables discussed in section 17.4.Let n be arbitrary,and have the cost of operation i be c(i).Then, n i=1c(i)= lg(n) i=1 2i+ i≤n not a power of2 1≤ lg(n) i=1 2i+n=21+ lg(n) ?1+n≤4n?1+n≤5n∈O(n) So,since to?nd the average,we divide by n,the average runtime of each com-mand is O(1). Exercise17.2-1 To every stack operation,we charge twice.First we charge the actual cost of the stack operation.Second we charge the cost of copying an element later on.Since we have the size of the stack never exceed k,and there are always k operations between backups,we always overpay by at least enough.So,the ammortized cost of the operation is constant.So,the cost of the n operation is O(n). Exercise17.2-2 1 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 1 算法导论第三次习题课 2008.12.17 2 19.1-1 如果x 是根节点：degree[sibling[x]] > sibling[x] 如果x 不是根节点：degree[sibling[x]] = sibling[x] –119.1-3 略 3 19.2-2 过程略( union 操作) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min ，用min-1代替-∞. [遍历堆中树的根节点] 4 15.1-1 15.1-2 略P195 或P329 15.1-4 f i [j]值只依赖f i [j-1]的值，从而可以从2n 压缩为2个。再加上f*、l*、l i [j]。 Print-station(l, I, j ) //i 为线路，j 为station if j>1 then Print-station(l, l i [j], j-1 ) print “line”I, “station”j; 5 15.2-1 略（见课本） 15.2-2 15.2-4 略 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1,j) return MATRIX-MULTIPLY(x, y) else return A i 6 15.3-1 （归纳法）递归调用 枚举15.3-2 没有效果，没有重叠子问题 15.3-4 略 (3)n Ο3/2(4/) n n Θ Chapter1 Michelle Bodnar,Andrew Lohr April12,2016 Exercise1.1-1 An example of a real world situation that would require sorting would be if you wanted to keep track of a bunch of people’s?le folders and be able to look up a given name quickly.A convex hull might be needed if you needed to secure a wildlife sanctuary with fencing and had to contain a bunch of speci?c nesting locations. Exercise1.1-2 One might measure memory usage of an algorithm,or number of people required to carry out a single task. Exercise1.1-3 An array.It has the limitation of requiring a lot of copying when re-sizing, inserting,and removing elements. Exercise1.1-4 They are similar since both problems can be modeled by a graph with weighted edges and involve minimizing distance,or weight,of a walk on the graph.They are di?erent because the shortest path problem considers only two vertices,whereas the traveling salesman problem considers minimizing the weight of a path that must include many vertices and end where it began. Exercise1.1-5 If you were for example keeping track of terror watch suspects,it would be unacceptable to have it occasionally bringing up a wrong decision as to whether a person is on the list or not.It would be?ne to only have an approximate solution to the shortest route on which to drive,an extra little bit of driving is not that bad. 1算法导论 第三版 第24章 答案 英
算法导论 第三版 第十九章 答案 英
Ch10算法导论 第三版 第十章 答案 英
算法导论 第三版 第十六章 答案 英
算法导论第三版新增27章中文版
算法导论 第三版 第十七章 答案 英
算法导论 第三版 第35章 答案 英
《算法导论2版》课后答案_加强版2
算法导论 第三版 第一章 答案 英
相关主题
文本预览