下载文档原格式
A.1-1求的简化公式。
利用等差级数求和公式和级数线性性质：
A.1-2利用调和级数性质证明。
利用调和级数性质：
A.1-3对，证明。
对无穷递减几何级数式两边求导，再乘以：
对该式再进行同上操作得到：
A.1-4 求。
A.1-5 求的值。
当时求得
当时：
计算得到：
A.1-6 利用求和公式的线性特征证明。
令，则下式显然成立：
再把函数代换回即可。
A.1-7 求的值。
A.1-8 求的值。
A.2-1 证明有常量上界。
A.2-2 求和的渐近上界。
故渐近上界是
A.2-3 通过分割求和证明第个调和数是。
故取得下界
A.2-4 通过积分求的近似值。
A.2-5 题略。
为了保证被积函数在积分域上都连续。
思考题
A-1 求和的界
求下列和式的渐近确界。
假设，都是常量。
a)
，得到确界为
b)
根据此式得到上界：
故得到下界：
故据此得到确界
c)
故得到上界：
故得到下界：
因此得到确界。
算法导论第九章习题答案（第三版）IntroductiontoAlgorithm Exercise
9.1-1
对所有的元素，两个⼀组进⾏⽐较，共需n-1次⽐较，可以构成⼀棵⼆叉树，最⼩的元素在树的根结点上，接下来，画出⼆叉树，可以很容易的看出共需lgn-1次⽐较，所以共需n+lgn-2次⽐较才可以找出第⼆⼩的元素。
9.1-2
略。
9.2-1
在randomized-select中，对于长度为0的数组，此时p=r，直接返回A[p],所以不会进⾏递归调⽤。
9.2-2
略。
9.2-3
RANDOMIZED-SELECT(A,p,r,i){
while(true){
if(p==r)
return A[p];
q=RANDOMIZED-PARTITION(A,p,r);
k=q-p+1;
if(i==k)
return A[q];
else if(i<k)
q--;
else{
q++;
i-=k;
}
}
}
9.2-4
每次都以最⼤的元素进⾏划分即可。
9.3-1
数学计算，根据书中例题仿照分析即可。
9.3-3
随机化
9.3-5
类似主元划分，只要把⿊箱⼦输出的值作为主元划分去选择即可。
9.3-6
多重⼆分即可。
9.3-7
算出中位数，之后算出每⼀个数与中位数的差即可。
9.3-8
分别取两个数组的中位数进⾏⽐较，如果两个中位数相等，那么即为所求，否则，取中位数较⼩的⼀个的右边，取较⼤的⼀个的右边，直到就剩4个元素为⽌，这时候只要求这4个元素的中位数即可。
算法导论参考答案算法导论参考答案算法导论是计算机科学领域中一本经典的教材，被广泛应用于计算机科学和工程的教学和研究中。
它涵盖了算法设计和分析的基本概念，以及各种常见算法的实现和应用。
本文将为读者提供一些算法导论中常见问题的参考答案，以帮助读者更好地理解和掌握这门课程。
1. 什么是算法？算法是一系列解决问题的步骤和规则。
它描述了如何将输入转换为输出，并在有限的时间内完成。
算法应具备正确性、可读性、健壮性和高效性等特点。
2. 如何分析算法的效率？算法的效率可以通过时间复杂度和空间复杂度来衡量。
时间复杂度表示算法执行所需的时间量级，常用的时间复杂度有O(1)、O(n)、O(logn)、O(nlogn)和O(n^2)等。
空间复杂度表示算法执行所需的额外空间量级，通常以字节为单位。
3. 什么是渐进符号？渐进符号用于表示算法的时间复杂度或空间复杂度的增长趋势。
常见的渐进符号有大O符号、Ω符号和Θ符号。
大O符号表示算法的上界，Ω符号表示算法的下界，Θ符号表示算法的平均情况。
4. 什么是分治法？分治法是一种算法设计策略，将问题分解为若干个子问题，并对子问题进行独立求解，最后将子问题的解合并得到原问题的解。
典型的分治算法有归并排序和快速排序。
5. 什么是动态规划？动态规划是一种通过将问题分解为相互重叠的子问题来求解的方法。
它通常用于求解具有重叠子问题和最优子结构性质的问题。
典型的动态规划算法有背包问题和最短路径问题。
6. 什么是贪心算法？贪心算法是一种通过每一步选择局部最优解来求解整体最优解的方法。
贪心算法通常不能保证得到全局最优解，但在某些问题上能够得到近似最优解。
典型的贪心算法有霍夫曼编码和最小生成树算法。
7. 什么是图算法？图算法是一类用于解决图结构相关问题的算法。
图由节点和边组成，节点表示对象，边表示对象之间的关系。
图算法包括图的遍历、最短路径、最小生成树和网络流等问题的求解。
8. 什么是NP完全问题？NP完全问题是一类在多项式时间内无法求解的问题。
算法导论32章答案32 String Matching32.1-2Suppose that all characters in the pattern P are different. Show how to accelerate NAIVE-STRING-MATCHER to run in timeO.n/ on an n-character text T.Naive-Search(T,P)for s = 1 to n – m + 1j = 0while T[s+j] == P[j] doj = j + 1if j = m return ss = j + s;该算法实际只是会扫描整个字符串的每个字符⼀次，所以其时间复杂度为O(n).31.1-3Suppose that pattern P and text T are randomly chosen strings of length m and n, respectively, from the d-ary alphabet ∑d ={0,1,2,..,d-1},where d ≧ 2.Show that the expected number of character-to-character comparisons made by the implicit loop inline 4 of the naive algorithm isover all executions of this loop. (Assume that the naive algorithm stops comparing characters for a given shift once it finds amismatch or matches the entire pattern.) Thus, for randomly chosen strings, the naive algorithm is quite efficient.当第4⾏隐含的循环执⾏i次时，其概率P为：P = 1/K i-1 * (1-1/k), if i < mP = 1/K m-1 * (1-1/k) + 1/K m , if i = m可以计算每次for循环迭代时，第4⾏的循环的平均迭代次数为：[1*(1-1/k)+2*(1/K)*(1-1/k)+3*(1/k2)(1-1/k)+…+(m-1)*(1-k m-2)(1-1/k) +m*(1/k m-1)(1-1/k) + m*(1/k m)]= 1 - 1/k + 2/k - 2/k2 + 3/k2 - 3/k3 +...+ m/k m-1 - m/k m + m/k m= 1 + 1/k + 1/k2 +...+ 1/k m-1= (1 - 1/K m) / (1 - 1/k)≤ 2所以，可知，第4⾏循环的总迭代次数为：(n-m+1) * [(1-1/K m) / (1-1/k)] ≤ 2 (n-m+1)31.1-4Suppose we allow the pattern P to contain occurrences of a gap character } that can match an arbitrary string of characters(even one of zero length). For example, the pattern ab}ba}c occurs in the text cabccbacbacab asand asNote that the gap character may occur an arbitrary number of times in the pattern but not at all in the text. Give a polynomial-time algorithm to determine whether such a pattern P occurs in a given text T, and analyze the running time of your algorithm.该算法只是要求判断是否模式P出现在该字符串中，那么问题被简化了许多。
第二章算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。
另，思考题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-15 while i > 0 and A[i] > key6 do A[i+1]←A[i]7 i ←i − 18 A[i+1]←keyC#对揑入排序算法的实现:public static void InsertionSort<T>(T[] Input) where T:IComparable<T>{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-14 while i ≥ 0 and A[i] > key5 do A[i+1]←A[i]6 i ←i − 17 A[i+1]←key循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。
算法导论9.1-1习题解答（⼆叉树）CLRS 9.1-1 :证明：在最坏情况下，利⽤n + [lgn] - 2此⽐较，即可找到n个元素中的第2⼩元素。
（提⽰：同时找最⼩元素)算法思想：1.将数组中的元素分组，每组两个元素，然后⽐较每组中的两个元素得到最⼩值，重新得到包含原来⼀半元素的数组，继续重复上述过程，那么最后⼀个元素必然为最⼩值。
如图所⽰，数组为{2, 1, 4, 3, 5}2.上述过程形成的是⼀个⼆叉树，其中叶⼦节点都为数组元素，⾮叶⼦节点刚好4个，这是⼆叉树的性质。
3.然后我们来找第⼆⼩元素，第⼆⼩元素必然跟着1，⾸先赋值为5，然后再赋值为3，然后赋值为2，即为所求。
PS：本章讨论的元素都互异，不存在相同值(见原书)#include <iostream>using namespace std;class Node{public:Node* left;Node* right;int data;Node();Node(int d);};class BinaryTree{public:Node* root;//创建树void create_tree(Node** node, int len);//求最⼩值int min(int a, int b);//寻找第⼆⼩值int search_second_small();BinaryTree();};int main(){int arr[10] = {89, 123, 7, 9, 2, 5, 25, 8, 43, 23};//叶⼦节点Node** node =new Node*[10];for(int i =0; i <10; i++)node[i] =new Node(arr[i]);BinaryTree* bi_tree =new BinaryTree();bi_tree->create_tree(node, 10);cout<<bi_tree->root->data<<endl;cout<<bi_tree->search_second_small()<<endl;return 0;}Node::Node(){left = right = NULL;}Node::Node(int d){data = d;left = right = NULL;}void BinaryTree::create_tree(Node** node, int len){//len == 2时，就剩下两个元素进⾏⽐较了，得到最后⼀个元素为root节点，即最⼩值节点 if(len ==2){root->left = node[0];root->right = node[1];root->data = min(node[0]->data, node[1]->data);}else{int new_len = (len%2) ? (len/2+1) : len/2;Node** new_node =new Node*[new_len];//new_node元素个数为奇数if(len%2){for(int i =0; i < new_len -1; i++){//构建⽗亲节点new_node[i] =new Node(min(node[2*i]->data, node[2*i+1]->data));new_node[i]->left = node[2*i];new_node[i]->right = node[2*i+1];}new_node[new_len -1] = node[len -1];}//new_node元素个数为偶数else{for(int i =0; i < new_len; i++){//构建⽗亲节点new_node[i] =new Node(min(node[2*i]->data, node[2*i+1]->data));new_node[i]->left = node[2*i];new_node[i]->right = node[2*i+1];}}create_tree(new_node, new_len);delete[] new_node;}}int BinaryTree::min(int a, int b){return a < b ? a : b;}int BinaryTree::search_second_small(){int second =1000000;Node* p = root;while(p->left != NULL && p->right != NULL){if(p->data == p->left->data && second > p->right->data){second = p->right->data;p = p->left;}else if(p->data == p->right->data && second > p->left->data){second = p->left->data;p = p->right;}elsereturn second;}return second;}BinaryTree::BinaryTree() {root = new Node();}。
Introduction to Algorithms September 24, 2004Massachusetts Institute of Technology 6.046J/18.410J Professors Piotr Indyk and Charles E. Leiserson Handout 7Problem Set 1 SolutionsExercise 1-1. Do Exercise 2.3-7 on page 37 in CLRS.Solution:The following algorithm solves the problem:1.Sort the elements in S using mergesort.2.Remove the last element from S. Let y be the value of the removed element.3.If S is nonempty, look for z=x−y in S using binary search.4.If S contains such an element z, then STOP, since we have found y and z such that x=y+z.Otherwise, repeat Step 2.5.If S is empty, then no two elements in S sum to x.Notice that when we consider an element y i of S during i th iteration, we don’t need to look at the elements that have already been considered in previous iterations. Suppose there exists y j∗S, such that x=y i+y j. If j<i, i.e. if y j has been reached prior to y i, then we would have found y i when we were searching for x−y j during j th iteration and the algorithm would have terminated then.Step 1 takes �(n lg n)time. Step 2 takes O(1)time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm is �(n lg n). We can do a more precise analysis if we notice that Step 3 actually requires �(lg(n−i))time at i th iteration.However, if we evaluate �n−1lg(n−i), we get lg(n−1)!, which is �(n lg n). So the total runningi=1time is still �(n lg n).Exercise 1-2. Do Exercise 3.1-3 on page 50 in CLRS.Exercise 1-3. Do Exercise 3.2-6 on page 57 in CLRS.Exercise 1-4. Do Problem 3-2 on page 58 of CLRS.Problem 1-1. Properties of Asymptotic NotationProve or disprove each of the following properties related to asymptotic notation. In each of the following assume that f, g, and h are asymptotically nonnegative functions.� (a) f (n ) = O (g (n )) and g (n ) = O (f (n )) implies that f (n ) = �(g (n )).Solution:This Statement is True.Since f (n ) = O (g (n )), then there exists an n 0 and a c such that for all n √ n 0, f (n ) ←Similarly, since g (n )= O (f (n )), there exists an n � 0 and a c such that for allcg (n ). �f (n ). Therefore, for all n √ max(n 0,n Hence, f (n ) = �(g (n )).�()g n ,0← �),0c 1 � g (n ) ← f (n ) ← cg (n ).n √ n c � 0 (b) f (n ) + g (n ) = �(max(f (n ),g (n ))).Solution:This Statement is True.For all n √ 1, f (n ) ← max(f (n ),g (n )) and g (n ) ← max(f (n ),g (n )). Therefore:f (n ) +g (n ) ← max(f (n ),g (n )) + max(f (n ),g (n )) ← 2 max(f (n ),g (n ))and so f (n ) + g (n )= O (max(f (n ),g (n ))). Additionally, for each n , either f (n ) √max(f (n ),g (n )) or else g (n ) √ max(f (n ),g (n )). Therefore, for all n √ 1, f (n ) + g (n ) √ max(f (n ),g (n )) and so f (n ) + g (n ) = �(max(f (n ),g (n ))). Thus, f (n ) + g (n ) = �(max(f (n ),g (n ))).(c) Transitivity: f (n ) = O (g (n )) and g (n ) = O (h (n )) implies that f (n ) = O (h (n )).Solution:This Statement is True.Since f (n )= O (g (n )), then there exists an n 0 and a c such that for all n √ n 0, �)f ()n ,0← �()g n ,0← f (n ) ← cg (n ). Similarly, since g (n ) = O (h (n )), there exists an n �h (n ). Therefore, for all n √ max(n 0,n and a c � such thatfor all n √ n Hence, f (n ) = O (h (n )).cc�h (n ).c (d) f (n ) = O (g (n )) implies that h (f (n )) = O (h (g (n )).Solution:This Statement is False.We disprove this statement by giving a counter-example. Let f (n ) = n and g (n ) = 3n and h (n )=2n . Then h (f (n )) = 2n and h (g (n )) = 8n . Since 2n is not O (8n ), this choice of f , g and h is a counter-example which disproves the theorem.(e) f(n)+o(f(n))=�(f(n)).Solution:This Statement is True.Let h(n)=o(f(n)). We prove that f(n)+o(f(n))=�(f(n)). Since for all n√1, f(n)+h(n)√f(n), then f(n)+h(n)=�(f(n)).Since h(n)=o(f(n)), then there exists an n0such that for all n>n0, h(n)←f(n).Therefore, for all n>n0, f(n)+h(n)←2f(n)and so f(n)+h(n)=O(f(n)).Thus, f(n)+h(n)=�(f(n)).(f) f(n)=o(g(n))and g(n)=o(f(n))implies f(n)=�(g(n)).Solution:This Statement is False.We disprove this statement by giving a counter-example. Consider f(n)=1+cos(�≈n)and g(n)=1−cos(�≈n).For all even values of n, f(n)=2and g(n)=0, and there does not exist a c1for which f(n)←c1g(n). Thus, f(n)is not o(g(n)), because if there does not exist a c1 for which f(n)←c1g(n), then it cannot be the case that for any c1>0and sufficiently large n, f(n)<c1g(n).For all odd values of n, f(n)=0and g(n)=2, and there does not exist a c for which g(n)←cf(n). By the above reasoning, it follows that g(n)is not o(f(n)). Also, there cannot exist c2>0for which c2g(n)←f(n), because we could set c=1/c2if sucha c2existed.We have shown that there do not exist constants c1>0and c2>0such that c2g(n)←f(n)←c1g(n). Thus, f(n)is not �(g(n)).Problem 1-2. Computing Fibonacci NumbersThe Fibonacci numbers are defined on page 56 of CLRS asF0=0,F1=1,F n=F n−1+F n−2for n√2.In Exercise 1-3, of this problem set, you showed that the n th Fibonacci number isF n=�n−� n,�5where �is the golden ratio and �is its conjugate.A fellow 6.046 student comes to you with the following simple recursive algorithm for computing the n th Fibonacci number.F IB(n)1 if n=02 then return 03 elseif n=14 then return 15 return F IB(n−1)+F IB(n−2)This algorithm is correct, since it directly implements the definition of the Fibonacci numbers. Let’s analyze its running time. Let T(n)be the worst-case running time of F IB(n).1(a) Give a recurrence for T(n), and use the substitution method to show that T(n)=O(F n).Solution: The recurrence is: T(n)=T(n−1)+T(n−2)+1.We use the substitution method, inducting on n. Our Induction Hypothesis is: T(n)←cF n−b.To prove the inductive step:T(n)←cF n−1+cF n−2−b−b+1← cF n−2b+1Therefore, T(n)←cF n−b+1provided that b√1. We choose b=2and c=10.∗{For the base case consider n0,1}and note the running time is no more than10−2=8.(b) Similarly, show that T(n)=�(F n), and hence, that T(n)=�(F n).Solution: Again the recurrence is: T(n)=T(n−1)+T(n−2)+1.We use the substitution method, inducting on n. Our Induction Hypothesis is: T(n)√F n.To prove the inductive step:T(n)√F n−1+F n−2+1√F n+1Therefore, T(n)←F n. For the base case consider n∗{0,1}and note the runningtime is no less than 1.1In this problem, please assume that all operations take unit time. In reality, the time it takes to add two numbers depends on the number of bits in the numbers being added (more precisely, on the number of memory words). However, for the purpose of this problem, the approximation of unit time addition will suffice.Professor Grigori Potemkin has recently published an improved algorithm for computing the n th Fibonacci number which uses a cleverly constructed loop to get rid of one of the recursive calls. Professor Potemkin has staked his reputation on this new algorithm, and his tenure committee has asked you to review his algorithm.F IB�(n)1 if n=02 then return 03 elseif n=14 then return 15 6 7 8 sum �1for k�1to n−2do sum �sum +F IB�(k) return sumSince it is not at all clear that this algorithm actually computes the n th Fibonacci number, let’s prove that the algorithm is correct. We’ll prove this by induction over n, using a loop invariant in the inductive step of the proof.(c) State the induction hypothesis and the base case of your correctness proof.Solution: To prove the algorithm is correct, we are inducting on n. Our inductionhypothesis is that for all n<m, Fib�(n)returns F n, the n th Fibonacci number.Our base case is m=2. We observe that the first four lines of Potemkin guaranteethat Fib�(n)returns the correct value when n<2.(d) State a loop invariant for the loop in lines 6-7. Prove, using induction over k, that your“invariant” is indeed invariant.Solution: Our loop invariant is that after the k=i iteration of the loop,sum=F i+2.We prove this induction using induction over k. We assume that after the k=(i−1)iteration of the loop, sum=F i+1. Our base case is i=1. We observe that after thefirst pass through the loop, sum=2which is the 3rd Fibonacci number.To complete the induction step we observe that if sum=F i+1after the k=(i−1)andif the call to F ib�(i)on Line 7 correctly returns F i(by the induction hypothesis of ourcorrectness proof in the previous part of the problem) then after the k=i iteration ofthe loop sum=F i+2. This follows immediately form the fact that F i+F i+1=F i+2.(e) Use your loop invariant to complete the inductive step of your correctness proof.Solution: To complete the inductive step of our correctness proof, we must show thatif F ib�(n)returns F n for all n<m then F ib�(m)returns m. From the previous partwe know that if F ib�(n)returns F n for all n<m, then at the end of the k=i iterationof the loop sum=F i+2. We can thus conclude that after the k=m−2iteration ofthe loop, sum=F m which completes our correctness proof.(f) What is the asymptotic running time, T�(n), of F IB�(n)? Would you recommendtenure for Professor Potemkin?Solution: We will argue that T�(n)=�(F n)and thus that Potemkin’s algorithm,F ib�does not improve upon the assymptotic performance of the simple recurrsivealgorithm, F ib. Therefore we would not recommend tenure for Professor Potemkin.One way to see that T�(n)=�(F n)is to observe that the only constant in the programis the 1 (in lines 5 and 4). That is, in order for the program to return F n lines 5 and 4must be executed a total of F n times.Another way to see that T�(n)=�(F n)is to use the substitution method with thehypothesis T�(n)√F n and the recurrence T�(n)=cn+�n−2T�(k).k=1Problem 1-3. Polynomial multiplicationOne can represent a polynomial, in a symbolic variable x, with degree-bound n as an array P[0..n] of coefficients. Consider two linear polynomials, A(x)=a1x+a0and B(x)=b1x+b0, where a1, a0, b1, and b0are numerical coefficients, which can be represented by the arrays [a0,a1]and [b0,b1], respectively. We can multiply A and B using the four coefficient multiplicationsm1=a1·b1,m2=a1·b0,m3=a0·b1,m4=a0·b0,as well as one numerical addition, to form the polynomialC(x)=m1x2+(m2+m3)x+m4,which can be represented by the array[c0,c1,c2]=[m4,m3+m2,m1].(a) Give a divide-and-conquer algorithm for multiplying two polynomials of degree-bound n,represented as coefficient arrays, based on this formula.Solution:We can use this idea to recursively multiply polynomials of degree n−1, where n isa power of 2, as follows:Let p(x)and q(x)be polynomials of degree n−1, and divide each into the upper n/2 and lower n/2terms:p(x)=a(x)x n/2+b(x),q(x)=c(x)x n/2+d(x),where a(x), b(x), c(x), and d(x)are polynomials of degree n/2−1. The polynomial product is thenp(x)q(x)=(a(x)x n/2+b(x))(c(x)x n/2+d(x))=a(x)c(x)x n+(a(x)d(x)+b(x)c(x))x n/2+b(x)d(x).The four polynomial products a(x)c(x), a(x)d(x), b(x)c(x), and b(x)d(x)are computed recursively.(b) Give and solve a recurrence for the worst-case running time of your algorithm.Solution:Since we can perform the dividing and combining of polynomials in time �(n), recursive polynomial multiplication gives us a running time ofT(n)=4T(n/2)+�(n)=�(n2).(c) Show how to multiply two linear polynomials A(x)=a1x+a0and B(x)=b1x+b0using only three coefficient multiplications.Solution:We can use the following 3 multiplications:m1=(a+b)(c+d)=ac+ad+bc+bd,m2=ac,m3=bd,so the polynomial product is(ax+b)(cx+d)=m2x2+(m1−m2−m3)x+m3.� (d) Give a divide-and-conquer algorithm for multiplying two polynomials of degree-bound nbased on your formula from part (c).Solution:The algorithm is the same as in part (a), except for the fact that we need only compute three products of polynomials of degree n/2 to get the polynomial product.(e) Give and solve a recurrence for the worst-case running time of your algorithm.Solution:Similar to part (b):T (n )=3T (n/2) + �(n )lg 3)= �(n �(n 1.585)Alternative solution Instead of breaking a polynomial p (x ) into two smaller polynomials a (x ) and b (x ) such that p (x )= a (x ) + x n/2b (x ), as we did above, we could do the following:Collect all the even powers of p (x ) and substitute y = x 2 to create the polynomial a (y ). Then collect all the odd powers of p (x ), factor out x and substitute y = x 2 to create the second polynomial b (y ). Then we can see thatp (x ) = a (y ) + x b (y )· Both a (y ) and b (y ) are polynomials of (roughly) half the original size and degree, and we can proceed with our multiplications in a way analogous to what was done above.Notice that, at each level k , we need to compute y k = y 2 (where y 0 = x ), whichk −1 takes time �(1) per level and does not affect the asymptotic running time.。
算法导论第八章答案8.2-4 :在O(1)的时间内，回答出输入的整数中有多少个落在区间[a...b]内。
给出的算法的预处理时间为O(n+k)算法思想：利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区C[0...k]，利用这个数组即可。
#includeusing 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<<b[i]<<endl;< p="">int m; int n;while(cin>>m>>n){ if(m >n)cout<<"区间输入不对"<<endl;< p="">else { if(n <0) cout<<"个数为"<<0<<endl;< p="">else if(m <=0&& n <= k) cout<<"个数为"<<c[n]<<endl;< p="">else if(n > k && m >0) cout<<"个数为"<<<endl;<="" c[m=""p="">else if(n > k && m <=0) cout<<"个数为"<<c[k]<<endl;< p="">else cout<<"个数为"<<<endl;<="" c[m="" p="">}} return 0; }void counting_sort(int*&a, int length, int k, int*&b, int*&c){ for(int i =0; i < k +1; i++) c[i] =0;for(int i =0; i < length; i++) c[a[i]]++;for(int i =1; i < k +1; i++) c[i] = c[i] + c[i-1];//这里需注释，因为对c数组内的元素进行减减操作会使其改变/*for(int i = length - 1; i >= 0; i--){b[c[a[i]] - 1] = a[i];c[a[i]]--;}*/ }PS:计数排序的总时间为O(k+n)，在实践中，如果当k = O(n)时，我们常常采用计数排序，这时其运行时间为O(n)8.3-4 :说明如何在O(n)时间内，对0到n^2 - 1之间的n个整数进行排序。
Introduction to Algorithm s Day 14 Massachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine, Lee Wee Sun, and Charles E. Leiserson Handout 17Problem Set 3 SolutionsMIT students: This problem set is due in lecture on Day 11.Reading: Chapters 8 and 9Both exercises and problems should be solved, but only the problems should be turned in. Exercises are intended to help you master the course material. Even though you should not turn in the exercise solutions, you are responsible for material covered by the exercises.Mark the top of each sheet with your name, the course number, the problem number, your recitation instructor and time, the date, and the names of any students with whom you collaborated. MIT students: Each problem should be done on a separate sheet (or sheets) of three-hole punched paper.You will often be called upon to “give an algorithm” to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your essay should provide the following:1. A description of the algorithm in English and, if helpful, pseudocode.2. At least one worked example or diagram to show more precisely how your algorithm works.3. A proof (or indication) of the correctness of the algorithm.4. An analysis of the running time of the algorithm.Remember, your goal is to communicate. Graders will be instructed to take off points for convoluted and obtuse descriptions.Exercise 3-1. Do exercise 8.1-2 on page 167 of CLRS.Exercise 3-2. Do exercise 8.1-3 on page 168 of CLRS.Exercise 3-3. Do exercise 8.2-3 on page 170 of CLRS.Exercise 3-4. Do exercise 8.4-2 on page 177 of CLRS.Exercise 3-5. Do exercise 9.3-1 on page 192 of CLRS.Exercise 3-6. Show that the second smallest of n elements can be found with n+Θ(lg n)comparisons in the worst case. (Hint: Also find the smallest element.)Problem 3-1. Largest i numbers in sorted orderGiven a set of n numbers, we wish to find the i largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of n and i.(a) Sort the numbers, and list the i largest.Solution:Use any optimal sorting algorithm, such as MergeSort or HeapSort. Then this can bedone in Θ(n lg n).(b) Build a max-priority queue from the numbers, and call E XTRACT-M AX i times.Solution:Call Build-Heap, Θ(n). Then call Extract-Max, Θ(lg i), i times. So, total runningtime is Θ(n+i lg i).(c) Use an order-statistic algorithm to find the i th largest number, partition around thatnumber, and sort the i largest numbers.Solution:Select the i-th largest number using SELECT, Θ(n), call partition, Θ(n), and then sortthe i largest numbers, Θ(i lg i). So our algorithm takes Θ(n+i lg i).Problem 3-2. At the wading poolYou work at a summer camp which holds regular outings for the n children which attend. One of these outings is to a nearby wading pool which always turns out to be something of a nightmare at the end because there are n wet, cranky children and a pile of 2n shoes (n left shoes and n right shoes) and it is not at all clear which kids go with which shoes. Not being particularly picky, all you care about is getting kids into shoes that fit. The only way to determine if a shoe is a match for a child is to try the shoe on the child’s foot. After trying on the shoe, you will know that it either fits, is too big, or is too small. It is important to note that you cannot accurately compare children’s feet directly with each other, nor can you compare the shoes. You know that for every kid, there are at least two shoes (one left shoe and one right shoe) that will fit, and your task is to shoe all of the children efficiently so that you can go home. There are enough shoes that each child will find a pair which fits her. Assume that each comparison (trying a shoe on a foot) takes one time unit.(a) Describe a deterministic algorithm that uses Θ(n 2) comparisons to pair children withshoes.Solution:For each child, try on all the shoes until you find the two shoes that fit. T (n )= T (n − 2) + O (n ) = Θ(n 2).(b) Prove a lower bound of Ω(n lg n ) for the number of comparisons that must be madeby an algorithm solving this problem. (Hint: How many leaves does the decision tree have?)Solution:There are n ! ways that left shoes can be assigned to children and n ! ways that right shoes can be assigned to children. So the decision tree should have n !2 leaves. n !2 ≥ n ! h ≥ lg(n !)h ≥ lg ( ne )n by Stirling’s Approximation = n lg n − n lg e= Ω(n lg n )(c) How might you partition the children into those with a smaller shoe size than a “pivot”child, and those with a larger shoe size than the pivot child?Solution:Take the pivot child and try on all the shoes until you find one that fits. This should take Θ(n ) time as there are 2n shoes. Then try the shoe on all the children. If the shoe is too small, then they have larger feet than the pivot child. If the shoe is too big, then they have smaller feet than the pivot child. This should also take Θ(n ) time making our partition algorithm run in linear time.(d) Give a randomized algorithm whose expected number of comparisons is O (n lg n ),and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?Solution:This is similar to quicksort. Pick a random child. Partition the children around that child as in part (c). Then take the shoe you used to partition the children and partition the shoes around it. Take the two shoes and pivot child and put them in the group of paired children. Then recurse on the two groups of shoes and children. This should have the same analysis as randomized quicksort because we have only added an extra call to partition which will still make the work done at each level Θ(n ).。
