Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 18
Текст из файла (страница 18)
This assumption is valid in mostsystems because a pointer to the array is passed, not the array itself. This problem examinesthe implications of three parameter-passing strategies:1. An array is passed by pointer. Time = Θ(1).2. An array is passed by copying. Time = Θ(N), where N is the size of the array.3. An array is passed by copying only the subrange that might be accessed by the calledprocedure. Time = Θ(q - p + 1) if the subarray A[p q] is passed.a. Consider the recursive binary search algorithm for finding a number in a sorted array(see Exercise 2.3-5). Give recurrences for the worst-case running times of binarysearch when arrays are passed using each of the three methods above, and give goodupper bounds on the solutions of the recurrences.
Let N be the size of the originalproblem and n be the size of a subproblem.b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.Problems 4-4: More recurrence examplesGive asymptotic upper and lower bounds for T(n) in each of the following recurrences.Assume that T(n) is constant for sufficiently small n.
Make your bounds as tight as possible,and justify your answers.a.b.c.d.e.f.g.T(n) = 3T(n/2) + n lg n.T(n) = 5T(n/5) + n/ lg n.T(n) = 3T(n/3 + 5) + n/2.T(n) = 2T(n/2) + n/ lg n.T(n) = T(n/2) + T(n/4) + T(n/8) + n.T(n) = T(n - 1) + 1/n.h. T(n) = T(n - 1) + lg n.i. T(n) = T(n - 2) + 2 lg n.j..Problems 4-5: Fibonacci numbersThis problem develops properties of the Fibonacci numbers, which are defined by recurrence(3.21). We shall use the technique of generating functions to solve the Fibonacci recurrence.Define the generating function (or formal power series) F aswhere Fi is the ith Fibonacci number.a. Show that F (z) = z + z F (z) + z2F(z).b. Show thatwhereandc. Show thatd. Prove thatfor i > 0, rounded to the nearest integer. (Hint: Observee. Prove that Fi+2 ≥ φi for i ≥ 0.Problems 4-6: VLSI chip testing.)Professor Diogenes has n supposedly identical VLSI[1] chips that in principle are capable oftesting each other.
The professor's test jig accommodates two chips at a time. When the jig isloaded, each chip tests the other and reports whether it is good or bad. A good chip alwaysreports accurately whether the other chip is good or bad, but the answer of a bad chip cannotbe trusted. Thus, the four possible outcomes of a test are as follows:Chip A says Chip B says ConclusionB is goodB is goodB is badB is badA is goodA is badA is goodA is badboth are good, or both are badat least one is badat least one is badat least one is bada.
Show that if more than n/2 chips are bad, the professor cannot necessarily determinewhich chips are good using any strategy based on this kind of pairwise test. Assumethat the bad chips can conspire to fool the professor.b. Consider the problem of finding a single good chip from among n chips, assuming thatmore than n/2 of the chips are good. Show that ⌊n/2⌋ pairwise tests are sufficient toreduce the problem to one of nearly half the size.c.
Show that the good chips can be identified with Θ(n) pairwise tests, assuming thatmore than n/2 of the chips are good. Give and solve the recurrence that describes thenumber of tests.Problems 4-7: Monge arraysAn m × n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤m and 1 ≤ j < l ≤ n, we haveA[i, j] + A[k, l] ≤ A[i, l] + A[k, j].In other words, whenever we pick two rows and two columns of a Monge array and considerthe four elements at the intersections of the rows and the columns, the sum of the upper-leftand lower-right elements is less or equal to the sum of the lower-left and upper-rightelements.
For example, the following array is Monge:10 17 13 28 2317 22 16 29 2324 28 22 34 2411 13 6 17 745 44 32 37 2336 33 19 21 675 66 51 53 34a. Prove that an array is Monge if and only if for all i = 1, 2, …, m - 1 and j = 1, 2,…, n 1, we haveA[i, j] + A[i + 1, j + 1] ≤ A[i, j + 1] + A[i + 1, j].Note (For the "only if" part, use induction separately on rows and columns.)b. The following array is not Monge.
Change one element in order to make it Monge.(Hint: Use part (a).)37 23 22 3221 6 7 1053 34 30 3132 13 9 643 21 15 8c. Let f(i) be the index of the column containing the leftmost minimum element of row i.Prove that f(1) ≤ f(2) ≤ ··· ≤ f(m) for any m × n Monge array.d. Here is a description of a divide-and-conquer algorithm that computes the left-mostminimum element in each row of an m × n Monge array A:o Construct a submatrix A′ of A consisting of the even-numbered rows of A.Recursively determine the leftmost minimum for each row of A′.
Thencompute the leftmost minimum in the odd-numbered rows of A.Explain how to compute the leftmost minimum in the odd-numbered rows of A (giventhat the leftmost minimum of the even-numbered rows is known) in O(m + n) time.e. Write the recurrence describing the running time of the algorithm described in part (d).Show that its solution is O(m + n log m).[1]VLSI stands for "very large scale integration," which is the integrated-circuit chiptechnology used to fabricate most microprocessors today.Chapter notesRecurrences were studied as early as 1202 by L. Fibonacci, for whom the Fibonacci numbersare named.
A. De Moivre introduced the method of generating functions (see Problem 4-5)for solving recurrences. The master method is adapted from Bentley, Haken, and Saxe [41],which provides the extended method justified by Exercise 4.4-2. Knuth [182] and Liu [205]show how to solve linear recurrences using the method of generating functions. Purdom andBrown [252] and Graham, Knuth, and Patashnik [132] contain extended discussions ofrecurrence solving.Several researchers, including Akra and Bazzi [13], Roura [262], and Verma [306], havegiven methods for solving more general divide-and-conquer recurrences than are solved bythe master method. We describe the result of Akra and Bazzi here, which works forrecurrences of the form(4.15)where k ≥ 1; all coefficients ai are positive and sum to at least 1; all bi are at least 2; f(n) isbounded, positive, and nondecreasing; and for all constants c > 1, there exist constants n0, d >0 such that f(n/c) ≥ df (n) for all n ≥ n0.
This method would work on a recurrence such as T(n)= T(⌊n/3⌋) + T(⌊2n/3⌋) + O(n), for which the master method does not apply. To solve therecurrence (4.15), we first find the value of p such that. (Such a p alwaysexists, and it is unique and positive.) The solution to the recurrence is thenfor n′ a sufficiently large constant. The Akra-Bazzi method can be somewhat difficult to use,but it serves in solving recurrences that model division of the problem into substantiallyunequally sized subproblems.
The master method is simpler to use, but it applies only whensubproblem sizes are equal.Chapter 5: Probabilistic Analysis andRandomized AlgorithmsThis chapter introduces probabilistic analysis and randomized algorithms. If you areunfamiliar with the basics of probability theory, you should read Appendix C, which reviewsthis material.
Probabilistic analysis and randomized algorithms will be revisited several timesthroughout this book.5.1 The hiring problemSuppose that you need to hire a new office assistant. Your previous attempts at hiring havebeen unsuccessful, and you decide to use an employment agency. The employment agencywill send you one candidate each day. You will interview that person and then decide to eitherhire that person or not. You must pay the employment agency a small fee to interview anapplicant.
To actually hire an applicant is more costly, however, since you must fire yourcurrent office assistant and pay a large hiring fee to the employment agency. You arecommitted to having, at all times, the best possible person for the job. Therefore, you decidethat, after interviewing each applicant, if that applicant is better qualified than the currentoffice assistant, you will fire the current office assistant and hire the new applicant. You arewilling to pay the resulting price of this strategy, but you wish to estimate what that price willbe.The procedure HIRE-ASSISTANT, given below, expresses this strategy for hiring inpseudocode.
It assumes that the candidates for the office assistant job are numbered 1 throughn. The procedure assumes that you are able to, after interviewing candidate i, determine ifcandidate i is the best candidate you have seen so far. To initialize, the procedure creates adummy candidate, numbered 0, who is less qualified than each of the other candidates.HIRE-ASSISTANT(n)1 best ← 0→ candidate 0 is a least-qualified dummy candidate2 for i ← 1 to n3do interview candidate i4if candidate i is better than candidate best5then best ← i6hire candidate iThe cost model for this problem differs from the model described in Chapter 2.
We are notconcerned with the running time of HIRE-ASSISTANT, but instead with the cost incurred byinterviewing and hiring. On the surface, analyzing the cost of this algorithm may seem verydifferent from analyzing the running time of, say, merge sort. The analytical techniques used,however, are identical whether we are analyzing cost or running time. In either case, we arecounting the number of times certain basic operations are executed.Interviewing has a low cost, say ci, whereas hiring is expensive, costing ch. Let m be thenumber of people hired. Then the total cost associated with this algorithm is O(nci + mch). Nomatter how many people we hire, we always interview n candidates and thus always incur thecost nci associated with interviewing.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
