Сlass on Design and Analysis of Algorithms, Solutions to Problem Set 2

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas, and Nancy Lynch February 19, 2015 6.046J/18.410J Problem Set 2 Solutions Problem Set 2 Solutions This problem set is due at 11:59pm on Thursday, February 19, 2015. Exercise 2-1. Read CLRS, Sections 30.1 and 30.2. Exercise 2-2. Exercise 30-2.3. Exercise 2-3. Exercise 30-2.4. Exercise 2-4. Read CLRS, Chapter 18. Exercise 2-5. Exercise 18.2-5 Exercise 2-6. Exercise 18.3-2 Problem 2-1. Pattern Matching [25 points] Suppose you are given a source string S[0 . . n − 1] of length n, consisting of symbols a and b. Suppose further that you are given a pattern string P [0 . . m − 1] of length m « n, consisting of symbols a, b, and ∗, representing a pattern to be found in string S. The symbol ∗ is a “wild card” symbol, which matches a single symbol, either a or b. The other symbols must match exactly. The problem is to output a sorted list M of valid “match positions”, which are positions j in S such that pattern P matches the substring S[j . . j + |P | − 1]. For example, if S = a b a b b a b and P = a b ∗, then the output M should be [0, 2]. (a) [4 points] Describe a straightforward, naı̈ve algorithm to solve the problem. Your algorithm should run in time O(nm). Solution: One can explicitly check every possible starting position s ∈ {0, 1, . . . , n− m} by checking whether each entry in P matches from s to s + m − 1. NAIVE -A LGORITHM(S, P ) 1 M = [] 2 for s = 0 to n − m 3 valid = TRUE 4 for j = 0 to m − 1 5 if P [j] = ∗ and P [j] = S[s + j] 6 valid = FALSE 7 if valid 8 M. APPEND(s) 9 return M 2 Problem Set 2 Solutions (b) [12 points] Give an algorithm to solve the problem by reducing it to the problem of polynomial multiplication. Specifically, describe how to convert strings S and P into polynomials such that the product of the polynomials allows you to determine the answer M . Give examples to illustrate your polynomial representation of the inputs and your way of determining outputs from the product, based on the example S and P strings given above. Solution: Let’s represent a by 1, b by −1, and ∗ by 0. We will use these representa­ tions instead of the original symbols in this solution. Notice that P matches S starting from position j, 0 ≤ j ≤ n − m, if and only if for every i, 0 ≤ i ≤ m − 1, either P [i] = 0 or S[j + i]P [i] = 1. This is true if and only if m−1 m S[j + i]P [i] = k, i=0 where k is the number of non-∗ symbols in P . We would like to express these summations as coefficients of a product of polynomi­ als. Let x be a variable. Represent S as fS (x) = S[0] + S[1]x + · · · + S[n − 1]xn−1 . Represent P as fP (x) = Q[0] + Q[1]x + · · · + Q[m − 1]xm−1 , where each Q[i] = P [m − 1 − i]. Thus, we have reversed the order of the coefficients in this last representation. Suppose C is the product of the S polynomial and the P polynomial. Then the coeffi­ cient of xm−1+j in C is m −1 m S[m − 1 + j − i]Q[i], i=0 which is equal to m −1 m S[i + j]P [i]. i=0 This is the same as the sum above. To obtain the output M , we simply examine all the coefficients of C, outputting position number j, 0 ≤ j ≤ n − m, exactly if the coefficient of xm−1+j is equal to k, the total number of non-∗ symbols in P . We output these in order of increasing j, as required. In the example above, S is represented by fS (x) = 1 − x + x2 − x3 − x4 + x5 − x6 Problem Set 2 Solutions 3 and P by fP (x) = −x + x2 . The product C is −x + 2x2 − 2x3 + 2x4 − 2x6 + 2x7 − x8 . The number k is equal to 2, so the terms of interest are 2x2 , 2x4 , and 2x7 . These would yield j = 0, 2, 5, but 5 is ruled out because we are only considering j ≤ n − m = 7 − 3 = 4. (c) [3 points] Suppose you combine your solution to Part (b) with an FFT algorithm for polynomial multiplication, as presented in Lecture 3. What is the time complexity of the resulting solution to the string matching problem? Solution: It’s O(n lg n). It takes time O(n lg n) to perform the needed DFT and inverse DFT algorithms, and O(n) for producing inputs for the DFT algorithm and extracting M from the outputs. (d) [6 points] Now consider the same problem but with a larger symbol alphabet. Specif­ ically, suppose you are given a representation of a DNA strand as a string D[0 . . n − 1] of length n, consisting of symbols A, C, G, and T ; and you are given a pattern string P [0 . . m − 1] of length m « n, consisting of symbols A, C, G, T , and ∗. The problem is, again, to output a sorted list M of valid “match positions”, which are positions j in D such that pattern P matches the substring D[j . . j + |P | − 1]. For example, if D = A C G A C C A T and P = A C ∗ A, then the output M should be [0, 3]. Based on your solutions to Parts (b) and (c), give an efficient algorithm for this setting. Illustrate your algorithm on the example above. Solution: Use a reduction. Encode A as a a, C as a b, G as b a, T as b b, and ∗ as ∗ ∗. Use our previous solution to solve the problem on the resulting string, obtaining a list M ' of positions. The final output list M will consist of just the even numbers from the list M ' , all divided by 2. This will take the time it takes to convert and then solve the original problem on arrays of length 2n and 2m respectively: O(2n + 2n lg(2n)) = O(n lg n). 4 Problem Set 2 Solutions Problem 2-2. Combining B-trees [25 points] Consider a new B-tree operation COMBINE(T1 , T2 , k). This operation takes as input two B-trees T1 and T2 with the same minimum degree parameter t, plus a new key k that does not appear in either T1 or T2 . We assume that all the keys in T1 are strictly smaller than k and all the keys in T2 are strictly larger than k. The COMBINE operation produces a new B-tree T , with the same minimum degree t, whose keys are those in T1 , those in T2 , plus k. In the process, it destroys the original trees T1 and T2 . In this problem, you will design an algorithm to implement the COMBINE operation. Your algo­ rithm should run in time O(|h1 − h2 | + 1), where h1 and h2 are the heights of trees T1 and T2 respectively. In analyzing the costs, you should regard t as a constant. (a) [5 points] First consider the special case of the problem in which h1 is assumed to be equal to h2 . Give an algorithm to combine the trees that runs in constant time. Solution: Construct a new root node for T consisting of the root nodes for T1 and T2 , with the root of T1 at the left, and with k inserted between the keys of the two original roots. Then, if the number of keys in the resulting root node is at least 2t − 1 then split the root node around its median, forming a new root node containing one key and two child nodes containing at least t − 1 keys apiece. Problem Set 2 Solutions C OMBINE(T1 , T2 , k) 1 T = T1 2 R = T.root 3 R2 = T2 .root 4 i = R.n + 1 5 [ Merging the two roots into one 6 T.ki = k 7 for j = 1 to R2 .n 8 i=i+1 9 T.ki = R2 .kj T.ci = R2 .cj 10 11 T.ci+1 = R2 .cR2 .n+1 12 R.n = i + 1 13 if R.n ≥ 2t − 1 14 [ Splitting node mid = R.n 15 2 16 dummy = A LLOCATE -N ODE() 17 dummy.n = 1 18 dummy.k1 = R.kmid 19 [ Allocating Children C1 = A LLOCATE -N ODE() 20 21 C1 .n = mid − 1 22 C2 = A LLOCATE -N ODE() 23 C2 .n = R.n − mid 24 [ Creating first child C1 .c1 = T.c1 25 26 for j = 1 to C1 .n 27 C1 .kj = T.kj 28 C1 .cj+1 = T.cj+1 29 [ Creating second child C2 .c1 = T.cmid+1 30 31 for j = 1 to C2 .n 32 C1 .kj = T.kj+mid 33 C1 .cj+1 = T.cj+mid+1 34 dummy.c1 = C1 dummy.c2 = C2 35 36 T.root = dummy 37 return T (b) [5 points] Consider another special case, in which h1 is assumed to be exactly equal to h2 + 1. Give a constant-time algorithm to combine the trees. 5 6 Problem Set 2 Solutions Solution: Append k to the right end of the right child node of T1 and append the root of T2 to that. Clearly this preserves sorted order. Now the right child may have anywhere from t + 1 to 4t − 1 keys. If it has 2t − 1 or more keys, then split it around its median key. If that causes the root node to have 2t − 1 nodes then split that around its median key, thus adding another level to the tree. C OMBINE(T1 , T2 , k) 1 x = T1 .root 2 x = x.cx.n+1 3 r = T2 .root 4 n = x.n + 1 + r.n 5 [ Append k to the rightmost child 6 x.kx .n+1 = k 7 [ Append the root of T2 to the node 8 x.cx .n+2 = r.c1 9 for j = 1 to r.n 10 x.kx .n+j +2 = r.kj 11 x.cx .n+j +3 = r.cj+1 12 [ Split node if too big 13 if n ≥ 2t − 1 14 p = x.parent 15 n = p.n 16 B-T REE -S PLIT-C HILD(p, n) (c) [5 points] Now consider the more general case in which h1 and h2 are arbitrary. Because the algorithm must work in such a small amount of time, and must work for arbitrary heights, a first step is to develop a new kind of augmented B-tree data structure in which each node x always carries information about the height of the subtree below x. Describe how to augment the common B-tree insertion and deletion operations to maintain this information, while still maintaining the asymptotic time complexity of all operations. Solution: Augment the tree by adding a height attribute for each node. The height of a leaf node is 0. For internal nodes, H EIGHT(x) = H EIGHT(x.c1 ) + 1. Insertion: New nodes are added during splitting. The newly allocated node in a split has the same height as the original node. The only other time a node is added is when the root is split. This is done by making the root the child of a dummy node and then splitting it. The height of the new root is set to one greater than the height of the old root. Deletion: In deletion, no nodes are deleted except the root. Since height values are indexed starting at the leaf, deletion does not affect node heights. Problem Set 2 Solutions With these additions, the asymptotic running time for insertion and deletion is that same as before, O(lg n). (d) [10 points] Now give an algorithm for combining two B-trees T1 and T2 , in the general case where h1 and h2 are arbitrary. Your algorithm should run in time O(|h1 −h2 |+1). Solution: If |h1 − h2 | < 2, use part (a) or (b). Otherwise, assume that h1 > h2 + 1 (h2 > h1 + 1 works symmetrically). Let x be the rightmost node of T1 at level h2 . Add k at the right end of x and append the root of T2 to that. Now node x may have anywhere from t + 1 to 4t − 1 keys. If it has 2t − 1 or more keys, then split it around its median key. The split may propagate upwards, possibly as far as the root. So, the time complexity depends linearly on the height difference O(|h1 − h2 |). C OMBINE(T1 , T2 , k) 1 T = T1 2 h1 = T1 .height 3 h2 = T2 .height 4 x = T.root 5 [ Move to the rightmost node at level h2 6 for j = 1 to h1 − h2 7 n = x.n 8 x = x.cn 9 r = T2 .root 10 n = x.n + 1 + r.n 11 [ Append k to the node 12 x.kx .n+1 = k 13 [ Append the root of T2 to the node 14 x.cx .n+2 = r.c1 15 for j = 1 to r.n 16 x.kx .n+j +2 = r.kj 17 x.cx .n+j +3 = r.cj+1 18 [ Split node if too big 19 if n ≥ 2t − 1 20 p = x.parent 21 n = p.n 22 B-T REE -S PLIT-C HILD(p, n) 23 return T 7