Page 534 - Discrete Mathematics and Its Applications

8.1 Applications of Recurrence Relations 513

such that n does not exceed t k = k(k + 1)/2, the kth triangu- ∗ 53. Construct the algorithm described in the text after Algo-
lar number, that is, t k−1 <n ≤ t k . The unsettled conjecture, rithm 1 for determining which talks should be scheduled
known as Frame’s conjecture, is that this algorithm uses the to maximize the total number of attendees and not just
fewest number of moves required to solve the puzzle, no mat- the maximum total number of attendees determined by
ter how the disks are moved. Algorithm 1.
38. ShowthattheReve’spuzzlewiththreediskscanbesolved 54. Use Algorithm 1 to determine the maximum number of
using five, and no fewer, moves. total attendees in the talks in Example 6 if w i , the number
of attendees of talk i, i = 1, 2,..., 7, is
39. Show that the Reve’s puzzle with four disks can be solved a) 20, 10, 50, 30, 15, 25, 40.
using nine, and no fewer, moves.
b) 100, 5, 10, 20, 25, 40, 30.
40. Describe the moves made by the Frame–Stewart al- c) 2, 3, 8, 5, 4, 7, 10.
gorithm, with k chosen so that the fewest moves are d) 10, 8, 7, 25, 20, 30, 5.
required, for
55. For each part of Exercise 54, use your algorithm from
a) 5 disks. b) 6 disks. c) 7 disks. d) 8 disks. Exercise 53 to find the optimal schedule for talks so that
∗ 41. Show that if R(n) is the number of moves used by the total number of attendees is maximized.
the Frame–Stewart algorithm to solve the Reve’s puzzle 56. In this exercise we will develop a dynamic program-
with n disks, where k is chosen to be the smallest integer ming algorithm for finding the maximum sum of con-
with n ≤ k(k + 1)/2, then R(n) satisfies the recurrence secutive terms of a sequence of real numbers. That
k
relation R(n) = 2R(n − k) + 2 − 1, with R(0) = 0 is, given a sequence of real numbers a 1 ,a 2 ,...,a n ,
and R(1) = 1. k
the algorithm computes the maximum sum i=j a i
∗ 42. Show that if k is as chosen in Exercise 41, then where 1 ≤ j ≤ k ≤ n.
R(n) − R(n − 1) = 2 k−1 . a) Show that if all terms of the sequence are nonnegative,
this problem is solved by taking the sum of all terms.
∗ 43. Show that if k is as chosen in Exercise 41, then
k i−1 k−1 Then, give an example where the maximum sum of
R(n) = i2 − (t k − n)2 .
i = 1 consecutive terms is not the sum of all terms.
∗ 44. Use Exercise 43 to give an upper bound on the num- b) Let M(k) be the maximum of the sums of consecutive
ber of moves required to solve the Reve’s puzzle for all terms of the sequence ending at a k . That is, M(k) =
integers n with 1 ≤ n ≤ 25. k a i . Explain why the recurrence rela-
max 1≤j≤k
i=j
√ √ tion M(k) = max(M(k − 1) + a k ,a k ) holds for k =
∗ 45. Show that R(n) is O( n2 2n ).
2, ..., n.
Let {a n } be a sequence of real numbers. The backward dif- c) Use part (b) to develop a dynamic programming algo-
ferences of this sequence are defined recursively as shown rithm for solving this problem.
next. The first difference ∇a n is
d) Show each step your algorithm from part (c) uses to
∇a n = a n − a n−1 . find the maximum sum of consecutive terms of the
sequence 2, −3, 4, 1, −2, 3.
k+1 k
The (k + 1)st difference ∇ a n is obtained from ∇ a n by e) Show that the worst-case complexity in terms of the
number of additions and comparisons of your algo-
k+1 k k
∇ a n =∇ a n −∅ a n−1 . rithm from part (c) is linear.
∗ 57. Dynamic programming can be used to develop
46. Find ∇a n for the sequence {a n }, where
an algorithm for solving the matrix-chain multi-
a) a n = 4. b) a n = 2n. plication problem introduced in Section 3.3. This
n
2
c) a n = n . d) a n = 2 . is the problem of determining how the product
2
47. Find ∇ a n for the sequences in Exercise 46. A 1 A 2 ··· A n can be computed using the fewest
integer multiplications, where A 1 , A 2 ,..., A n are
48. Show that a n−1 = a n −∅ a n . m 1 × m 2 ,m 2 × m 3 ,...,m n × m n+1 matrices, respec-
2
49. Show that a n−2 = a n − 2∇a n +∇ a n . tively, and each matrix has integer entries. Recall that
by the associative law, the product does not depend on
∗ 50. Prove that a n−k can be expressed in terms of a n , ∇a n , the order in which the matrices are multiplied.
k
2
∇ a n ,..., ∇ a n . a) Show that the brute-force method of determining the
minimum number of integer multiplications needed to
51. Express the recurrence relation a n = a n−1 + a n−2 in
2
terms of a n , ∇a n , and ∇ a n . solve a matrix-chain multiplication problem has expo-
nential worst-case complexity. [Hint: Do this by first
52. Show that any recurrence relation for the sequence {a n } showing that the order of multiplication of matrices
2
can be written in terms of a n , ∇a n , ∇ a n ,.... The result- is specified by parenthesizing the product. Then, use
ing equation involving the sequences and its differences Example 5 and the result of part (c) of Exercise 41 in
is called a difference equation. Section 8.4.]