Chapter 3 Review
217
Find the average number of comparisons by adding the results from the table and dividing by n. (Hint: See
Practice 7 of Section 2.2—we told you that you should remember this!)
36. Find the average number of comparisons under the assumption that x is equally likely to be at any of the
n positions in the list or not in the list.
Exercises 37–40 concern a better upper bound for the number of divisions required by the Euclidean algorithm
in finding gcd(a, b). Assume that a and b are positive integers with a > b.
37. Suppose that m divisions are required to find gcd(a, b). Prove by induction that for m ≥ 1, it is true that
a ≥ F(m + 2) and b ≥ F(m + 1), where F(n) is the Fibonacci sequence. (Hint: To find gcd(a, b), after the
first division the algorithm computes gcd(b, r).)
38. Suppose that m divisions are required to find gcd(a, b), with m ≥ 4. Prove that
a
3
2
b
m+1
< F(m + 2) ≤ a
(Hint: Use the result of Exercise 37 here and Exercise 26 of Section 3.1.)
39. Suppose that m divisions are required to find gcd(a, b), with m ≥ 4. Prove that m < (log 1.5 a) − 1.
(Hint: Use the result of Exercise 38.)
40. a. Compute gcd(89, 55) and count the number of divisions required.
b. Compute the upper bound on the number of divisions required for gcd(89, 55) using Equation (1).
c. Compute the upper bound on the number of divisions required for gcd(89, 55) using the result of
Exercise 39.
d. The eighteenth-century French mathematician Gabriel Lamé proved that an upper bound on the number
of division done by the Euclidean algorithm to find gcd(a, b) where a > b is 5 times the number of
decimal digits in b. Compute the upper bound on the number of divisions required for gcd(89, 55) using
Lamé’s theorem.
c h a p t e r 3 Review
termInology
analysis of algorithms (p. 203)
Backus−Naur form (BNF)
(p. 163)
binary search algorithm (p. 169)
binary string (p. 163)
characteristic equation of a
recurrence relation (p.190)
closed−form solution (p. 180)
concatenation (p. 163)
constant coefficient recurrence
relation (p. 182)
divide-and-conquer algorithm
(p. 208)
divide-and-conquer recurrence
relation (p. 193)
empty string (p. 163)
Fibonacci sequence (p. 159)
first-order recurrence relation
(p. 182)
homogeneous recurrence relation
(p. 182)
index of summation (p. 182)
inductive definition (p. 158)
linear recurrence relation
(p. 182)
palindrome (p. 163)
recurrence relation (p. 159)
recursive definition (p. 158)
second-order recurrence relation
(p. 188)
selection sort algorithm (p. 168)
sequence (infinite sequence)
(p. 158)
sequential search algorithm
(p. 204)
solving a recurrence relation
(p. 180)
structural induction (p. 164)
summation notation (p. 182)
upper bound (p. 210)
217
Find the average number of comparisons by adding the results from the table and dividing by n. (Hint: See
Practice 7 of Section 2.2—we told you that you should remember this!)
36. Find the average number of comparisons under the assumption that x is equally likely to be at any of the
n positions in the list or not in the list.
Exercises 37–40 concern a better upper bound for the number of divisions required by the Euclidean algorithm
in finding gcd(a, b). Assume that a and b are positive integers with a > b.
37. Suppose that m divisions are required to find gcd(a, b). Prove by induction that for m ≥ 1, it is true that
a ≥ F(m + 2) and b ≥ F(m + 1), where F(n) is the Fibonacci sequence. (Hint: To find gcd(a, b), after the
first division the algorithm computes gcd(b, r).)
38. Suppose that m divisions are required to find gcd(a, b), with m ≥ 4. Prove that
a
3
2
b
m+1
< F(m + 2) ≤ a
(Hint: Use the result of Exercise 37 here and Exercise 26 of Section 3.1.)
39. Suppose that m divisions are required to find gcd(a, b), with m ≥ 4. Prove that m < (log 1.5 a) − 1.
(Hint: Use the result of Exercise 38.)
40. a. Compute gcd(89, 55) and count the number of divisions required.
b. Compute the upper bound on the number of divisions required for gcd(89, 55) using Equation (1).
c. Compute the upper bound on the number of divisions required for gcd(89, 55) using the result of
Exercise 39.
d. The eighteenth-century French mathematician Gabriel Lamé proved that an upper bound on the number
of division done by the Euclidean algorithm to find gcd(a, b) where a > b is 5 times the number of
decimal digits in b. Compute the upper bound on the number of divisions required for gcd(89, 55) using
Lamé’s theorem.
c h a p t e r 3 Review
termInology
analysis of algorithms (p. 203)
Backus−Naur form (BNF)
(p. 163)
binary search algorithm (p. 169)
binary string (p. 163)
characteristic equation of a
recurrence relation (p.190)
closed−form solution (p. 180)
concatenation (p. 163)
constant coefficient recurrence
relation (p. 182)
divide-and-conquer algorithm
(p. 208)
divide-and-conquer recurrence
relation (p. 193)
empty string (p. 163)
Fibonacci sequence (p. 159)
first-order recurrence relation
(p. 182)
homogeneous recurrence relation
(p. 182)
index of summation (p. 182)
inductive definition (p. 158)
linear recurrence relation
(p. 182)
palindrome (p. 163)
recurrence relation (p. 159)
recursive definition (p. 158)
second-order recurrence relation
(p. 188)
selection sort algorithm (p. 168)
sequence (infinite sequence)
(p. 158)
sequential search algorithm
(p. 204)
solving a recurrence relation
(p. 180)
structural induction (p. 164)
summation notation (p. 182)
upper bound (p. 210)