Homework 7Due Oct. 21st, 2021Note 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 uniquewords, design a dynamic programming algorithm to determine if s canbe segmented into a space-separated sequence of one or more dictionarywords. If s=“algorithmdesign” and your dictionary contains “algorithm”and “design”. Your algorithm should answer Yes as s can be segmented as“algorithmdesign”.Let si,kdenote the substring sisi+1. . . sk. Let Opt(k) denote whether thesubstring s1,kcan be segmented using the words in the dictionary, namelyOP T (k) = 1 if the segmentation is possible and 0 otherwise. A segmenta-tion of this substring s1,kis possible if only the last word (say si. . . sk) is inthe dictionary the remaining substring s1,ican be segmented. Therefore,wehave equation:Opt(k) = max0<i<k and si+1,kis a word in the dictionaryOpt(i)We can begin solving the above recurrence with the initial condition thatOpt(0) = 1 and then go on to compute Opt(k) for k = 1, 2, . . . , n. Theanswer 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 the4 minutes are listed as follows (in time order):1• 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 letOP TA(i) represent the maximum value of a plan in minute 1 throughi that ends on machine A, and define OP TB(i) analogously for B. Ifcase (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 haveOP 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) =a1and OP TB(1) = b1. Then the algorithm can be written as follows:It takes O(1) time to complete the operations in each iteration; thereare O(n) iterations; the tracing backs takes O(n) time. Thus, the over-all complexity is O(n).23. Solve Kleinberg and Tardos, Chapter 6, Exercise 24.The basic idea is to ask: How should we gerrymander precincts 1 throughj, for each j? To make this work, though, we have to keep track of a fewextra things, by adding some variables. For brevity, we say that A-votes ina precinct are the voters for part A and B-voter are the votes for part B. Wekeep 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-votesin distance 1 and y A-votes in district 2, while allocating p of the first jprecincts 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 caseyou check the results of sub-problem M[j, p−1, x−z, y]) or in district 2 (inwhich case you check the results of sub-problem M[j, p, x, y − z]). Now todecide if there’s a solution to the while problem, you scan the entire table atthe end, looking for a value of true in any entry from M[n, n/2, x, y] whereeach of x and y is greater than mn/4. (Since each district gets mn/2 votestotal).We can build this up in the order of increasing j, and each sub-problemtakes constant time to compute, using the values of smaller sub-problems.Since there are n2, m2sub-problems, the running time is O(n2m2).4. We initialize another matrix (dp) with the same dimensions as the originalone initialized with all 0’s.dp(i,j) represents the side length of the maximum square whose bottom rightcorner 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 updatethe value of the current element asdp(i, j) = mindp(i − 1, j), dp(i − 1, j − 1), dp(i, j − 1)+ 1.We also remember the size of the largest square found so far. In this way, wetraverse the original matrix once and find out the required maximum size.This gives the side length of the square (say maxsqlen). The required resultis the area maxsqlen2An entry 2 at (1, 3) implies that we have a square of side 2 up to that index inthe original matrix. Similarly, a 2 at (1, 2) and (2, 2) implies that a square of3side 2 exists up to that index in the original matrix. Now to make a squareof side 3, only a single entry of 1 is pending at (2, 3). So, we enter a 3corresponding 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 formedup 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 ithrow we are using only the previous element and the(i − 1)throw. Therefore, we don’t need 2D dp matrix as 1D dp array willbe sufficient for this.Initially the dp array contains all 0’s. As we scan the elements of the originalmatrix across a row, we keep on updating the dp array as per the equationdp[j] = min(dp[j − 1], dp[j], prev), where prev refers to the old dp[j-1].For every row, we repeat the same process and update in the same dp