218
Recursion, Recurrence Relations, and Analysis of Algorithms
SelF-teSt
Answer the following true-false questions without looking back in the chapter.
Section 3.1
1. A sequence defined by
S(l) = 7
S(n) = 3S(n − 1) + 2 for n ≥ 2
contains the number 215.
2. A collection T of numbers is defined recursively by
1. 6 and 8 belong to T
2. If X and Y belong to T, so does X + 2Y
Every even number ≥ 18 belongs to T.
3. Recursive algorithms are valuable primarily because
they run more efficiently than iterative algorithms.
4. In the recursive algorithm SelectionSort, changing
one line of the algorithm to
“find the index i of the minimum item in L
between 1 and j ”
sorts the list L in decreasing order.
5. In applying the binary search algorithm to the list
2, 5, 7, 10, 14, 20
where x = 8 is the target item, x is never compared
to 5.
Section 3.2
1. A closed-form solution to a recurrence relation is
obtained by applying mathematical induction to the
recurrence relation.
o n t h e c o m p u t e r
For Exercises 1–7, write a computer program that
produces the desired output from the given input.
1. Input: Binary string
Output: Message indicating whether the input
string is a palindrome (see Practice 7)
Algorithm: Use recursion.
2. Input: String of characters x and a positive integer n
Output: Concatenation of n copies of x
Algorithm: Use recursion.
(Some programming languages provide builtin string manipulation capabilities, such as
concatenation.)
3. Input: Positive integer n
Output: nth value in the Fibonacci sequence using
a. iteration.
b. recursion.
2. S(n) = 2S(n − 1) + 3S(n − 2) + 5n is a linear,
first-order recurrence relation with constant
c oefficients.
3. S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i) is a closed-form
solution to any linear first-order recurrence relation
with constant coefficients.
4. The solution to the recurrence relation S(n) =
c 1 S(n − 1) + c 2 S(n − 2) involves solving the characteristic equation t
2
− c 1 t − c 2 = 0.
5. Divide-and-conquer algorithms lead to recurrence
relations that are not first-order.
Section 3.3
1. Analysis of an algorithm generally finds the amount
of work done in the worst case because it is too
difficult to analyze an average case.
2. In the worst case, the string pattern-matching
algorithm requires n + m comparisons, where
n = the text size and m = the pattern size.
3. Binary search is more efficient than sequential
search on a sorted list of more than three elements.
4. The recursive version of the sequential search
algorithm is a divide-and-conquer algorithm.
5. An upper bound for the Euclidean algorithm gives
a ceiling on the number of divisions required to find
gcd(a, b).
Recursion, Recurrence Relations, and Analysis of Algorithms
SelF-teSt
Answer the following true-false questions without looking back in the chapter.
Section 3.1
1. A sequence defined by
S(l) = 7
S(n) = 3S(n − 1) + 2 for n ≥ 2
contains the number 215.
2. A collection T of numbers is defined recursively by
1. 6 and 8 belong to T
2. If X and Y belong to T, so does X + 2Y
Every even number ≥ 18 belongs to T.
3. Recursive algorithms are valuable primarily because
they run more efficiently than iterative algorithms.
4. In the recursive algorithm SelectionSort, changing
one line of the algorithm to
“find the index i of the minimum item in L
between 1 and j ”
sorts the list L in decreasing order.
5. In applying the binary search algorithm to the list
2, 5, 7, 10, 14, 20
where x = 8 is the target item, x is never compared
to 5.
Section 3.2
1. A closed-form solution to a recurrence relation is
obtained by applying mathematical induction to the
recurrence relation.
o n t h e c o m p u t e r
For Exercises 1–7, write a computer program that
produces the desired output from the given input.
1. Input: Binary string
Output: Message indicating whether the input
string is a palindrome (see Practice 7)
Algorithm: Use recursion.
2. Input: String of characters x and a positive integer n
Output: Concatenation of n copies of x
Algorithm: Use recursion.
(Some programming languages provide builtin string manipulation capabilities, such as
concatenation.)
3. Input: Positive integer n
Output: nth value in the Fibonacci sequence using
a. iteration.
b. recursion.
2. S(n) = 2S(n − 1) + 3S(n − 2) + 5n is a linear,
first-order recurrence relation with constant
c oefficients.
3. S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i) is a closed-form
solution to any linear first-order recurrence relation
with constant coefficients.
4. The solution to the recurrence relation S(n) =
c 1 S(n − 1) + c 2 S(n − 2) involves solving the characteristic equation t
2
− c 1 t − c 2 = 0.
5. Divide-and-conquer algorithms lead to recurrence
relations that are not first-order.
Section 3.3
1. Analysis of an algorithm generally finds the amount
of work done in the worst case because it is too
difficult to analyze an average case.
2. In the worst case, the string pattern-matching
algorithm requires n + m comparisons, where
n = the text size and m = the pattern size.
3. Binary search is more efficient than sequential
search on a sorted list of more than three elements.
4. The recursive version of the sequential search
algorithm is a divide-and-conquer algorithm.
5. An upper bound for the Euclidean algorithm gives
a ceiling on the number of divisions required to find
gcd(a, b).