Homework 7 Due Oct 21st 2021 Note This homework assignment covers dynamic programming from Klien berg and Tardos 1 Given a non empty string s and a dictionary containing a list of unique words design a dynamic programming algorithm to determine if s can be segmented into a space separated sequence of one or more dictionary words If s algorithmdesign and your dictionary contains algorithm and design Your algorithm should answer Yes as s can be segmented as algorithmdesign Let si k denote the substring sisi 1 sk Let Opt k denote whether the substring s1 k can be segmented using the words in the dictionary namely OP T k 1 if the segmentation is possible and 0 otherwise A segmenta tion of this substring s1 k is possible if only the last word say si sk is in the dictionary the remaining substring s1 i can be segmented Therefore we have equation Opt k max 0 i k and si 1 k is a word in the dictionary Opt i We can begin solving the above recurrence with the initial condition that Opt 0 1 and then go on to compute Opt k for k 1 2 n The answer corresponding to Opt n is the solution and can be computed in n2 time 2 Solve Kleinberg and Tardos Chapter 6 Exercise 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 the 4 minutes are listed as follows in time order 1 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 nal 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 minute 1 through i that ends on machine A and de ne 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 Similarly we get the recursive relation for OP TB i OP TB i bi max OP TB i 1 OP TA i 2 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 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 over all complexity is O n 2 3 Solve Kleinberg and Tardos Chapter 6 Exercise 24 The basic idea is to ask How should we gerrymander precincts 1 through j for each j To make this work though we have to keep track of a few extra things by adding some variables For brevity we say that A votes in a precinct are the voters for part A and B voter are the votes for part B We keep track of the following information about a partial solution How many precincts have been assigned to district 1 so far How many A votes are in district 1 so far How many A votes are in district 2 so far So let M j p x y true if it is possible to achieve at least x A votes in distance 1 and y A votes in district 2 while allocating p of the rst j precincts to district 1 Now suppose precinct j 1 has z A votes To com pute M j 1 p x y you either put precinct j 1 in district 1 in which case you check the results of sub problem M j p 1 x z y or in district 2 in which case you check the results of sub problem M j p x y z Now to decide if there s a solution to the while problem you scan the entire table at the end looking for a value of true in any entry from M n n 2 x y where each of x and y is greater than mn 4 Since each district gets mn 2 votes total We can build this up in the order of increasing j and each sub problem takes constant time to compute using the values of smaller sub problems Since there are n2 m2 sub problems the running time is O n2m2 4 We initialize another matrix dp with the same dimensions as the original one initialized with all 0 s dp i j represents the side length of the maximum square whose bottom right corner is the cell with index i j in the original matrix Starting from index 0 0 for every 1 found in the original matrix we update the value of the current element as dp i j min cid 0 dp i 1 j dp i 1 j 1 dp i j 1 cid 1 1 We also remember the size of the largest square found so far In this way we traverse the original matrix once and nd out the required maximum size This gives the side length of the square say maxsqlen The required result is the area maxsqlen2 An entry 2 at 1 3 implies that we have a square of side 2 up to that index in the original matrix Similarly a 2 at 1 2 and 2 2 implies that a square of 3 side 2 exists up to that index in the original matrix Now to make a square of side 3 only a single entry of 1 is pending at 2 3 So we enter a 3 corresponding to that position in the dp array Now consider the case for the index 3 4 Here the entries at index 3 3 and 2 3 imply that a square of side 3 is possible up to their indices But the entry 1 at index 2 4 indicates that a square of side 1 only can be formed up to its index Therefore while making an entry at the index 3 4 this el ement obstructs the formation of a square having a side larger than 2 Thus the maximum sized square that can be formed up to this index is of size 2 2 To reduce space complexity for calculating dp of ith row we are using …