Chapter 8: Q2E (page 535)
How many comparisons are needed to locate the maximum and minimum elements in a sequence with 128 elements using the algorithm in Example 2?
Thus, the number of comparisons required is 254.
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
(a) Set up a divide-and-conquer recurrence relation for the number of multiplications required to compute, where is a real number and is a positive integer, using the recursive algorithm from Exercise 26 in Section 5.4.
b) Use the recurrence relation you found in part (a) to construct a big- estimate for the number of multiplications used to compute using the recursive algorithm.
Give a big- estimate for the function in Exerciseifis an increasing function.
Suppose that the votes of people for different candidates (where there can be more than two candidates) for a particular office are the elements of a sequence. A person wins the election if this person receives a majority of the votes.
a) Devise a divide-and-conquer algorithm that determines whether a candidate received a majority and, if so, determine who this candidate is. [Hint: Assume that is even and split the sequence of votes into two sequences, each with elements. Note that a candidate could not have received a majority of votes without receiving a majority of votes in at least one of the two halves.]
b) Use the master theorem to give a big-estimate for the number of comparisons needed by the algorithm you devised in part (a).
Suppose that the function \(f\) satisfies the recurrence relation \(f(n) = 2f(\sqrt n ) + 1\) whenever \(n\) is a perfect square greater than\(1\)and\(f(2) = 1\).
a) Find\(f(16)\).
b) Give a big- \(O\) estimate for\(f(n)\). (Hint: Make the substitution\(m = \log n\)).
Find the coefficient of \({x^9}\) in the power series of each of these functions.
a) \({\left( {1 + {x^3} + {x^6} + {x^9} + \cdots } \right)^3}\)
b) \({\left( {{x^2} + {x^3} + {x^4} + {x^5} + {x^6} + \cdots } \right)^3}\)
c) \(\left( {{x^3} + {x^5} + {x^6}} \right)\left( {{x^3} + {x^4}} \right)\left( {x + {x^2} + {x^3} + {x^4} + \cdots } \right)\)
d) \(\left( {x + {x^4} + {x^7} + {x^{10}} + \cdots } \right)\left( {{x^2} + {x^4} + {x^6} + {x^8} + } \right.\)\( \cdots )\)
e) \({\left( {1 + x + {x^2}} \right)^3}\)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
