Page 556 - Discrete Mathematics and Its Applications

8.3 Divide-and-Conquer Algorithms and Recurrence Relations 535

Exercises

1. How many comparisons are needed for a binary search that n is even and split the sequence of votes into
in a set of 64 elements? two sequences, each with n/2 elements. Note that a
candidate could not have received a majority of votes
2. How many comparisons are needed to locate the max- without receiving a majority of votes in at least one
imum and minimum elements in a sequence with 128 of the two halves.]
elements using the algorithm in Example 2?
b) Use the master theorem to give a big-O estimate for
3. Multiply (1110) 2 and (1010) 2 using the fast multiplica- the number of comparisons needed by the algorithm
tion algorithm. you devised in part (a).
4. Express the fast multiplication algorithm in pseudocode. 18. Suppose that each person in a group of n people votes for
exactly two people from a slate of candidates to fill two
5. Determine a value for the constant C in Example 4 and positions on a committee. The top two finishers both win
use it to estimate the number of bit operations needed to positions as long as each receives more than n/2 votes.
multiply two 64-bit integers using the fast multiplication
algorithm. a) Devise a divide-and-conquer algorithm that deter-
mines whether the two candidates who received the
6. How many operations are needed to multiply two 32 × 32 most votes each received at least n/2 votes and, if so,
matrices using the algorithm referred to in Example 5? determine who these two candidates are.
7. Suppose that f (n) = f (n/3) + 1 when n is a positive b) Use the master theorem to give a big-O estimate for
integer divisible by 3, and f(1) = 1. Find the number of comparisons needed by the algorithm
a) f(3). b) f(27). c) f(729). you devised in part (a).
8. Suppose that f (n) = 2f (n/2) + 3whenn is aneven pos- 19. a) Set up a divide-and-conquer recurrence relation
itive integer, and f(1) = 5. Find for the number of multiplications required to
n
compute x , where x is a real number and n is a
a) f(2). b) f(8). c) f(64). d) f(1024). positive integer, using the recursive algorithm from
2
9. Suppose that f (n) = f (n/5) + 3n when n is a positive Exercise 26 in Section 5.4.
integer divisible by 5, and f(1) = 4. Find
b) Use the recurrence relation you found in part (a) to
a) f(5). b) f(125). c) f(3125). construct a big-O estimate for the number of mul-
k
10. Find f (n) when n = 2 , where f satisfies the recurrence tiplications used to compute x using the recursive
n
relation f (n) = f (n/2) + 1 with f(1) = 1. algorithm.
11. Give a big-O estimate for the function f in Exercise 10 20. a) Set up a divide-and-conquer recurrence relation for
if f is an increasing function. the number of modular multiplications required to
n
k
12. Find f (n) when n = 3 , where f satisfies the recurrence compute a mod m, where a, m, and n are pos-
relation f (n) = 2f (n/3) + 4 with f(1) = 1. itive integers, using the recursive algorithms from
Example 4 in Section 5.4.
13. Give a big-O estimate for the function f in Exercise 12 b) Use the recurrence relation you found in part (a) to
if f is an increasing function.
construct a big-O estimate for the number of modular
k
n
14. Suppose that there are n = 2 teams in an elimination multiplications used to compute a mod m using the
tournament, where there are n/2 games in the first round, recursive algorithm.
with the n/2 = 2 k−1 winners playing in the second round, 21. Suppose that the function f satisfies the recurrence rela-
and so on. Develop a recurrence relation for the number tion f (n) = 2f( n) + 1 whenever n is a perfect square
√
of rounds in the tournament.
greater than 1 and f(2) = 1.
15. How many rounds are in the elimination tournament de- a) Find f(16).
scribed in Exercise 14 when there are 32 teams?
b) Give a big-O estimate for f (n).[Hint: Make the sub-
16. Solve the recurrence relation for the number of rounds in stitution m = log n.]
the tournament described in Exercise 14. 22. Suppose that the function f satisfies the recurrence re-
√
lation f (n) = 2f( n) + log n whenever n is a perfect
17. Suppose that the votes of n people for different candi-
dates (where there can be more than two candidates) for square greater than 1 and f(2) = 1.
a particular office are the elements of a sequence. A per- a) Find f(16).
son wins the election if this person receives a majority of b) Find a big-O estimate for f (n).[Hint: Make the sub-
the votes. stitution m = log n.]
a) Devise a divide-and-conquer algorithm that deter- ∗∗ 23. This exercise deals with the problem of finding the largest
mines whether a candidate received a majority and, sum of consecutive terms of a sequence of n real numbers.
if so, determine who this candidate is. [Hint: Assume When all terms are positive, the sum of all terms provides