Page 251 - Discrete Mathematics and Its Applications

230 3 / Algorithms

3
a) Show that this algorithm uses O(n ) comparisons to a) log n b) 1000n c) n 2
compute the matrix M. d) 1000n 2 e) n 3 f) 2 n
3
b) Show that this algorithm uses (n ) comparisons to 2n 2 n
g) 2 h) 2
compute the matrix M. Using this fact and part (a),
3
conclude that the algorithms uses (n ) comparisons. 17. What is the largest n for which one can solve within
a minute using an algorithm that requires f (n) bit op-
[Hint: Only consider the cases where i ≤ n/4 and
erations, where each bit operation is carried out in
j ≥ 3n/4 in the two outer loops in the algorithm.] −12
10 seconds, with these functions f (n)?
13. The conventional algorithm for evaluating a polynomial 2
n
a n x + a n−1 x n−1 + ··· + a 1 x + a 0 at x = c can be ex- a) log log n b) log n c) (log n)
pressed in pseudocode by d) 1000000n e) n 2 f) 2 n
g) 2 n 2
procedure polynomial(c, a 0 ,a 1 ,...,a n : real numbers)
18. How much time does an algorithm take to solve a prob-
power := 1 2 n
lem of size n if this algorithm uses 2n + 2 operations,
y := a 0 each requiring 10 −9 seconds, with these values of n?
for i := 1 to n
a) 10 b) 20 c) 50 d) 100
power := power ∗ c
y := y + a i ∗ power 19. How much time does an algorithm using 2 50 operations
n
return y {y = a n c + a n−1 c n−1 + ··· + a 1 c + a 0 } need if each operation takes these amounts of time?
a) 10 −6 s b) 10 −9 s c) 10 −12 s
where the final value of y is the value of the polynomial
at x = c. 20. What is the effect in the time required to solve a prob-
2
a) Evaluate 3x + x + 1at x = 2 by working through lem when you double the size of the input from n to 2n,
assuming that the number of milliseconds the algorithm
eachstepofthealgorithmshowingthevaluesassigned
uses to solve the problem with input size n is each of these
at each assignment step.
function? [Express your answer in the simplest form pos-
b) Exactly how many multiplications and additions are
sible, either as a ratio or a difference. Your answer may
used to evaluate a polynomial of degree n at x = c?
be a function of n or a constant.]
(Do not count additions used to increment the loop
a) log log n b) log n c) 100n
variable.)
d) n log n e) n 2 f) n 3
14. There is a more efficient algorithm (in terms of the num-
ber of multiplications and additions used) for evaluating g) 2 n
polynomials than the conventional algorithm described 21. What is the effect in the time required to solve a problem
in the previous exercise. It is called Horner’s method. when you increase the size of the input from n to n + 1,
This pseudocode shows how to use this method to find the assuming that the number of milliseconds the algorithm
n
value of a n x + a n−1 x n−1 + ··· + a 1 x + a 0 at x = c. uses to solve the problem with input size n is each of these
function? [Express your answer in the simplest form pos-
procedure Horner(c, a 0 ,a 1 ,a 2 ,...,a n : real numbers) sible, either as a ratio or a difference. Your answer may
be a function of n or a constant.]
y := a n
for i := 1 to n a) log n b) 100n c) n 2
y := y ∗ c + a n−i d) n 3 e) 2 n f) 2 n 2
n
return y {y = a n c + a n−1 c n−1 + ··· + a 1 c + a 0 }
g) n!
2
a) Evaluate 3x + x + 1at x = 2 by working through 22. Determine the least number of comparisons, or best-case
eachstepofthealgorithmshowingthevaluesassigned performance,
at each assignment step.
a) required to find the maximum of a sequence of n in-
b) Exactly how many multiplications and additions are
tegers, using Algorithm 1 of Section 3.1.
used by this algorithm to evaluate a polynomial of
degree n at x = c? (Do not count additions used to b) used to locate an element in a list of n terms with a
increment the loop variable.) linear search.
15. What is the largest n for which one can solve within one c) used to locate an element in a list of n terms using a
second a problem using an algorithm that requires f (n) binary search.
bit operations, where each bit operation is carried out in 23. Analyze the average-case performance of the linear
10 −9 seconds, with these functions f (n)? search algorithm, if exactly half the time the element x is
a) log n b) n c) n log n not in the list and if x is in the list it is equally likely to
d) n 2 e) 2 n f) n! be in any position.
16. What is the largest n for which one can solve within a 24. An algorithm is called optimal for the solution of a prob-
day using an algorithm that requires f (n) bit operations, lem with respect to a specified operation if there is no
where each bit operation is carried out in 10 −11 seconds, algorithm for solving this problem using fewer opera-
with these functions f (n)? tions.