Comments on Question 1 Assignment 4 =================================== Date: Mon, 20 Apr 1998 03:47:41 -0400 From: meng@explorer.dgp.toronto.edu To: ut.cdf.csc270h@cdf.utoronto.ca Subject: Comments on Assignment 4 Question 1 Here are some of the common mistakes people made in Assignment 4 Question 1. CASE I: ======= Some students did not understand cell (r,c) should have min cost for splitting f_{c}..f_{c+r}. Instead they have cell (r,c) = cost of splitting the whole string, f_1 ... f_6, in order to segment out the substring, f_c, f_{c+1} ... f{c+r}. e.g., (f3,f4,f4,f6): cut after e 10 abcde fghij cut after b 5 ab cde fghij cut after h 5 ab cde fgh ij cut after f 3 ab cde f gh ij ---- 23 It looks like people came up with the order of cutting by merely eye-balling it. They did not realize that they should . reuse the min cost information they got for substrings; . and consider possible min cost resulting from all possible first cut locations. This is not dynamic programming. --------------------------------------------------------------------- CASE II: ======== Some other students got the table right. But the "show work" section has the same problem as people in CASE I. (a) No reuse of min cost for substring. (b) Did not consider all possible first cut locations. Most people have both problems. Because they are not reusing min cost of substrings, it would have been a big pain for them to list all possible permutations of the sequence of cuts for each little substrings. Therefore, some chose to list two possible cutting orders, say for (f2, .., f6). Meng Comments on Question 2 Assignment 4 =================================== Date: Sun, 19 Apr 1998 17:32:42 -0400 From: Hugo Sin To: ut.cdf.csc270h@cdf.utoronto.ca Subject: Assignment 4 Problem 2 In general, the marking for Problem 2 was extremely tough. If you received a mark higher than 11/15, be proud :) There were several recurring problems (message in bracket denotes corresponding marks lost and written message on assignmen): 1) For efficient computing, there was no need to calculate the minimum sums for cut points if the entire sequence could fit on a whole line! This occured at row 2, col 3 of Table 1. Almost everyone missed this. (-4 no need) 2) In the case that the entire sequence does fit on one line, the resulting minimum sum is NOT 0, unless it is the last line! You need that min sum for further calculations. In fact, there should only be one zero (for the case of w_7 by itself.. it is the last line!) in the whole table, since no subsequence of this problem will result in a full line. (-4) 3) You have to take the last line into account. Some of you just subtracted 64 (8^3, which is the min sum of w_7 by itself) from the final answer. This is wrong, because your table will not come up with the correct solution if w_6 and w_7 both fit on one line. (-5) 4) Surprisingly, too many of you did not provide the final answer! You should explicitly write something like "The optimal sequence is xxx and the minimum sum is xxx." And some of you provided the optimal sequence but not the minimum sum. The assignemnt specifically asks for both. Just imagine if someone (maybe you future boss at work) asked you to solve this problem and you gave them back 2 tables.... (-3 for optimal sequence, -3 for minimum sum) 5) For Table 1, you need to actually carry out the calculations. If you left the entries in the table as "8^3+7^3+2^3", how are you supposed to use this value to compare? Ex. if you have 8^3+7^3 and 9^3+6^3, how would a computer compare which is bigger (efficiently) without actually performing the calculation? (-4 do calcs) 6) You need to take w_7 into account. In this problem, it just happens that not both w_6 and w_7 can fit on the same line, and therefore you could exclude w_7 in the calculations and still get the right answer. This is specific to this problem. More importantly, this is NOT dynamic programming! You should have some way of using this fact in your table. That's why you need to have column 7. (-3 no col 7) 7) And as in any other dynamic programming algorithms we did this year, you also need a row 0. This should store the min sum of each word by itself is calculated. (-3 no row 0) 8) Finally, the solution must be a dynamic programming solution implementation in the computer. After the first iteration (which fills in row 0), you should not need any other variables except for the loops counter and the n = 13 (denoting the length of one line). Some of you implemented solution which needs more than the two tables, and received a very low mark as a result. And a few of you did not use a dynamic programming method, and consequently received 0/15. Good luck on your exams! Hugo