Discrete Mathematics for Computer Science

568 CHAPTER 9 Recurrence Relations

10. How many ways can an athlete run up a set of stairs if either one or two steps are taken
    at a time?

11. Let f(n) be the number of strings of n symbols formed using the symbols 0, 1, and

2 such that no two consecutive 0's occur. Show that f(n) = 2f(n - 1) + 2f(n - 2).

Solve the recurrence, and enumerate all such strings of length four.

rnDivide and Conquer Paradigm

One aspect of the study of algorithms is to recognize how algorithms designed to solve

quite different problems are actually similar. One effective strategy for algorithm design,

called divide and conquer, suggests splitting a problem of size n (number of inputs or size

of input) into a number of instances of the same problem but each of a smaller size. The

strategy then proposes solving the smaller problems separately before putting the solutions

of the smaller problems together to solve the original problem. We will show how the

divide-and-conquer strategy is used to develop effective algorithms for searching, sorting,

and multiplying "large" integer values.

Suppose the solution of the original problem of size n can be found by solving a num-

ber of subproblems of size n/d for some d. There are three types of divide-and-conquer

algorithms. The first solves fewer than d subproblems of size n/d to solve the original

problem. An algorithm of this type is the binary search algorithm. The second solves d

subproblems of size n/d to solve the original problem. An algorithm of this type is the

merge sort algorithm. The third solves more than d subproblems of size n/d to solve the

original problem. An algorithm of this type is the extended precision multiplication algo-

rithm for integers. A general recurrence relation by which all these algorithms have their

complexity represented will be solved, and this solution will be interpreted in terms of the

algorithms that are presented. Finally, the complexity of each type of divide-and-conquer

algorithm will be determined.

Binary Search

When searching for an element in a set of elements from a linearly ordered set, the proce-

dure of examining each of the elements one at a time could be used. This procedure may

require that every element be examined before the search can conclude. If the application

involves repeating this search procedure many times on a large set of elements, then it

becomes very time-consuming. To reduce the time needed to search for a single element,

a divide-and-conquer approach can be used provided the set has its elements stored in

sorted order. Proceed by dividing the sorted set into two equal-or almost equal-parts.

Let one part contain all the elements less than the middle element of the set stored in or-

der; let the other part contain all the elements greater than or equal to the middle element,

also stored in order. Determine which part can possibly contain the element sought by

comparing it to the middle element of the set. The part of the set that cannot contain the

element sought is then eliminated from further consideration. The procedure is repeated

on the set of elements that can still possibly contain the element being sought. This set