Chapter 3 Review
219
Now insert a counter in each version to indicate the
total number of addition operations done. Run each
version for various values of n and, on a single graph,
plot the number of additions as a function of n for each
version.
4. Input: Two positive integers a and b with a > b
Output: gcd(a, b) using
a. the iterative version of the Euclidean algorithm
b. a recursive version of the Euclidean algorithm
5. Input: Unsorted list of 10 integers
Output: Input list sorted in increasing order
Algorithm: Use the recursive selection sort of
Example 12.
6. Input: Sorted list of 10 integers and an integer x
Output: Message indicating whether x is in the list
Algorithm: Use the binary search algorithm of
Example 13.
7. Input: Text string, pattern string
Output: Location of beginning of pattern string in
text string, or a message that the pattern string is
not found within the text string
Algorithm: See Example 28.
8. The value (1 + "5)∙2, known as the golden ratio,
is related to the Fibonacci sequence by
lim
nS ∞
F(n + 1)
F(n)
=
1 + "5
2
Verify this limit by computing F(n + 1)/F(n) for
n = 10, 15, 25, 50, and 100 and comparing the
result with the golden ratio.
9. Compare the work done by sequential search and binary search on an ordered list of n entries by computing n and 1 + log n for values of n from 1 to 100.
Present the results in graphic form.
219
Now insert a counter in each version to indicate the
total number of addition operations done. Run each
version for various values of n and, on a single graph,
plot the number of additions as a function of n for each
version.
4. Input: Two positive integers a and b with a > b
Output: gcd(a, b) using
a. the iterative version of the Euclidean algorithm
b. a recursive version of the Euclidean algorithm
5. Input: Unsorted list of 10 integers
Output: Input list sorted in increasing order
Algorithm: Use the recursive selection sort of
Example 12.
6. Input: Sorted list of 10 integers and an integer x
Output: Message indicating whether x is in the list
Algorithm: Use the binary search algorithm of
Example 13.
7. Input: Text string, pattern string
Output: Location of beginning of pattern string in
text string, or a message that the pattern string is
not found within the text string
Algorithm: See Example 28.
8. The value (1 + "5)∙2, known as the golden ratio,
is related to the Fibonacci sequence by
lim
nS ∞
F(n + 1)
F(n)
=
1 + "5
2
Verify this limit by computing F(n + 1)/F(n) for
n = 10, 15, 25, 50, and 100 and comparing the
result with the golden ratio.
9. Compare the work done by sequential search and binary search on an ordered list of n entries by computing n and 1 + log n for values of n from 1 to 100.
Present the results in graphic form.