339 pág.

# MatemathicsForComputerScientists

Pré-visualização50 páginas

case, k = 2, a1 = 2, a2 = 8/9, b1 = 1/2, b2 = 3/4, and g(x) = x2. 12.4.1 Solving Divide and Conquer Recurrences A few years ago, two guys in Beirut named Akra and Bazzi discovered an elegant way to solve all divide-and-conquer recurrences. Theorem 76 (Akra-Bazzi, weak form). Suppose that: T (x) = \uf8f1\uf8f4\uf8f2\uf8f4\uf8f3 is defined for 0 \u2264 x \u2264 x0 k\u2211 i=1 aiT (bix) + g(x) for x > x0 where: \u2022 a1, . . . , ak are positive constants \u2022 b1, . . . , bk are constants between 0 and 1 \u2022 x0 is \u201clarge enough\u201d in a technical sense we leave unspecified \u2022 |g\u2032(x)| = O(xc) for some c \u2208 N Then: T (x) = \u398 ( xp ( 1 + \u222b x 1 g(u) up+1 du )) where p satisfies the equation \u2211k i=1 aib p i = 1. We won\u2019t prove this here, but let\u2019s apply the theorem to solve the nasty recurrence from above: T (x) = 2T (x/2) + 8/9T (3x/4) + x2 The first step is to find p, which is defined by the equation: 2 ( 1 2 )p + 8 9 ( 3 4 )p = 1 Equations of this form don\u2019t always have closed-form solutions. But, in this case, the solution is simple: p = 2. Next, we have to check that g\u2032(x) does not grow too fast: |g\u2032(x)| = |2x| = O(x) Recurrences I 157 Finally, we can compute the solution to the recurrence by integrating: T (x) = \u398 ( x2 ( 1 + \u222b x 1 u2 u3 du )) = \u398 ( x2 (1 + log x) ) = \u398(x2 log x) The Akra-Bazzi method an be frustrating, because you do a lot of inexplicable inter- mediate calculations and then the answer just pops out of an integral. However, it goes through divide-and-conquer recurrences like a Weed Wacker. Let\u2019s try one more example. Suppose that the following recurrence holds for all suffi- ciently large x: T (x) = T (x/3) + T (x/4) + x Here k = 2, a1 = 1, a2 = 1, b1 = 1/3, b2 = 1/4, and g(x) = x. Note that |g\u2032(x)| = 1 = O(1), so the Akra-Bazzi theorem applies. The next job is to compute p, which is defined by the equation: ( 1 3 )p + ( 1 4 )p = 1 We\u2019re in trouble: there is no closed-form expression for p. But at least we can say p < 1, and this turns out to be enough. Let\u2019s plow ahead and see why. The Akra-Bazzi theorem says: T (x) = \u398 ( xp ( 1 + \u222b x 1 u up+1 du )) = \u398 ( xp ( 1 + \u222b x 1 u\u2212p du )) = \u398 ( xp ( 1 + ( u1\u2212p 1\u2212 p \u2223\u2223\u2223\u2223x u=1 ))) = \u398 ( xp ( 1 + x1\u2212p \u2212 1 1\u2212 p )) = \u398 ( xp + x 1\u2212 p \u2212 xp 1\u2212 p ) = \u398(x) In the last step, we use the fact that xp = o(x) since p < 1; in other words, the term involving x dominates the terms involving xp, so we can ignore the latter. Overall, this calculation show that we don\u2019t need to know the exact value of p because it cancels out! In recitation we\u2019ll go over a slightly more general version of the Akra-Bazzi theorem. This generalization says that small changes in the sizes of subproblems do not affect the solution. This means that some apparent complications are actually irrelevant, which is nice. 158 Recurrences I Chapter 13 Recurrences II 13.1 Asymptotic Notation and Induction We\u2019ve seen that asymptotic notation is quite useful, particularly in connection with re- currences. And induction is our favorite proof technique. But mixing the two is risky business; there is great potential for subtle errors and false conclusions! False Claim 77. If T (1) = 1 T (n) = 2T (n/2) + n then T (n) = O(n). This claim is false; the Akra-Bazzi theorem implies that the correct solution is T (n) = \u398(n log n). But where does the following \u201cproof\u201d go astray? Proof. The proof is by strong induction. Let P (n) be the proposition that T (n) = O(n). Base case: P (1) is true because T (1) = 1 = O(1). Inductive step: For n \u2265 2 assume P (1), P (2), . . . P (n\u2212 1) to prove P (n). We have: T (n) = 2 · T (n/2) + n = 2 ·O(n/2) + n = O(n) The first equation is the recurrence, the second uses the assumption P (n/2), and the third is a simplification. Where\u2019s the bug? The proof is already far off the mark in the second sentence, which defines the induction hypothesis. The statement \u201cT (n) = O(n)\u201d is either true or false; its 160 Recurrences II validity does not depend on a particular value of n. Thus, the very idea of trying to prove that the statement holds for n = 0, 1, 2, . . . is wrong-headed. The safe way to reason inductively about asymptotic phenomena is to work directly with the definition of the notation. Let\u2019s try to prove the claim above in this way. Remember that f(n) = O(n) means that there exist constants n0 and c > 0 such that |f(n)| \u2264 cn for all n \u2265 n0. (Let\u2019s not worry about the absolute value for now.) If all goes well, the proof attempt should fail in some blatantly obvious way, instead of in a subtle, hard-to-detect way like the earlier argument. Since our perverse goal is to demonstrate that the proof won\u2019t work for any constants n0 and c, we\u2019ll leave these as variables and assume only that they\u2019re chosen so that the base case holds; that is, T (n0) \u2264 cn. Proof Attempt. We use strong induction. Let P (n) be the proposition that T (n) \u2264 cn. Base case: P (n0) is true, because T (n0) \u2264 cn. Inductive step: For n > n0, assume that P (n0), . . . , P (n\u2212 1) are true in order to prove P (n). We reason as follows: T (n) = 2T (n/2) + n \u2264 2c(n/2) + n = cn+ n = (c+ 1)n 6\u2264 cn The first equation is the recurrence. Then we use induction and simplify until the argu- ment collapses! 13.2 Linear Recurrences Last lecture we saw how to solve Divide and Conquer recurrences. In this lecture, we\u2019ll consider another family of recurrences, called \u201clinear recurrences\u201d, that also frequently arise in computer science and other disciplines. We\u2019ll first see how to solve a specific linear recurrence and then generalize our method to work for all linear recurrences. 13.2.1 Graduate Student Job Prospects In a new academic field (say computer science), there are only so many faculty positions available in all the universities of the world. Initially, there were not enough qualified candidates, and many positions were unfilled. But, over time, new graduates are filling the positions, making job prospects for later computer science students ever more bleak. Worse, the increasing number of professors are able to train an increasing number of graduate students, causing positions to fill ever more rapidly. Eventually, the universities will be saturated; new computer science graduates will have no chance at an academic Recurrences II 161 career. Our problem is to determine when the universities will stop hiring new computer science faculty and, in particular, to answer the question, \u201cAre the 6.042 TAs doomed?\u201d Here are the details of the problem. \u2022 There are a total of N faculty positions available worldwide. This number never changes due to budgetary constraints. \u2022 Congress has passed a law forbidding forced retirement in universities, and no one will retire voluntarily. (This is true and a problem!) In our analysis, therefore, once a faculty position is filled, it never opens up again. \u2022 Each year, every professor trains exactly 1 student who will go on to become a pro- fessor the following year. The only exception is that first year professors do not train students; they are too busy publishing, teaching, getting grants, and serving on committees. \u2022 In year 0, there are no computer science professors in the world. In year 1, the first professor is hired. 13.2.2 Finding a Recurrence Ideally, we could find a formula for the number of professors in the world in a given year. Then we could determine the year in which all N faculty positions are filled. Let f(n) be the number of professors during year n. To develop some intuition about the problem, we can compute values of this function for small n by hand. f(0) = 0 No CS professors; the dark ages. f(1) = 1 1 new professor; too busy to train a student. f(2)