Discrete Mathematics for Computer Science

Solving First-Order Recurrence Relations 557 Proof In the general formula, let c = 1 and k = 0. 0 Corollary 2. The solution of T ...

558 CHAPTER 9 Recurrence Relations rn Exercises Solve T(n) = T(n- 1) +n forn > I with T(0) = 2. Solve T(n) = T(n - 1) + n fo ...

Exercises 559 that describes the complexity of the procedure by counting the number of comparisons made between pairs of element ...

560 CHAPTER 9 Recurrence Relations Algortm Seeto Sor INPUT: A list of distinct values List[]. List[N] OUTPUT: List[l],.... List[ ...

Fibonacci Recurrence Relation 561 (a) Use the algorithm described to find the matrix product for ( ) (;2) (b) For matrices of si ...

562 CHAPTER 9 Recurrence Relations values one at a time, starting with F 2 .As an example, F 5 may be calculated using this proc ...

Fibonacci Recurrence Relation 563 possibility can be determined. For example, it may be possible to determine whether such a fun ...

564 CHAPTER 9 Recurrence Relations Since both cl and c2 are roots of the characteristic equation of the recurrence c2- kC - k2 = ...

Fibonacci Recurrence Relation 565 1F,/5=A -I-B-) Fo =1 =A + B ( 2 F, I A (± 2 v) +B (1 2 5) 1I=A+tB 1 A+ B 2 2 The solution of t ...

566 CHAPTER 9 Recurrence Relations For small values of n, it often is much easier to use the recurrence relation directly to cal ...

Exercises 567 Solution. Form the characteristic equation and then factor it: c - 6c - 7 = 0 c =7, -1 Form the general solution o ...

568 CHAPTER 9 Recurrence Relations How many ways can an athlete run up a set of stairs if either one or two steps are taken at ...

Binary Search 569 of elements is about half the size of the previously examined set. The process of dividing the set in half and ...

570 CHAPTER 9 Recurrence Relations Figure 9.4 represents the execution of BinSrch in looking for 9 in the set {1, 2, 4, 6, 9, 13 ...

Merge Sort 571 rnMerge Sort Sorting algorithms not only are studied in a variety of computer science courses but also are used a ...

572 CHAPTER 9 Recurrence Relations 9.8.2 Example Figure 9.5 shows the algorithm applied to an array with eight elements. The rec ...

Multiplication of n-Bit Numbers 573 W Multiplication of n-Bit Numbers Because the design of a computer includes a decision about ...

574 CHAPTER 9 Recurrence Relations The term 4T (n/2) accounts for the n/2-digit multiplications while m I -n accounts for the ad ...

Multiplication of n-Bit Numbers 575 where m2 is a constant and n = 2 k. The term m2 • n represents the additions, subtractions, ...

576 CHAPTER 9 Recurrence Relations Divide-and-Conquer Recurrence Relations To focus attention on the kinds of recurrence relatio ...