Mathematics for Computer Science
21.2. Merge Sort 873 On the second line, we grouped thenterms and powers of 2. On the third, we collapsed the geometric sum. Ste ...
Chapter 21 Recurrences874 21.3 Linear Recurrences So far we’ve solved recurrences with two techniques: guess-and-verify and plug ...
21.3. Linear Recurrences 875 This is the Fibonacci recurrence, the most famous of all recurrence equations. Fibonacci numbers ar ...
Chapter 21 Recurrences876 This suggests that there are at least two different solutions to the recurrence, ne- glecting the boun ...
21.3. Linear Recurrences 877 Similarly, the second boundary condition implies that f.1/Ds 1 C p 5 2 ! 1 Ct 1 p 5 2 ! 1 D1: Now ...
Chapter 21 Recurrences878 21.3.2 Solving Homogeneous Linear Recurrences The method we used to solve the Fibonacci recurrence can ...
21.3. Linear Recurrences 879 f.0/ D 0 ,f.1/D 1 ,f.2/ D 4 , andf.3/ D 9. Then we would obtain four equations in four unknowns: f. ...
Chapter 21 Recurrences880 Add the homogeneous and particular solutions together to obtain thegeneral solution. Now use the boun ...
21.4. Divide-and-Conquer Recurrences 881 Therefore, the functionf.n/D 2 2 nn 2 solves this variant of the Towers of Hanoi recu ...
Chapter 21 Recurrences882 Short Guide to Solving Linear Recurrences A linear recurrence is an equation f.n/Da 1 f.n1/Ca 2 f.n2/C ...
21.4. Divide-and-Conquer Recurrences 883 Merge Sort is an example of a divide-and-conquer algorithm: it divides the in- put, “co ...
Chapter 21 Recurrences884 Looks likepD 1 does the job. Then we compute the integral: T.n/D‚ n 1 C Zn 1 u 1 u^2 du D‚ n ...
21.4. Divide-and-Conquer Recurrences 885 This is the typical situation: the asymptotic solution to a divide-and-conquer recurren ...
Chapter 21 Recurrences886 where: 1.x 0 is large enough so thatTis well-defined, 2.a 1 ;:::;akare positive constants, 3.b 1 ;:::; ...
21.4. Divide-and-Conquer Recurrences 887 h 2 .x/are both at most 1, which is easilyO.x=log^2 x/as required by the theorem statem ...
Chapter 21 Recurrences888 21.5 A Feel for Recurrences We’ve guessed and verified, plugged and chugged, found roots, computed int ...
21.5. A Feel for Recurrences 889 Divide-and-conquer recurrences are also sensitive to the number of subproblems. For example, fo ...
Chapter 21 Recurrences890 constantn. State the value ofpyou get for each recurrence (which can be left in the form of logs). Als ...
21.5. A Feel for Recurrences 891 The final, merged list is the output. What’s great is that because multiple copies of each numb ...
Chapter 21 Recurrences892 week initiate one new member each. On week 0 there is one devil-worshiper. There are two devil-worship ...
«
37
38
39
40
41
42
43
44
45
46
»
Free download pdf