CSCI303Homework4 Problem1(6.1-1): What are the minimum and maximum numbers of elements in a heap of height h? Solution1: A heap is a semi-complete binary tree,so the minimum number of elements in a heap of height h is2h,and the maximum number of elements in a heap of height h is2h+1?1. Problem2(6.1-6): Is the sequence 23,17,14,6,13,10,1,5,7,12 a max-heap? Solution2: The sequence is not a max-heap,because7is a child of6,but7>6. Problem3(6.2-1): Using Figure6.2as a model,illustrate the operation of Max-Heapify(A,3)on the array A= 27,17,3,16,13,10,1,5,7,12,4,8,9,10 . Solution3:
Problem4(6.2-6): Show that the worst-case running time of Max-Heapify on a heap of size n is?(lg n).(Hint:For a heap with n nodes,give node values that cause Max-Heapify to be called recursively at every node on a path from the root down to a leaf.) Solution4: Consider a heap of n nodes where the root node has been changed to contain the smallest value of all the nodes.Now when we call Max-Heapify on the root,the value will have to be exchanged down with its child at every level,until it reaches the lowest level.This is because,after every swapping,the value will still be smaller than both its children(since it is the minimum),until it reaches the lowest level where it has no more children.In such a heap,the number of exchanges to max-heapify the root will be equal to the height of the tree,which is lg n.So the worst case running time is?(lg n).
\documentclass{ctexart} \usepackage{amsmath} \usepackage{amssymb} \usepackage{fancyhdr} \begin{document} \pagestyle{fancy} \title{算法分析与设计第一次作业} \author{XXXX XXX\XXXXXX} \date{2013/9/11} \maketitle \noindent 3.1-2\ 证明： 证明$(n+a)^b=\Theta(n^b)$等价于证明存在$c_{1},c_{2},n_{0}>0$使得对于任意的 $n>n_{0}$,都有$0\leq c_{1}n^b \leq (n+a)^b \leq c_{2}n^b$成立。 $\because$ $n+a\leq n+|a|$，$\therefore$当$n\geq |a|$时，$n+a\leq 2n$。 又$\because$ $n+a\geq n-|a|$，$\therefore$当$|a|\leq \frac{1}{2}$时，$n+a \geq \frac{1}{2}n$。综上，当$n\geq 2|a|$时，$0\leq \frac{1}{2}n \leq (n+a) \leq 2n$。 $\therefore$ 对于$b>0$，有$0\leq (\frac{1}{2}n)^b \leq (n+a)^b \leq (2n)^b$ $\therefore$ 存在$c_{1} = (\frac{1}{2}n)^b$，$c_{2} = (2n)^b$，$n_{0}=2|a|$， 使得$0\leq c_{1}n^b \leq (n+a)^b \leq c_{2}n^b$成立。\ \ \ $\therefore$原命题得证。 \\ \noindent 3.1-3\ 解释：设运行时间为$F(n)$，则$F(n)\geq 0(n^2)$， $\therefore$ 若$F_{1}(n) = 0(n^2)$，则$F(n)\geq F_{1}(n)$， 又$\because$ $\forall$ n，$T(n)=0$时，$T(n)=0(n^2)$，且运行时间都大于0， $\therefore$对于所有的运行时间$F(n)$都有$F(n)\geq 0(n^2)$， $\therefore$这句话是没有意义的。 \\ \noindent
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
1 第一课课程细节；绪论：算法分析，插入排序法(Insertion Sort)，归并排序(Merge Sort) 阅读：1-2章 发测验0 2 演示课1 算法的正确性 发《作业1》 3 第二课渐进记号(Asymptotic Notation)。递归公式(Recurrences)：置换法，迭代法，主方法 阅读：3-4 章，除了§4.4 4 第三课分治法：Strassen 算法，费氏数列，多项式乘法。 阅读：28 章第2 节，30章第1节 5 演示课2 递归公式，松散性 阅读：Akra-Bazzi 的讲义 6 第四课快速排序法，随机化算法 阅读：5 章 1 到 3 节，7 章 收《作业1》发《作业2》 7 演示课3 排序法：堆排序，动态集合，优先队列 阅读：6 章 8 第五课线性时间的排序法：时间下界，计数排序法，基数排序法 阅读：8 章第1 到 3 节 收《作业2》发《作业3》 9 第六课顺序统计学，中位数 阅读：9 章 10 演示课4 中位数的应用，桶排序 阅读：8 章第4 节 11 第七课散列，全域散列 阅读：11 章 1 到 3 节 收《作业3》发《作业4》 12 第八课散列函数，完美散列 阅读：11 章第 5 节 13 演示课5 测验1 复习 收《作业4》
14 评分后的作业4可以在中午拿到 15 测验1 16 演示课6 二叉搜索树，树的遍历 阅读：12 章 1 到 3 节 17 第九课二叉搜索树和快速排序法之间的关系；随机二叉搜索树的分析阅读：12 章 4 节 发《作业5》 18 第十课红黑树，旋转，插入，删除 阅读：13 章 19 演示课7 2-3树，B-树 阅读：18 章 1 到 2 节 20 第十一课高级数据结构，动态顺序统计，线段树（区间树） 阅读：14 章 收《作业5》发《作业6》 21 第十二课计算几何，区间查询 阅读：33 章 1 到 2 节 22 演示课8 凸多边形 阅读：33 章 3 节 23 第十三课van Emde Boas树，优先队列 阅读：van Emde Boas 的讲义 收《作业6》发《作业7》 24 第十四课平摊分析，表的复制，可能法 阅读：17 章 25 演示课9 竞争分析，自我排序列 26 第十五课动态规划，最长公共子序列，最优二叉搜索树 阅读：15 章 收《作业7》发《作业8》 27 第十六课贪婪算法，最小生成树 阅读：16 章 1 到 3 节，23 章 28 演示课10 贪婪算法和动态规划的范例
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) 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 Θ CSCI 303Homework 1 Problem 1(2.1-1): Using Figure 2.2as a model,illustrate the operation of Insertion-Sort on the array A = 31,41,59,26,41,58 . Solution 1: 265841594131Problem 2(2.2-1): Express the function n 3/1000?100n 2?100n +3in terms of Θ-notation. Solution 2: n 3/1000?100n 2?100n +3=Θ(n 3) Problem 3(Derived from 2.2-2): Consider sorting n numbers stored in array A by ?rst ?nding the smallest element of A and exchanging it with the element in A [1].Then ?nd the second smallest element of A ,and exchange it with A [2].Continue in this manner for the ?rst n ?1elements of A .Write pseudocode for this algorithm,which is known as Selection-Sort .Give the worst-case running times of selection sort in Θ-notation. Solution 3: Selection-Sort (A ) for i ←1to length [A ] do min-value ←A [i ] min-index =i for j =i +1to length [A ] do if A [j ]≤min-value min-value =A [j ] min-index =j A [i ]?A [min-index ] The worst-case running time of Selection-Sort is Θ(n 2). 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/e713750197.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 第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题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 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 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 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算法导论 第三版 第24章 答案 英
《算法导论2版》课后答案_加强版2
USC算法导论作业
算法导论 第三版 第十九章 答案 英
算法导论参考 答案
Ch10算法导论 第三版 第十章 答案 英
算法导论习题答案
算法导论 第三版 第十六章 答案 英
相关主题
文本预览