Discrete Mathematics for Computer Science

Divide-and-Conquer Recurrence Relations 577 Theorem 1. (Solution of Divide-and-Conquer Recurrences) The solution of T =CT(n/d)+f ...

578 CHAPTER 9 Recurrence Relations k Cj+I " f(dk+l/dJ+l) + f(dk+l) dk dkl) j=0 k+I L C' " f(dk+l/di) j=0 as required. Corollary ...

Exercises 579 mn .(3k+1 - 2 k+1) (n = 2 k) = 3m •3k - 2m .2k The following identity can be used to simplify this expression: 3k ...

580 CHAPTER 9 Recurrence Relations Solve these recurrences using back substitution. Verify the solutions are correct by inducti ...

Chapter Review 581 a power of d. The solution of this class of recurrence relations leads to a classification of divide-and-conq ...

582 CHAPTER 9 Recurrence Relations 9.12.2 Starting to Review For n = 0, 1, 2, and 3, show that Yn = 2 • 3' is a solution for yo ...

Chapter Review 53 9.12.4 Using Discrete Mathematics in Computer Science Find a recurrence relation for the sum of the first n n ...

584 CHAPTER 9 Recurrence Relations (a) Find a recurrence relation to describe the complexity of the recursive code for carrying ...

Chapter Review 585 (b) INPUT: n E N, the coefficients of P stored in a[0.. n], and a real number x0 OUTPUT: P(xo) Poly = a [0] f ...

586 CHAPTER 9 Recurrence Relations For the two versions of the sorting routine called INSORT, determine the complexity of the c ...

Languages and Regular Sets A particularly important application of finite sequences is languages. The words of a lan- guage are ...

588 APPENDIX A Languages and Regular Sets the set of words to be the set of all legal tokens of the language where a token in a ...

APPENDIX A Languages and Regular Sets 589 Definition 5. Let A and B be two sets of words: (a) AB={x.y:xEAandy iB} (b) A^0 = {A}, ...

590 APPENDIX A Languages and Regular Sets Definition 6 allows identifiers to be of any finite length. Although a compiler will n ...

Finite Automata A fundamental problem in computer science is to decide whether a word is in a language. For the case of regular ...

592 APPENDIX B Finite Automata 8(010, q2) = 3(10, B(0, q2)) = 6(10, qo) 8(10, q2) = 8(0, 8(1, qo)) = 8(0, qj) 8(0, ql) = q2 Sinc ...

Exercises 593 Draw the state diagram for the automata. Determine which of the following words are in the language: (a) 0011011 ( ...

594 APPENDIX B Finite Automata The standard way to describe the individual tokens ("words") of a computer language is with regu ...

Index G c O(F), 285 Ordering Three Values 1, 301 binary predicate, 135 P(n, r), 436 Ordering Three Values II, 302 binary functio ...

596 Index circuit, 341 congruent, 181 difference, 20 directed, 394 conjunction, 91 relative, 20 circular permutations, 439 conju ...