当前位置：文档之家 › 算法函数,算法作业,算法导论

算法函数,算法作业,算法导论

  • 格式：docx
  • 大小：320.35 KB
  • 文档页数：7

1. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2steps, while merge sort runs in (64n lg n) steps. For which values of n does insertion sort beat merge sort?Answer: if we want the insertion sort beat the merge sort, the condition that should be satisfied with is:8n2 < 64n lg nn < 8 lg n2n< n82<= n < =43So when n range from 2 to 43，the insertion sort beat the merge sort。

2. Algorithm Mystery(A: Array [i..j] of integer)if i=j then return A[i]elsek=i+floor((j-i)/2)temp1= Mystery(A[i..k])temp2= Mystery(A[(k+1)..j]if temp1<temp2 then return temp1 else return temp2What does the recursive algorithm above compute?Determine and state the two recurrence relations of this algorithm.Determine the values of constants in the recurrences by assuming that acomparison, returning a value, reading a value from an array cell, variable assignment, arithmetic operations and the floor function have a cost of 1 each.Use one of the methods discussed in class to determine the EXACT mathematical expression for T(n). Based on that expression, state the order of complexity of this algorithm.Now use a different method to solve the recurrences and show that the order of complexity you stated in (c) is right. Show details of your work if you want to get partial credit.Answer:(a) the recursive algorithm above compute the smallest integer in the A:Array[i..j](找序列里的最小值)（b）Divide and conquer algorithm. It divide the array into two parts ,each of the two parts continue divide the array into two parts ,and when it can’t be divided , it is recursive, and then ,compare the two part and get the smaller number.(分治方法，当递归时将数组分为两块来比较,递归取小的值) （c）Answer:T steps and time costreturned value calculate k function call compareT(1) 1 0 0 0T(2) 2 1 2 2T(3) 3 2 4 4T(4) 4 3 8 8…T(n) n n-1 2(n-1) 2(n-1)T(n)=n+(n-1)*5=6n-5complexity of this algorithm: O(n)(d)T(n) = 2T(n/2) + O（1）T(n) = 4T(n/4) + 3O（1）T(n) = 8T(n/8) + 7O（1）..T(n) = nT(1) + (2lgn-1)O（1）T(n) = O(n)So complexity of this algorithm: O(n)3. Provide an algorithm for Min-Heap-Increase-Key (A, i, key); use the same pseudo-code conventions as the Heap algorithms we discussed in Ch. 6. Answer:PARENT(i)return i/2LEFT(i)return 2*iRIGHT(i)return 2*i+1MIN-HEAPIFY(A,i)l=LEFT(i)r=RIGHT(i)if l<=A.heap-size and A[l] < A[i]smallest=lelsesmallest=iif r<=A.heap-size and A[r] < A[i]smallest=relsesmallest=iif smallest!=iexchange A[i] with A[smallest]MIN=HEAPIFY (A,smallest)A.heap-size = A.lengthfor i = A.length 」downto 1MIN-HEAPIFY(A,i)HEAPSORT(A)BUILD-MIN-HEAP(A)for i=A.length downto 2exchenge A[1] with A[i]A.heap-size = A.heap-size-1MIN-HEAPIFY(A,1)4. Illustrate the operation of Min-Heap-Insert (A, 5) on the heap A=<5, 7, 6, 9, 11, 15, 14, 12, 13, 18, 17, 16>. Use the heap of Fig. 6.5 (pp 141) as a model to show the operation of the Min-Heap-Decrease-Key call. For this problem you must first figure out how to change Max-Heap-Insert and Max-Heap-Increase-Key algorithms to get Min-Heap-Insert and Min-Heap-Decrease-Key algorithms, but you do not have to provide these algorithms in your answer.57 69 11 15 14 12 13 18 17 1657 69 11 15 14 12 13 18 17 16 +∞57 69 11 15 1412 13 18 17 16 557 69 11 5 14 12 13 18 17 16 1557 59 11 6 145. Using Figure 7.1 as a model, illustrate the operations of QUICKSORT which uses the Median-of-Three pivot picking strategy (assume that the median is swapped with the rightmost element and then the Partition algorithm is called) on the array <25, 33, 22, 45, 27, 37, 40, 28, 24>.Exchange median with the rightest6. Observe that the while loop of line 5-7 of the INSERTION-SORT procedure usesa linear search or scan (backward) through the sorted subarray A[1, … ,j-1]. Can we use a binary search instead to improve the overall worst-case running time of insertion sort to Θ(n lg n)?(reference 1: INSERTION-SORT12 13 18 17 16 15reference 2: binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value, whether alone or part of a record, within a sorted array. It works by comparing the target value to the middle element of the array; if they are not equal, the lower or upper half of the array is eliminated depending on the result and the search is repeated until the position of the target value is found.)将插入排序的顺序查找改为二分查找算法：Answer：INSERTION-SORT(A)for j = 2 to A.lengthkey = A[j]//Insert A[j] into the sorted sequence A[1..j-1]high = j-1low = 1while low < highmid = (low+high)/2if key ==A[mid] thenbreakif key < A[mid] thenhigh = mid-1if key > A[mid] thenlow = mid+1for i= mid to j-1A[i+1] = A[i]A[mid] = keyWith the overall worst-case the complexity of the binary search isΘ(n lg n) but when insert the complexity of the array move is still n ²，so in general the running time can’t inprove to Θ(n lg n).(最差情况下，二分查找法的时间复杂度是) Θ(n lg n)，但是插入时数组移动的时间复杂度仍然是n ²，所以总体运行时间不能提高到Θ(n lg n).。

合集下载

算法导论课程作业答案

算法导论课程作业答案

算法导论课程作业答案Introduction to AlgorithmsMassachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leiserson Handout10Diagnostic Test SolutionsProblem1Consider the following pseudocode:R OUTINE(n)1if n=12then return13else return n+R OUTINE(n?1)(a)Give a one-sentence description of what R OUTINE(n)does.(Remember,don’t guess.) Solution:The routine gives the sum from1to n.(b)Give a precondition for the routine to work correctly.Solution:The value n must be greater than0;otherwise,the routine loops forever.(c)Give a one-sentence description of a faster implementation of the same routine. Solution:Return the value n(n+1)/2.Problem2Give a short(1–2-sentence)description of each of the following data structures:(a)FIFO queueSolution:A dynamic set where the element removed is always the one that has been in the set for the longest time.(b)Priority queueSolution:A dynamic set where each element has anassociated priority value.The element removed is the element with the highest(or lowest)priority.(c)Hash tableSolution:A dynamic set where the location of an element is computed using a function of the ele ment’s key.Problem3UsingΘ-notation,describe the worst-case running time of the best algorithm that you know for each of the following:(a)Finding an element in a sorted array.Solution:Θ(log n)(b)Finding an element in a sorted linked-list.Solution:Θ(n)(c)Inserting an element in a sorted array,once the position is found.Solution:Θ(n)(d)Inserting an element in a sorted linked-list,once the position is found.Solution:Θ(1)Problem4Describe an algorithm that locates the?rst occurrence of the largest element in a?nite list of integers,where the integers are not necessarily distinct.What is the worst-case running time of your algorithm?Solution:Idea is as follows:go through list,keeping track of the largest element found so far and its index.Update whenever necessary.Running time isΘ(n).Problem5How does the height h of a balanced binary search tree relate to the number of nodes n in the tree? Solution:h=O(lg n) Problem 6Does an undirected graph with 5vertices,each of degree 3,exist?If so,draw such a graph.If not,explain why no such graph exists.Solution:No such graph exists by the Handshaking Lemma.Every edge adds 2to the sum of the degrees.Consequently,the sum of the degrees must be even.Problem 7It is known that if a solution to Problem A exists,then a solution to Problem B exists also.(a)Professor Goldbach has just produced a 1,000-page proof that Problem A is unsolvable.If his proof turns out to be valid,can we conclude that Problem B is also unsolvable?Answer yes or no (or don’t know).Solution:No(b)Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable.If the proof turns out to be valid,can we conclude that problem A is unsolvable as well?Answer yes or no (or don’t know).Solution:YesProblem 8Consider the following statement:If 5points are placed anywhere on or inside a unit square,then there must exist two that are no more than √2/2units apart.Here are two attempts to prove this statement.Proof (a):Place 4of the points on the vertices of the square;that way they are maximally sepa-rated from one another.The 5th point must then lie within √2/2units of one of the other points,since the furthest from the corners it can be is the center,which is exactly √2/2units fromeach of the four corners.Proof (b):Partition the square into 4squares,each with a side of 1/2unit.If any two points areon or inside one of these smaller squares,the distance between these two points will be at most √2/2units.Since there are 5points and only 4squares,at least two points must fall on or inside one of the smaller squares,giving a set of points that are no more than √2/2apart.Which of the proofs are correct:(a),(b),both,or neither (or don’t know)?Solution:(b)onlyProblem9Give an inductive proof of the following statement:For every natural number n>3,we have n!>2n.Solution:Base case:True for n=4.Inductive step:Assume n!>2n.Then,multiplying both sides by(n+1),we get(n+1)n!> (n+1)2n>2?2n=2n+1.Problem10We want to line up6out of10children.Which of the following expresses the number of possible line-ups?(Circle the right answer.)(a)10!/6!(b)10!/4!(c) 106(d) 104 ·6!(e)None of the above(f)Don’t knowSolution:(b),(d)are both correctProblem11A deck of52cards is shuf?ed thoroughly.What is the probability that the4aces are all next to each other?(Circle theright answer.)(a)4!49!/52!(b)1/52!(c)4!/52!(d)4!48!/52!(e)None of the above(f)Don’t knowSolution:(a)Problem12The weather forecaster says that the probability of rain on Saturday is25%and that the probability of rain on Sunday is25%.Consider the following statement:The probability of rain during the weekend is50%.Which of the following best describes the validity of this statement?(a)If the two events(rain on Sat/rain on Sun)are independent,then we can add up the twoprobabilities,and the statement is true.Without independence,we can’t tell.(b)True,whether the two events are independent or not.(c)If the events are independent,the statement is false,because the the probability of no rainduring the weekend is9/16.If they are not independent,we can’t tell.(d)False,no matter what.(e)None of the above.(f)Don’t know.Solution:(c)Problem13A player throws darts at a target.On each trial,independentlyof the other trials,he hits the bull’s-eye with probability1/4.How many times should he throw so that his probability is75%of hitting the bull’s-eye at least once?(a)3(b)4(c)5(d)75%can’t be achieved.(e)Don’t know.Solution:(c),assuming that we want the probability to be≥0.75,not necessarily exactly0.75.Problem14Let X be an indicator random variable.Which of the following statements are true?(Circle all that apply.)(a)Pr{X=0}=Pr{X=1}=1/2(b)Pr{X=1}=E[X](c)E[X]=E[X2](d)E[X]=(E[X])2Solution:(b)and(c)only。

学习算法的经典教材推荐

学习算法的经典教材推荐

学习算法的经典教材推荐在计算机科学领域，算法是一门重要的学科。

学习算法不仅可以提高我们解决问题的能力，还可以培养我们的逻辑思维和分析能力。

因此，选择一本好的算法教材是非常重要的。

在本文中，我将向大家推荐几本经典的算法教材，希望对大家的学习有所帮助。

1.《算法导论》（Introduction to Algorithms）《算法导论》是由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein合著的一本经典教材。

这本书系统地介绍了算法设计和分析的基本原理，包括排序、图算法、动态规划等。

它以清晰的语言和丰富的示例，帮助读者理解算法的核心思想和实现细节。

《算法导论》适合作为算法课程的教材，也适合作为算法学习的参考书。

2.《算法（第4版）》（Algorithms, Part I）《算法（第4版）》是由Robert Sedgewick和Kevin Wayne合著的一本经典教材。

这本书以Java语言为基础，介绍了常见的算法和数据结构，包括排序、查找、图算法等。

它不仅提供了清晰的解释和示例代码，还包含了大量的练习题和编程项目，帮助读者巩固所学知识。

《算法（第4版）》适合初学者入门，也适合有一定算法基础的读者进一步深入学习。

3.《算法设计与分析基础》（Foundations of Algorithm Design and Analysis）《算法设计与分析基础》是由王晓东、王晓燕和李海霞合著的一本经典教材。

这本书以算法设计和分析为核心，介绍了常见的算法思想和技术，包括贪心算法、动态规划、分治算法等。

它注重理论与实践的结合，通过真实的案例和实验分析，帮助读者理解算法的应用场景和效果评估。

《算法设计与分析基础》适合计算机科学专业的学生和从业人员，也适合对算法感兴趣的读者。

4.《算法之美》《算法之美》是由吴军著的一本畅销书。

虽然不是传统的教材，但它以通俗易懂的语言，介绍了算法在现实生活中的应用和影响。

算法导论4-4

算法导论4-4

算法导论4-4读书笔记本章主要讲解了使⽤递归树⽅法求解递归式；在递归树中，每个节点表⽰⼀个单⼀⼦问题的代价，⼦问题对应某次递归函数调⽤。

我们将树中每层中的代价求和，得到每层代价，然后将所有曾的代价求和，得到所有层次的递归调⽤的总代价。

递归树适合⽤来⽣成好的猜测，然后可⽤代⼊法来验证猜测是否正确，但是在某种程度上，递归树法可能不够精确；课后练习由于本次课后练习的题⽬相似性较⾼，所以这⾥只做两题，第⼀和最后⼀道题4.4-1对递归式T(n)=3T(\lfloor n/2 \rfloor) + n，利⽤递归树确定⼀个好的渐近上界，⽤代⼊法进⾏验证。

上⾯是递归树，其中第i层有3^i个节点，每个节点的代价是(\frac{1}{2})^in，所以叶⼦节点的代价为3^{\log_2^n}，即n^{\log_2^3};所以总代价为：\begin{aligned} T(n)&=c\sum_{i=0}^{\log_2^n-1}(\frac{3}{2})^in + \theta(n^{\log_2^3}) \\[2ex] &=cn \ast \frac{(\frac{3}{2})^{\log_2^n}-1}{\frac{3} {2}-1} + \theta(n^{\log_2^3}) \\[2ex] &=2cn\ast {(\frac{3}{2})^{\log_2^n}} - 2cn + \theta(n^{\log_2^3})\\[2ex] &=2cn^{\log_2^3} - 2cn +\theta(n^{\log_2^3})\\[2ex] &=\theta(n^{\log_2^3}) \end{aligned}证明略4.4-9对递归式T(n)=T(\alpha n)+T((1-\alpha)n)+cn，利⽤递归树给出⼀个渐近紧确解，其中0<\alpha<1和c>0是常数。

《算法导论》[第3章]函数的增长-[3.1]渐进记号

《算法导论》[第3章]函数的增长-[3.1]渐进记号

《算法导论》[第3章]函数的增长-[3.1]渐进记号|概念回顾|当输⼊规模⼤到使只有运⾏时间的增长量级有关时，就使在研究算法的渐进效率。

⼏个重要渐进记号的定义：Θ(g(n))={ f(n): 存在正常数c1,c2和n0，使对所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n) }O(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=f(n)<=cg(n) }Ω(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=cg(n)<=f(n) }o(g(n))={ f(n): 对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0<=f(n)<=cg(n) }ω(g(n))={ f(n): 对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0<=cg(n)<f(n) }|习题解答|3.1-1 设f(n)与g(n)都是渐进⾮负函数。

利⽤Θ记号的基本定义来证明max(f(n),g(n))=Θ(f(n)+g(n))。

证明：因为f(n)和g(n)都使渐进⾮负函数，同时假设存在这样的整数c1,c2和n0，使得：0<=c1(f(n)+g(n))<=max(f(n)+g(n))<=c2(f(n)+g(n)) 成⽴。

令c2=1，则第3个不等式显然成⽴，因为两正数之和定⼤于两个中的最⼤值；再令c1=1/2，则第2个不等式也成⽴，因为两正数中最⼤的⼀个数定⼤于或等于两数的平均值；第1个不等式，因为f(n)与g(n)都使渐进⾮负，所以也显然成⽴。

综上，既该等式确实成⽴。

最后再根据Θ记号的定义可得：max(f(n),g(n))=Θ(f(n)+g(n))。

3.1-2 证明对任意实常数a和b，其中b>0，有[2] (n+a)^b=Θ(n^b)证明：要想证明上式成⽴，先要来证明等式：[1] 0<=c1(n^b)<=(n+a)^b<=c2(n^b)也就使说存在两个正常数c1,c2，使得当n充分⼤时(n+a)^b，能够被夹在c1(n^b)和c2(n^b)中间。