Assignment 4 solutions ---------------------- PROBLEM 1 Cost of one cut = length of string being cut These are the table entries that should be filled in, and the substring corresponding to them: 5 1,2,3,4,5,6 4 1,2,3,4,5 2,3,4,5,6 3 1,2,3,4 2,3,4,5 3,4,5,6 2 1,2,3 2,3,4 3,4,5 4,5,6 1 1,2 2,3 3,4 4,5 5,6 1 2 3 4 5 Calculations ------------ (row,column): (2,1): split at 1: 5+4 split at 2: 5+2 = 7 (2,2): at 2: 5+4 = 9 at 3: 5+4 = 9 (2,3): at 3: 6+3 = 9 at 4: 6+4 (2,4): at 4: 5+4 at 5: 5+3 = 8 (3,1): at 1: 6+9 at 2: 6+2+4 = 12 at 3: 6+7 (3,2): at 2: 7+9 at 3: 7+4+3 = 14 at 4: 7+9 (3,3): at 3: 8+8 = 16 at 4: 8+4+4 = 16 at 5: 8+9 (4,1): at 1: 8+14 at 2: 8+2+9 at 3: 8+7+3 = 18 at 4: 8+12 (4,2): at 2: 9+16 at 3: 9+4+8 = 21 at 4: 9+9+4 at 5: 9+14 (5,1): at 1: 10+21 at 2: 10+2+16 at 3: 10+7+8 = 25 at 4: 10+12+4 at 5: 10+18 Minimum Cost Table Split Position Table ------------------ -------------------- 5 | 25 5 | 3 | | 4 | 18 21 4 | 3 3 | | 3 | 12 14 16 3 | 2 3 3/4 | | 2 | 7 9 9 8 2 | 2 2/3 3 5 | | 1 | 2 4 4 3 4 1 | 1 2 3 4 5 +------------------ +------------------ 1 2 3 4 5 1 2 3 4 5 Total cost is 25. Splitting sequence is 123456 -> 123 -> 12 3 456 -> 45 6 ((12)3)((45)6) If row 0 is present, there should be six columns and all costs in row 0 should be zero. PROBLEM 2 Use the dynamic programming paradigm: Solve subproblems of smaller size before ones of larger size. A subproblem is a subsequence of the words and its solution is a way to split the words across different lines, with minimum cost. Given subsequence w_i ... w_j ... w_k, with i <= j <= k, if we insert a newline after w_j, the minimum cost for w_i ... w_k is the minimum cost for w_i ... w_j plus the minimum cost for w_{j+1} ... w_k. However, if w_i ... w_k can all fit on one line, no split should be done (since any split would have greater total cost) and the cost is the cube of the number of remaining spaces, UNLESS w_k is the last word (w_7 in our problem), in which case the cost is zero since w_i ... w_k all fit on the last line. / 0 if w_i ... w_k fit on last line Cost = | cube of spaces if w_i ... w_k fit on one line, not the last \ sum of subproblems otherwise Column c, row r of the tables corresponds to the subproblem involving w_c ... w_{c+r}. Calculations ------------ word | w_1 w_2 w_3 w_4 w_5 w_6 w_7 --------+---------------------------------- length | 6 7 2 3 5 5 9 (row,column): (0,1): (13-6)^3 = 343 (0,2): (13-7)^3 = 216 (0,3): (13-2)^2 = 1331 (0,4): (13-3)^3 = 1000 (0,5): (13-5)^3 = 512 (0,6): (13-5)^3 = 512 (0,7): 0 (1,1): 343+216 = 559 (1,2): (13-7-2-1)^3 = 27 (1,3): (13-2-3-1)^3 = 343 (1,4): (13-3-5-1)^3 = 64 (1,5): (13-5-5-1)^3 = 8 (1,6): 512+0 = 512 (2,1): at 1: 343+27 = 370 at 2: 559+1331 = 1890 (2,2): at 2: 216+343 = 559 at 3: 27+1331 = 1358 (2,3): (13-2-3-5-2)^3 = 1 (2,4): at 4: 1331+8 = 1339 at 5: 64+512 = 576 (2,5): at 5: 512+512 = 1024 at 6: 8+0 = 8 (3,1): at 1: 343+559 = 902 at 2: 559+343 = 902 at 3: 370+1000 = 1370 (3,2): at 2: 216+1 = 217 at 3: 27+64 = 91 at 4: 559+512 = 1071 (3,3): at 3: 1331+556 = 1887 at 4: 343+8 = 351 at 5: 1+512 = 513 (3,4): at 4: 1000+8 = 1008 at 5: 64+512 = 576 at 6: 576+0 = 576 (4,1): at 1: 343+91 = 434 at 2: 559+1 = 560 at 3: 370+64 = 434 at 4: 902+512 = 1414 (4,2): at 2: 216+351 = 567 at 3: 27+576 = 603 at 4: 559+8 = 567 at 5: 91+512 = 603 (4,3): at 3: 1331+576 = 1907 at 4: 343+8 = 351 at 5: 1+512 = 513 at 6: 351+0 = 351 (5,1): at 1: 343+567 = 910 at 2: 559+351 = 910 at 3: 370+576 = 946 at 4: 902+8 = 910 at 5: 434+512 = 946 (5,2): at 2: 216+351 = 567 at 3: 27+576 = 603 at 4: 559+8 = 567 at 5: 434+512 = 946 at 6: 567+0 = 567 (6,1): at 1: 343+567 = 910 at 2: 559+351 = 910 at 3: 370+576 = 946 at 4: 902+8 = 910 at 5: 434+512 = 946 at 6: 910+0 = 910 Minimum Cost Table Split Position Table ------------------ -------------------- 6 | 910 6 |1/2/4/6 | | 5 | 910 567 5 |1/2/4 2/4/6 | | 4 | 434 567 351 4 |1/3 2/4 4/6 | | 3 | 902 91 351 576 3 |1/2 3 4 5/6 | | 2 | 370 559 1 576 8 2 | 1 2 - 5 6 | | 1 | 559 27 343 64 8 512 1 | 1 2 3 4 5 6 | | 0 | 343 216 1331 1000 512 512 0 0 | +-------------------------------- +-------------------------- 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Total cost is 910. Many split sequences exists, but each causes the words to be distributed as follows: w_1 w_2 w_3 w_4 w_5 w_6 w_7 Solutions without dynamic programming get 0/15 James Stewart