Page 589 - Discrete Mathematics and Its Applications

568 8 / Advanced Counting Techniques

exceed a fixed weight limit W. Let M(j, w) denote the 22. Find a recurrence relation that describes the number of
maximum total weight of the items in a subset of the comparisons used by the following algorithm: Find the
first j items such that this total weight does not exceed w. largest and second largest elements of a sequence of n
This problem is known as the knapsack problem. numbers recursively by splitting the sequence into two
a) Show that if w j > w, then M(j, w) = M(j − 1, w). subsequences with an equal number of terms, or where
b) Show that if w j ≤ w, then M(j, w) = there is one more term in one subsequence than in the
max(M(j − 1, w), w j + M(j − 1, w − w j )). other, at each stage. Stop when subsequences with two
c) Use (a) and (b) to construct a dynamic programming terms are reached.
algorithm for determining the maximum total weight 23. Give a big-O estimate for the number of comparisons
of items so that this total weight does not exceed W. used by the algorithm described in Exercise 22.
In your algorithm store the values M(j, w) as they are
found. 24. A sequence a 1 ,a 2 ,...,a n is unimodal if and only if
d) Explain how you can use the values M(j, w) com- there is an index m,1 ≤ m ≤ n, such that a i <a i+1
puted by the algorithm in part (c) to find a subset of when 1 ≤ i< m and a i >a i+1 when m ≤ i< n. That
items with maximum total weight not exceeding W. is, the terms of the sequence strictly increase until the
In Exercises 15–18 we develop a dynamic programming al- mth term and they strictly decrease after it, which implies
gorithm for finding a longest common subsequence of two that a m is the largest term. In this exercise, a m will al-
sequences a 1 ,a 2 ,...,a m and b 1 ,b 2 ,...,b n , an important ways denote the largest term of the unimodal sequence
problem in the comparison of DNA of different organisms. a 1 ,a 2 ,...,a n .
15. Suppose that c 1 ,c 2 ,...,c p is a longest common a) Show that a m is the unique term of the sequence that
subsequence of the sequences a 1 ,a 2 ,...,a m and is greater than both the term immediately preceding it
b 1 ,b 2 ,...,b n . and the term immediately following it.
a) Show that if a m = b n , then c p = a m = b n and b) Show that if a i <a i+1 where 1 ≤ i< n,
c 1 ,c 2 ,...,c p−1 is a longest common subsequence of then i + 1 ≤ m ≤ n.
a 1 ,a 2 ,...,a m−1 and b 1 ,b 2 ,...,b n−1 when p> 1. c) Show that if where 1 ≤ i< n,
b) Suppose that a m = b n . Show that if c p = a m , then 1 ≤ m ≤ i. a i >a i+1
then c 1 ,c 2 ,...,c p is a longest common subse-
quence of a 1 ,a 2 ,...,a m−1 and b 1 ,b 2 ,...,b n and d) Develop a divide-and-conquer algorithm for locat-
also show that if c p = b n , then c 1 ,c 2 ,...,c p is a ing the index m.[Hint: Suppose that i <m<j.
longest common subsequence of a 1 ,a 2 ,...,a m and Use parts (a), (b), and (c) to determine whether
b 1 ,b 2 ,...,b n−1 . (i+j)/2
+ 1 ≤ m ≤ n,1 ≤ m ≤ (i+j)/2
− 1,
or m = (i + j)/2
.]
16. Let L(i, j) denote the length of a longest com-
mon subsequence of a 1 ,a 2 ,...,a i and b 1 ,b 2 ,...,b j , 25. Show that the algorithm from Exercise 24 has worst-case
where 0 ≤ i ≤ m and 0 ≤ j ≤ n. Use parts (a) and (b) time complexity O(log n) in terms of the number of com-
of Exercise 15 to show that L(i, j) satisfies the recur- parisons.
rence relation L(i, j) = L(i − 1,j − 1) + 1 if both i Let {a n } be a sequence of real numbers. The forward dif-
and j are nonzero and a i = b i , and L(i, j) = ferences of this sequence are defined recursively as fol-
max(L(i, j − 1), L(i − 1,j)) if both i and j are nonzero lows: The first forward difference is a n = a n+1 − a n ; the
k
and a i = b i , and the initial condition L(i, j) = 0if i = 0 (k + 1)st forward difference k+1 a n is obtained from a n
k
k
or j = 0. by k+1 a n = a n+1 − a n .
17. Use Exercise 16 to construct a dynamic programming
26. Find a n , where
algorithm for computing the length of a longest com- 2
a) a n =3. b) a n =4n+7. c) a n =n +n+1.
mon subsequence of two sequences a 1 ,a 2 ,...,a m and 3
k
b 1 ,b 2 ,...,b n , storing the values of L(i, j) as they are 27. Let a n = 3n + n + 2. Find a n , where k equals
found. a) 2. b) 3. c) 4.
18. Develop an algorithm for finding a longest com- ∗ 28. Suppose that a n = P(n), where P is a polynomial of de-
mon subsequence of two sequences a 1 ,a 2 ,...,a m and gree d. Prove that d+1 a n = 0 for all nonnegative inte-
b 1 ,b 2 ,...,b n using the values L(i, j) found by the algo- gers n.
rithm in Exercise 17.
29. Let {a n } and {b n } be sequences of real numbers. Show
19. Find the solution to the recurrence relation f (n) = that
k
2
f (n/2) + n for n = 2 where k is a positive integer and
f(1) = 1. (a n b n ) = a n+1 ( b n ) + b n ( a n ).
20. Find the solution to the recurrence relation f (n) =
4
k
3f (n/5) + 2n , when n is divisible by 5, for n = 5 , 30. Show that if F(x) and G(x) are the generating func-
where k is a positive integer and f(1) = 1. tions for the sequences {a k } and {b k }, respectively,
21. Give a big-O estimate for the size of f in Exercise 20 and c and d are real numbers, then (cF + dG )(x) is the
if f is an increasing function. generating function for {ca k + db k }.