Page 392 - Discrete Mathematics and Its Applications

5.4 Recursive Algorithms 371

i
17. Describe a recursive algorithm for multiplying two non- 38. Give a recursive algorithm for finding the string w , the
negative integers x and y based on the fact that xy = concatenation of i copies of w, when w is a bit string.
2(x · (y/2)) when y is even and xy = 2(x ·`y/2 ) + x 39. Prove that the recursive algorithm for finding the reversal
when y is odd, together with the initial condition xy = 0 of a bit string that you gave in Exercise 37 is correct.
when y = 0.
40. Prove that the recursive algorithm for finding the concate-
18. Prove thatAlgorithm 1 for computing n! when n is a non-
nation of i copies of a bit string that you gave in Exercise
negative integer is correct.
38 is correct.
19. Prove that Algorithm 3 for computing gcd(a, b) when a n n
∗ 41. Give a recursive algorithm for tiling a 2 × 2 checker-
and b are positive integers with a< b is correct.
board with one square missing using right triominoes.
20. Prove that the algorithm you devised in Exercise 17 is
correct. 42. Givearecursivealgorithmfortriangulatingasimplepoly-
gon with n sides, using Lemma 1 in Section 5.2.
21. Prove that the recursive algorithm that you found in Ex-
ercise 7 is correct. 43. Give a recursive algorithm for computing values of the
Ackermann function. [Hint: See the preamble to Exer-
22. Prove that the recursive algorithm that you found in Ex-
ercise 10 is correct. cise 48 in Section 5.3.]
2
23. Devise a recursive algorithm for computing n where n 44. Use a merge sort to sort 4, 3, 2, 5, 1, 8, 7, 6 into increasing
2 order. Show all the steps used by the algorithm.
is a nonnegative integer, using the fact that (n + 1) =
2
n + 2n + 1. Then prove that this algorithm is correct. 45. Use a merge sort to sort b, d, a, f, g,h,z,p,o, k into al-
n
2
24. Devise a recursive algorithm to find a , where a is a phabetic order. Show all the steps used by the algorithm.
real number and n is a positive integer. [Hint: Use the 46. How many comparisons are required to merge these pairs
n
2
2
equality a 2 n+1 = (a ) .] of lists using Algorithm 10?
25. How does the number of multiplications used by the al- a) 1, 3, 5, 7, 9; 2, 4, 6, 8, 10
gorithm in Exercise 24 compare to the number of multi- b) 1, 2, 3, 4, 5; 6, 7, 8, 9, 10
n
2
plications used by Algorithm 2 to evaluate a ? c) 1, 5, 6, 7, 8; 2, 3, 4, 9, 10
∗ 26. Use the algorithm in Exercise 24 to devise an algo- 47. Show that for all positive integers m and n there are sorted
n
rithm for evaluating a when n is a nonnegative integer. lists with m elements and n elements, respectively, such
[Hint: Use the binary expansion of n.] that Algorithm 10 uses m + n − 1 comparisons to merge
∗ 27. How does the number of multiplications used by the al- them into one sorted list.
gorithm in Exercise 26 compare to the number of multi- ∗ 48. What is the least number of comparisons needed to merge
n
plications used by Algorithm 2 to evaluate a ?
any two lists in increasing order into one list in increasing
28. How many additions are used by the recursive and itera- order when the number of elements in the two lists are
tive algorithms given in Algorithms 7 and 8, respectively, a) 1, 4? b) 2, 4? c) 3, 4? d) 4, 4?
to find the Fibonacci number f 7 ?
∗ 49. Prove that the merge sort algorithm is correct.
29. Devise a recursive algorithm to find the nth term of the se-
quence defined by a 0 = 1, a 1 = 2, and a n = a n−1 · a n−2 , The quick sort is an efficient algorithm. To sort
a 1 ,a 2 ,...,a n , this algorithm begins by taking the first
for n = 2, 3, 4,....
element a 1 and forming two sublists, the first contain-
30. Devise an iterative algorithm to find the nth term of the
ing those elements that are less than a 1 , in the order they
sequence defined in Exercise 29.
arise, and the second containing those elements greater
31. Is the recursive or the iterative algorithm for finding the than a 1 , in the order they arise. Then a 1 is put at the end
sequence in Exercise 29 more efficient? of the first sublist. This procedure is repeated recursively
32. Devise a recursive algorithm to find the nth term of for each sublist, until all sublists contain one item. The or-
the sequence defined by a 0 = 1, a 1 = 2, a 2 = 3, and dered list of n items is obtained by combining the sublists
a n = a n−1 + a n−2 + a n−3 , for n = 3, 4, 5,.... of one item in the order they occur.
33. Devise an iterative algorithm to find the nth term of the 50. Sort 3, 5, 7, 8, 1, 9, 2, 4, 6 using the quick sort.
sequence defined in Exercise 32.
51. Let a 1 ,a 2 ,...,a n be a list of n distinct real numbers.
34. Is the recursive or the iterative algorithm for finding the How many comparisons are needed to form two sublists
sequence in Exercise 32 more efficient?
from this list, the first containing elements less than a 1
35. Give iterative and recursive algorithms for finding the nth and the second containing elements greater than a 1 ?
term of the sequence defined by a 0 = 1, a 1 = 3, a 2 = 5,
and a n = a n−1 · a 2 · a 3 . Which is more efficient? 52. Describe the quick sort algorithm using pseudocode.
n−2 n−3
36. Give a recursive algorithm to find the number of parti- 53. What is the largest number of comparisons needed to or-
der a list of four elements using the quick sort algorithm?
tions of a positive integer based on the recursive definition
given in Exercise 47 in Section 5.3. 54. What is the least number of comparisons needed to order
37. Give a recursive algorithm for finding the reversal of a bit a list of four elements using the quick sort algorithm?
string. (See the definition of the reversal of a bit string in 55. Determine the worst-case complexity of the quick sort
the preamble of Exercise 34 in Section 5.3.) algorithm in terms of the number of comparisons used.