CSCI 570 - Summer 2015 - HW5 Solutions1. Reading Assignment: Kleinb erg and Tardos, Chapter 6.1-6.4.2. (Chapter 5, Q 5 ) Let Yi,kdenote the substring yi, yi+1, · · · , yk. Denote theoptimal segmentation for Y1,kas X1, X2, · · · , Xm. A key observation tomake in this problem is that X1, X2, · · · , Xm−1is an optimal segmentationfor the prefix of Y1,kexcluding Xm(because otherwise we could substitutethe solution for the prefix by an optimal one and get a better solution).Given this observation, let Opt(k) represent the quality of an optimalsegmentation of the substring Y1,k. We have the following recurrence:OP T (k) = max1≤i≤k{OP T (i − 1) + Quality(Yi,k)} . (1)We can begin solving the above recurrence with the initial condition thatOP T (0) = 0 and then go on to compute OP T (k) for k = 1, 2, · · · , n, i.e.,OP T (0) = 0;for k = 1, · · · , n doOP T (k) = max1≤i≤k{OP T (i − 1) + Quality(Yi,k)};Record the indexiwhich achieves the maximum, denoted asi∗(k);end forReturn OP T (n);Track back through the array OP T by checking from i∗(n) to i∗(1) to recoverthe optimal segmentation.It takes O(n) time to compute each OP T (k);there are O(n) iterations; ittakes O(n) time to trace back to recover the optimal segmentation. Sothe overall complexity is O(n2).3. (Chapter 6, Q 6 ) Let W = {w1, w2, · · · , wn} be the set of ordered wordswhich we wish to print. In the optimal solution, if the last line contains pwords, then the previous lines constitute an optimal solution for the subproblem with the set {w1, · · · , wn−p}. Otherwise, by replacing with anoptimal solution for the previous lines, we would get a better solution.For i ≤ j, let S(i, j) represent the slack of a line containing the wordswi, · · · , wj. To facilitate later derivation, we set S(i, j) = +∞ if these1words exceed the length of a whole line L. Therefore, we haveS (i, j) =L −j−1∑m=i(cm+ 1) − cj, if L ≥j−1∑m=i(cm+ 1) − cj+∞, otherwise, (2)where the summation∑j−1m=icm= 0, if i > j − 1. In order to reducethe complexity, S( i, j) can be further computed based on the value ofS(i, j − 1), i.e.,S (i, i) ={L − ci, L ≥ ci+∞, otherwise, (3)S (i, j) ={S (i, j − 1) − cj− 1, if S (i, j − 1) < +∞ and S (i, j − 1) ≥ cj+ 1+∞, otherwise,(4)where j ≥ i + 1.Define OP T (k) as the sum of squares of slacks for the optimal solutionwith the words w1, · · · , wk. As noted above, the optimal solution musthave the followingOP T (k) = min1≤m≤k{(S (m, k))2+ OP T (m − 1)}, (5)and the base case is: OP T (0) = 0; Then the algorithm is as follows:for i = 1, · · · , n doCompute S(i, i) according to (3)if i < n thenfor j = i + 1, · · · , n doCompute S (i, j) according to (4);end forend ifend forOP T (0) = 0;for k = 1, · · · , n doOP T (k) = min1≤m≤k{(S (m, k))2+ OP T (m − 1)};Record the index m which achieves the minimum, denoted as m∗(k);end forReturn OP T (n);Track back through the array OP T by checking from m∗(n) to m∗(1) torecover the optimal solution.It takes O(n) time to compute all S(i, j) with fixed i by considering valuesof j in increasing order; thus, we can compute all S(i, j) in O(n2) time.Each iteration of computing OP T (k) takes O(n) time, and there are O(n)iterations. The tracking back operation takes O(n) time. Therefore, theoverall time complexity is O (n2).24. (Chapter 6, Q 10 )a) Consider the following example: there are totally 4 minutes, the num-bers of steps that can be done respectively on the two machines in the4 minutes are listed as follows (in time order):• Machine A: 2, 1, 1, 200• Machine B: 1, 1, 20, 100The given algorithm will choose A then move, then stay on B for thefinal two steps. The optimal solution will stay on A for the four steps.b) An observation is that, in the optimal solution for the time intervalfrom minute 1 to minute i, you should not move in minute i, becauseotherwise, you can keep staying on the machine where you are andget a better solution (ai> 0 and bi> 0). For the time interval fromminute 1 to minute i, consider that if you are on machine A in minutei, you either (i) stay on machine A in minute i − 1 or (ii) are in theprocess of moving from machine B to A in minute i − 1.Now let OP TA(i) represent the maximum value of a plan in miniute1 through i that ends on machine A, and define OP TB(i) analogouslyfor B. If case (i) is the best action to make for minute i − 1, wehave OP TA(i) = ai+ OP TA(i − 1); otherwise, we have OP TA(i) =ai+ OP TB(i − 2). In sum, we haveOP TA(i) = ai+ max {OP TA(i − 1) , OP TB(i − 2)} . (6)Similarly, we get the recursive relation for OP TB(i):OP TB(i) = bi+ max {OP TB(i − 1) , OP TA(i − 2)} . (7)The algorithm initializes OP TA(0) = 0, OP TB(0) = 0, OP TA(1) = a1and OP TB(1) = b1. Then the algorithm can be written as follows:OP TA(0) = 0; OP TB(0) = 0;OP TA(1) = a1; OP TB(1) = b1;for i = 2, · · · , n doOP TA(i) = ai+ max {OP TA(i − 1) , OP TB(i − 2)};Record the action (either stay or move) in minute i − 1 that achieves themaximum.OP TB(i) = bi+ max {OP TB(i − 1) , OP TA(i − 2)};Record the action in minute i − 1 that achieves the maximum.end forReturn max {OP TA(n), OP TB(n)};Track back through the arrays OP TAand OP TBby checking the actionrecords from minute n − 1 to minute 1 to recover the optimal solution.It takes O(1) time to complete the op erations in each iteration; there areO(n) iterations; the tracing backs takes O(n) time. Thus, the overallcomplexity is O(n).35. (Chapter 6, Q 16 ) For each subtree T′of T , we define OP T (T′) to be thenumber of rounds it takes for everyone in T′to be notified, once the roothas the message. Suppose T′has child sub-trees T(T′)1, T(T′)2, · · · , T(T′)dT′,and we label them so that OP T (T(T′)1) ≥ OP T (T(T′)2) ≥ · · · ≥ OP T (T(T′)dT′).For tree T′, here the root node should talk to its child sub-tree in de-creasing order of the time it takes for their sub-trees (recursively) to benotified. This greedy strategy must be optimal for T′(You can use the“swapping method” you learned in class for greedy algorithm to show itsoptimality, which is left to you as an exercise). Then the recurrence canbe expressed asOP T (T′) = max1≤j≤dT′{j + OP T (T(T′)j)}. (8)Base case: if T′is simply a leaf …