Discrete Mathematics for Computer Science

Chapter Review 581

a power of d. The solution of this class of recurrence relations leads to a classification of

divide-and-conquer recurrence relations.

The algorithm for the Tower of Hanoi problem exemplifies first-order recurrence re-

lations. The Fibonacci sequence recurrence relation exemplifies second-order recurrence

relations. The different types of divide-and-conquer recurrence relations are exemplified

by binary search, merge sort, and n-bit multiplication.

9.12.1 Terms, Theorems, Algorithms

9.1-9.3 Summary

TERMS

back substitution matrix multiplication

boundary value nonhomogeneous

first order solution

first-order recurrence relation Tower of Hanoi

initial value

ALGORITHMS

Iterative Bubble Sort Selection Sort

Recursive Bubble Sort Tower of Hanoi

THEOREM

Solution of First-Order Recurrence Relations

9.4 Summary

TERMS

boundary values particular solution
characteristic equation second order
Fibonacci sequence second-order recurrence relation
homogeneous trivial solution
initial values

THEOREM

Solution of Second-Order Recurrence Relations

9.6-9.10 Summary

TERMS

divide and conquer multiplication of n-bit numbers
divide-and-conquer relation

ALGORITHM

Binary Search
Merge Sort

THEOREMS

Master Theorem
Solution of Divide-and-Conquer Recurrences