Supreme Chancellor Palpatine wants to create more clones for his army to fight the Jedi Order. He has a proposed DNA sequence, but his clone production machinery has been scrambled and he has been left with a sequence of DNA strands where somesubsequenceof these strands can (hopefully) be stitched together (i.e., concatenated) to form the proposed DNA sequence.
Supreme Chancellor Palpatine has tasked his underlings to find the most efficient way to stitch together a subsequence of the scrambled DNA strands in order to recover the proposed DNA sequence.
Input Format
Supreme Chancellor Palpatine has provided you with the proposed DNA sequence as well as a sequence of DNA strands.
The first line contains a target string (i.e., proposed DNA sequence).
The next line specifices a number of tiles (i.e., DNA strands).
The finallines contain the tiles.
NOTE: The tiles are 1-indexed, meaning that (as above) we denote the first tile as(with the subscript indicating index 1). s1,s2,....,sk
tiles-sample-IO/input0.txt thhhxhhxtxstbhststht 22 thhhxhhxtx th th s h t bxst h xh h hs sh h x t x txsbbhststht sth xstb hs tstht b tiles-sample-IO/input1.txt vqpmpvpmmqvmmmmppmmv 36 vq v pmp v vqp vp v qp qp v mpvp mpqvm v p pmmv mpvpv v p mqv m v vp mqvm v mmmq m ppmpv p mmmpp mmp q m p v mmv mm tiles-sample-IO/input2.txt zjpjnpjpnpjpjnznjzpnzzjjnnpznnzjjjnzpnznzzjpnnpzjnzpjjpznnpzzzjpznjnjjpjnzpnjnjjzznjzjjjppppnnzpppnj 83 zjpjnpjpnpjpjnznjzpnzzjjnnpznn zjpjnpjpnpj zjpjnpjpn zjpjnpj zjpjnpjpnpjpjnznjzpnzz zjpjnpjpnp zjpjnpjpn pnpjpj nznj jp jjnnp zjpjnpjpnpjpjnzn pjpjnznjzpnzzjnnnpz zjpjnpjp npj jzpnz nnpjj pjnznjzpnzzjjnnpznnzjjjnz pjnznjzpnzzjjnn pjpjnznjz jn zpnzzjjnnpznnzjj pn pnzpnznzzjpnnpzjn pnzzjjnnpznnzjjjnzpn nnzzjpnnpzjnzpj pznnzjjjnzpnznzzjpnnpz jn zjjnnpznnzjjjjz zjpjnpjpnpjp jnzpjjpz j n znzzjpnnpzjnzpjjpznnpzzzjpznjn znn z nznjzpnzjjjnnpznn jpznnpzzzjnznjnj zjjj znjzpnzzjjnnpznnzjj nzpnznzzjpnnpzjn zpjjpznnpzzzjpzn pnznzzjpnnpzjnzpjjpznnpzz jpjnzp pjjpznnpzzzjpznjnjjpnnzp jnjjpjn zjjznzp nznzzjpnnpzjnz zjjjnzpnznz njnjjzznjzjjzppppnnzpp z npzzzjpznjnjj pj zjpnnpzjnzpjjpznn pzzzjpz jnzpnznzzjpnnpzjnzpjjp pjnzp znnpzzz jpznjnjjpjnzpnjnjjzznjzjj njnjjpjnzpnjnjjzznjzjjp jjpjnzpnjnjjzznjzj jjppppnnzpppnj pjjp jjn jjzzzjzjjjppppnnzpppnj pnznzzjpnnpzjnzpjjpznnpzzzjp znjnjjp z ppz pnnzpppnj zpnjnjjzznj zjpznj njjpjnzj jnzpnjnjjzznjzjjjppppnnzpppnj z jjjpp ppnnzpppnj jppppnnzpppnj zn njnjjzznjzjjj ppppnnzpppnj njnjjzznjzjjjppppnnzpppnj npzzzjpznjnjjpjnzpnjnjjzznjzjjjppppnnzpppnj tiles-sample-IO/input3.txt xxbopooobpxboxpoopxopopbppxxxbpppxbboxoooobpxppbxoxbbppobpbopxpbpoxxppopobxxoxopppoxoobbooxbooopppbopobobbobooxbxobxppxbobbpoxpbobboxpobbpbbobboopxxpbobpooxoxpxbbpboxopxxpooxxbpobxpbobxxoppoxppopxbxoo 186 xxbopooobpx x xxbopooobpxboxpoopxopop xx xopooobpxboxpoo x xx xxbopooobpxboxpoopxopopbp xxbop xbopooobpxboxpoopxopop bopooobpxboxpoopxopopbppxxxbpppxbboxo pxopoppppx xxbopooobpxboxpoopxo o xbo p bppxxxbppp obobpxboxpoopx popbpp xxbopo xxxpp boxpoopxo opopbbpxxxbpppxb oobpxboxpoopxopopbp pxxxbpppxoboxo xx xbboxob boxoooo xxxbpppxb ooobppppbx bppxxxbpppxbbo boxoooobp popbppxx xbpppx xxbboxooo pooobpxboxpoopxopopbp oobpxppbxoxbbppob oobpxppbxoxbb x xppbxoxbbppobp ppob bbox oob oooobpxpp xoooobpxppbxoxbbpp bpxppbxoxbbppo pxxxbpp obpoppbxoxb bpppxbboxooo obp bxoxbbppobpbopx b obop xppbxoxbbppobp obpbop bopxpbpoxxppopobxxoxop bppxbpbopxpb xpb pxbboxo xpbp ppox ooobpxppbxoxbbppobpbopxpbp bpp pbopxpb poxxppopo pbp oxxppopobxxox poxxppopobxxoxopppox bbp p opppoxoo bobb bxxoxopppoxoobbooobooopppbopob oxxppopobxxox oxxppopobxxoxopppoxoobbooxbooopppbopo xpbpoxxppopobxxoxoppp bb ooxbooopppbopob oxoobboo xpo bobbobo oxbxobxppxbobb poxpb oopp obboxpobbpbbob x obop boopx pb oxxppopobxxoxopppoxo obbooxbooopppbopob oo o b ooxpooo bobooxbxobxppxbobbpoxp obbobooxbxobxppxbobb opppoxoobbooxbooo poxpbobb xb boo bobbo xpbobpoox oxpob pppbopobobbopooxbxob oxpxbbpboxopxxpooxxbpo booxbxobxppxo pbopxpbxo bpb opobpbbobo xpobb bobboo oxbxoboppxbo xpp b pppbopobobboboox oobbooxbooopppbopobobb bbpoxpbobboxpo x bpox xppopobxboxop xxbpopo pxxpbobpooxoxpxbbpboxopxxpooxxbpob obooxbxo bbpbbobboopxxpbo bpooxxx bxppxbobbpoxpbobboxp bobbpox bxxoxopp ppoxxobbooxbooop poxoobbooobooopppbopobob pbbobboop obb xxpbobpooxoxpxbbpb pbobboxpobppbbo bxobxppx ppbopobobboboox booooxbx bo bbpoxp pxbbpboxopxxpooxxbpobxp pbbobboopxxpbobp oxopxxp bxobxppx bobboxpobbpbbobbo opxxpbobpooxoxpxbbpbox opxxpooxxbpob bbxppxbobbp ooxxbpobxp bboopxxpbobpooxoxpxbbpboxopxxp xpbobxxoppoxppo b ooxxbpob b x oxb xpbobboxpob xpbobxxoppoxppopxbxoo poxpbobboxpobbpbbobboopxxpbobpoo obb poxxb obboxpobbpbbobboopxxpbobpooxoxpxbbpboxopxx pbobxxoppox pxb bobxxop poo bpbbooboopxxp ooxoxpxbbpb ppopxbx oo xpbobxxoppx oxopxxpoo bobxx boxp ooxoxpxbbpboxopxxpooxxbpobxpbobxxoxpoxppopx xxbpobxp bobxxoppoxppopxbxoo xxbpobxpbobxxoppoxppopobxoo xppopxbxoo poxppopxbxoo xoxpxbbpboxopxxpo oppoxopop bbxoo booo xoo oxxbpobppbobxxoppoxppopxbxoo tiles-sample-IO/input4.txt qcwbqfpybmccqmwoqqqcqycoabqwqbowcopcmacoqomwppofwqmpmbopqopqwmocyfppompoapyyyymwmfmfpmqoapwocqcyymbp 38 qcwbqfp qcw qcwbqfpybmccqmwoqq qcqycoqbqw qcwbqfpybmccqmwoqqqcqycoab qcwbqfpybmccqmwoqq qfqy coabqwqbowcopcmacoqomwppofwqmpmbopbopqwmocyfpp q wqb qbowcopcmacaqomwppofwqmp ompoap ybmccqmwo bqfpybm mbopqopqwmocy yyyymwmfmfpmq oapwocqcyym qqfcqycoabqwqbowcopcmacoqomwppof wcqmwoqqqcq wqp ycoabqwqbowcb pcyacoqomwppofw f pmbopqopqwmocyfppom owcopcmacoqomwppofwqmpmbo qmpmbopqopqwmqcyfppo by ppomp pqopqwmocyfppompoapyyyymwmf afpmqo oapyyyymwmfmfpmqyapw poapyyyymwmfmfpmqoapwocqcby apwocqcyy fpoa oqqcyymbp pyyyymwmfmfpmqoapwocqcyymbp mbp mbp tiles-sample-IO/output0.txt 10 2 5 8 9 10 14 15 19 20 21 tiles-sample-IO/output1.txt 6 5 11 20 23 29 35 tiles-sample-IO/output2.txt 5 2 18 66 67 74 tiles-sample-IO/output3.txt 11 4 11 62 75 81 82 83 85 101 123 158 tiles-sample-IO/output4.txt 0 Basic Algorithms — Spring 2020 — Problem Set 7 Due: Wed, April 29, 11am 1. Mastering the Master Theorem. Use the “Master Theorem,” as discussed in class, to solve the following recurrences: (a) T (n) ≤ 2T (bn/4c) +O( √ n) (b) T (n) ≤ 2T (bn/4c) +O(n0.51) (c) T (n) ≤ 3T (bn/3c) +O(n) (d) T (n) ≤ 16T (bn/4c) +O(n1.5) (e) T (n) ≤ 7T (bn/2c) +O(n2) 2. Weighing coins. You are given n coins — they all look identical, and all have the same weight except one, which is heavier than all the rest. You also have a balance scale, on which you can place one set of coins on one side, and another set of coins on the other, and the scale will tell you whether the two sets have the same weight, and if not, which is the heavier set. Suppose that performing one such weighing takes one minute, and in addition, you have to pay a fee of m dollars, where m is the total number of coins placed on the scale in that weighing. Design and analyze a strategy that will identify the heavy coin in O(log n) minutes and at a cost of O(n) dollars. You may analyze the your strategy using the Master Theorem. You may not assume that n has any special form (although you might want to first think about the case where n is a power of 2). 3. Quasi-linear recursion tree analysis. Suppose we have an algorithm that on inputs of size n, recursively solves two problems of size n/2, with a “local running time” t(n) that satisfies c1n log2(n) ≤ t(n) ≤ c2n log2(n) for some constants c1, c2 and all n ≥ 2. For simplicity, assume that n is a power of 2. Also, assume that n ≥ 2 and the recursion stops when n = 2. Let T (n) be the total running time of the algorithm on inputs of size n. Prove that d1n(log2(n)) 2 ≤ T (n) ≤ d2n(log2(n))2 for some constants d1, d2 and all n ≥ 2. Note that the Master Theorem is not directly applicable here. However, you should prove this using a recursion tree analysis, similar to the one that was used to prove the Master Theorem in class. Hint: for each level j, estimate the number of subproblems at that level, and the local running time for each subproblem at that level. 4. Uneven divide and conquer (1). Suppose we have an algorithm that on problems of size n, if n ≥ 10, it recursively solves two subproblems, one of size b0.7nc and one of size b0.2nc. Furthermore, the “local running time” is O(n). Prove that T (n) = O(n) using a recursion tree analysis. Hint: Let Sj be the sum of all subproblem sizes at level j. Show that Sj+1 ≤ 0.9Sj for all j ≥ 0. To get started, suppose the subproblems at level j have sizes n1, . . . , nk, so Sj = ∑ i ni. 5. Uneven divide and conquer (2). Suppose we have an algorithm that on problems of size n, if n ≥ 10, it recursively solves two subproblems, one of size b0.9nc and one of size b0.1nc. Furthermore, the “local running time” is O(n2). Prove that T (n) = O(n2) using a recursion tree analysis. Hint: Let Sj be the sum of the squares of the subproblem sizes at level j. Show that Sj+1 ≤ 0.82Sj for all j ≥ 0. To get started, suppose the subproblems at level j have sizes n1, . . . , nk, so Sj = ∑ i n 2 i . 1 6. Roots to coefficients. You are to design an efficient algorithm for the following problem. The input is a list of elements a1, a2, . . . , an ∈ F , where F is some field. The output is the coefficient vector of the polynomial (X − a1)(X − a2) · · · (X − an) ∈ F [X]. For example, if the input is the 1, 2, 3, 4, the output would be (24,−50, 35,−10, 1), which is the coefficient vector of the polynomial (X − 1)(X − 2)(X − 3)(X − 4) = 24− 50X + 35X2 − 10X3 +X4. A simple but not very efficient algorithm would run as follows: f ← 1 for i ∈ [1 . . n] do f ← f · (X − ai) output f Note that in general, if we have f = c0 + c1X + · · ·+ cdXd, and a ∈ F , then we have f · (X − a) = −ac0 + (c0 − ac1)X + · · ·+ (cd−1 − acd)Xd + cdXd+1. This means that in the above algorithm, each loop iteration can be implemented so as to cost Θ(i) operations in F , and hence the total cost of the above algorithm is Θ(n2) operations in F . Your task is to design a faster algorithm for this problem. That is, your algorithm should use o(n2) operations in F . To this end, you may make use of a fast polynomial multiplication algorithm Mul that takes as input two polynomials in F [X] and outputs their product (inputs and outputs are represented by their coefficient vectors). You may assume that the algorithm Mul runs in time O(dα), where d is a bound on the degrees of the input polynomials, and α is a constant, where 1 < α="">< 2. use a divide and conquer strategy to design your algorithm. you may analyze the running time of your algorithm using the “master theorem” from class. 2 2.="" use="" a="" divide="" and="" conquer="" strategy="" to="" design="" your="" algorithm.="" you="" may="" analyze="" the="" running="" time="" of="" your="" algorithm="" using="" the="" “master="" theorem”="" from="" class.="">