CSCI 570 Summer 2015 HW5 Solutions 1 Reading Assignment Kleinberg and Tardos Chapter 6 1 6 4 2 Chapter 5 Q 5 Let Yi k denote the substring yi yi 1 yk Denote the optimal segmentation for Y1 k as X1 X2 Xm A key observation to make in this problem is that X1 X2 Xm 1 is an optimal segmentation for the prefix of Y1 k excluding Xm because otherwise we could substitute the solution for the prefix by an optimal one and get a better solution Given this observation let Opt k represent the quality of an optimal segmentation of the substring Y1 k We have the following recurrence OP T k max OP T i 1 Quality Yi k 1 i k 1 We can begin solving the above recurrence with the initial condition that OP 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 do OP T k max OP T i 1 Quality Yi k 1 i k Record the index i which achieves the maximum denoted as i k end for Return OP T n Track back through the array OP T by checking from i n to i 1 to recover the optimal segmentation It takes O n time to compute each OP T k there are O n iterations it takes O n time to trace back to recover the optimal segmentation So the overall complexity is O n2 3 Chapter 6 Q 6 Let W w1 w2 wn be the set of ordered words which we wish to print In the optimal solution if the last line contains p words then the previous lines constitute an optimal solution for the sub problem with the set w1 wn p Otherwise by replacing with an optimal 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 words wi wj To facilitate later derivation we set S i j if these 1 words exceed the length of a whole line L Therefore we have j 1 j 1 cm 1 cj cm 1 cj if L L 2 S i j m i m i otherwise j 1 where the summation m i cm 0 if i j 1 In order to reduce the complexity S i j can be further computed based on the value of S i j 1 i e L ci L ci S i i 3 otherwise S i j 1 cj 1 if S i j 1 and S i j 1 cj 1 S i j otherwise 4 where j i 1 Define OP T k as the sum of squares of slacks for the optimal solution with the words w1 wk As noted above the optimal solution must have the following 2 OP T k min S m k OP T m 1 5 1 m k and the base case is OP T 0 0 Then the algorithm is as follows for i 1 n do Compute S i i according to 3 if i n then for j i 1 n do Compute S i j according to 4 end for end if end for OP T 0 0 for k 1 n do 2 OP T k min S m k OP T m 1 1 m k Record the index m which achieves the minimum denoted as m k end for Return OP T n Track back through the array OP T by checking from m n to m 1 to recover the optimal solution It takes O n time to compute all S i j with fixed i by considering values of 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 the overall time complexity is O n2 2 4 Chapter 6 Q 10 a Consider the following example there are totally 4 minutes the numbers of steps that can be done respectively on the two machines in the 4 minutes are listed as follows in time order Machine A 2 1 1 200 Machine B 1 1 20 100 The given algorithm will choose A then move then stay on B for the final 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 interval from minute 1 to minute i you should not move in minute i because otherwise you can keep staying on the machine where you are and get a better solution ai 0 and bi 0 For the time interval from minute 1 to minute i consider that if you are on machine A in minute i you either i stay on machine A in minute i 1 or ii are in the process of moving from machine B to A in minute i 1 Now let OP TA i represent the maximum value of a plan in miniute 1 through i that ends on machine A and define OP TB i analogously for B If case i is the best action to make for minute i 1 we have OP TA i ai OP TA i 1 otherwise we have OP TA i ai OP TB i 2 In sum we have OP 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 a1 and 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 do OP 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 the maximum 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 for Return max OP TA n OP TB n Track back through the arrays OP TA and OP TB by checking the action records from minute n 1 to minute 1 to recover the optimal solution It takes O 1 time to complete the operations in each iteration there are O n iterations the tracing backs takes O n time Thus the overall complexity is O n 3 5 Chapter 6 Q 16 For each subtree T of T we define OP T T to be the number of rounds it takes for everyone in T to be notified once the root T T T has the message Suppose T has child sub trees T1 T2 TdT T and we label them so that OP T T1 T OP T T2 …