==================================================== SOLUTIONS OF ASSIGNMENT 4 ---- CSC 270, FALL 1999 ==================================================== ======================== SOLUTIONS FOR QUESTION 1 ======================== ====== PART A ====== j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ======+=====+=====+=====+=====+=====+=====+=====+===== A[j] | 1 | 2 | 1 | 2 | 3 | 4 | 1 | 1 ------+-----+-----+-----+-----+-----+-----+-----+----- ====== PART B ====== A[0] = 1 For j > 0 : A[j] = A[j-1] + 1 if v_j > v_{j-1}, A[j] = 1 if v_j <= v_{j-1} ====== PART C ====== Note that the algorithm below is done using the recursive definition of Part B; this could be done in a simpler way (exercise!). int lics( const double *list, int n ) int *A = new int[ n ]; // to store array "A" int max_length; // maximum length found so far // Base case for A. max_length = A[0] = 1; // Compute the values of A following the recurrence, // and update `max_length' as we go along. for ( int j = 1; j < n; j++ ) { if ( list[j] > list[j-1] ) A[j] = A[j-1] + 1; else A[j] = 1; if ( A[j] > max_length ) max_length = A[j]; } //for delete[] A; return max_length; ======================== SOLUTIONS FOR QUESTION 2 ======================== ====== PART A ====== The cost of computing ((x_1 + x_2) + x_3) = 6+8 = 14 The cost of computing (x_1 + (x_2 + x_3)) = 8+9 = 17 ====== PART B ====== COLUMN = 1, ROW = 1 (Adding x_1 and x_2) There is only one way to perform this addition which is (x_1 + x_2). Thus MC[1,1] = 2 and SP[1,1] = 1 COLUMN = 2, ROW = 1 (Adding x_2 and x_3) There is only one way to perform this addition which is (x_2 + x_3). Thus MC[1,2] = 6 and SP[1,2] = 2 COLUMN = 3, ROW = 1 (Adding x_3 and x_4) There is only one way to perform this addition which is (x_3 + x_4). Thus MC[1,3] = 8 and SP[1,3] = 3 COLUMN = 4, ROW = 1 (Adding x_4 and x_5) There is only one way to perform this addition which is (x_4 + x_5). Thus MC[1,4] = 8 and SP[1,4] = 4 COLUMN = 5, ROW = 1 (Adding x_5 and x_6) There is only one way to perform this addition which is (x_5 + x_6). Thus MC[1,5] = 9 and SP[1,5] = 5 COLUMN = 1, ROW = 2 (Adding x_1, x_2 and x_3) There are two ways of performing this addition which are ((x_1 + x_2) + x_3) which has cost 2+6=8 (x_1 + (x_2 + x_3)) which has cost 7+6=13 Thus MC[2,1] = 8 and SP[2,1] = 2 COLUMN = 2, ROW = 2 (Adding x_2, x_3 and x_4) There are two ways of performing this addition which are ((x_2 + x_3) + x_4) which has cost 6+8=14 (x_2 + (x_3 + x_4)) which has cost 9+8=17 Thus MC[2,2] = 14 and SP[2,2] = 3 COLUMN = 3, ROW = 2 (Adding x_3, x_4 and x_5) There are two ways of performing this addition which are ((x_3 + x_4) + x_5) which has cost 8+9=17 (x_3 + (x_4 + x_5)) which has cost 9+8=17 Thus MC[2,3] = 17 and SP[2,3] = 3 or 4 COLUMN = 4, ROW = 2 (Adding x_4, x_5 and x_6) There are two ways of performing this addition which are ((x_4 + x_5) + x_6) which has cost 8+9=17 (x_4 + (x_5 + x_6)) which has cost 10+9=19 Thus MC[2,4] = 17 and SP[2,4] = 5 COLUMN = 1, ROW = 3 (Adding x_1, x_2, x_3 and x_4) There are three ways of performing this addition which are ((x_1 + x_2 + x_3) + x_4) which has cost 8+8=16 ((x_1 + x_2) + (x_3 + x_4)) which has cost 2+8+9=19 (x_1 + (x_2 + x_3 + x_4)) which has cost 14+9=23 Thus MC[3,1] = 16 and SP[3,1] = 3 COLUMN = 2, ROW = 3 (Adding x_2, x_3, x_4 and x_5) There are three ways of performing this addition which are ((x_2 + x_3 + x_4) + x_5) which has cost 14+9=23 ((x_2 + x_3) + (x_4 + x_5)) which has cost 6+8+9=23 (x_2 + (x_3 + x_4 + x_5)) which has cost 10+17=27 Thus MC[3,2] = 23 and SP[3,2] = 3 COLUMN = 3, ROW = 3 (Adding x_3, x_4, x_5 and x_6) There are three ways of performing this addition which are ((x_3 + x_4 + x_5) + x_6) which has cost 17+10=27 ((x_3 + x_4) + (x_5 + x_6)) which has cost 8+9+10=27 (x_3 + (x_4 + x_5 + x_6)) which has cost 10+17=27 Thus MC[3,3] = 27 and SP[3,3] = 4 or 5 COLUMN = 1, ROW = 4 (Adding x_1, x_2, x_3, x_4 and x_5) There are four ways of performing this addition which are ((x_1 + x_2 + x_3 + x_4) + x_5) which has cost 16+9=25 ((x_1 + x_2 + x_3) + (x_4 + x_5)) which has cost 8+8+9=25 ((x_1 + x_2) + (x_3 + x_4 + x_5)) which has cost 2+17+10=29 (x_1 + (x_2 + x_3 + x_4 + x_5)) which has cost 23+10=33 Thus MC[4,1] = 25 and SP[4,1] = 3 or 4 COLUMN = 2, ROW = 4 (Adding x_2, x_3, x_4, x_5 and x_6) There are four ways of performing this addition which are ((x_2 + x_3 + x_4 + x_5) + x_6) which has cost 23+10=33 ((x_2 + x_3 + x_4) + (x_5 + x_6)) which has cost 14+9+10=33 ((x_2 + x_3) + (x_4 + x_5 + x_6)) which has cost 6+17+10=33 (x_2 + (x_3 + x_4 + x_5 + x_6)) which has cost 27+11=38 Thus MC[4,2] = 33 and SP[4,2] = 3 or 4 or 5 COLUMN = 1, ROW = 5 (Adding x_1, x_2, x_3, x_4, x_5 and x_6) There are five ways of performing this addition which are ((x_1 + x_2 + x_3 + x_4 + x_5) + x_6) which has cost 25+10=35 ((x_1 + x_2 + x_3 + x_4) + (x_5 + x_6)) which has cost 16+9+10=35 ((x_1 + x_2 + x_3) + (x_4 + x_5 + x_6)) which has cost 8+17+10=35 ((x_1 + x_2) + (x_3 + x_4 + x_5 + x_6)) which has cost 2+27+11=40 (x_1 + (x_2 + x_3 + x_4 + x_5 + x_6)) which has cost 33+11=44 Thus MC[5,1] = 35 and SP[5,1] = 3 or 4 or 5 In filling in the table, we shall adopt the following policy. When an element in the summing table can take more than one value, we shall choose the lowest value, eg. since SP[5,1] can be 3 or 4 or 5, we shall choose SP[5,1] = 3 Then the MC and SP tables are as follows: MINIMUM COST TABLE ================== 1 2 3 4 5 6 6 - - - - - - 5 35 - - - - - 4 25 33 - - - - 3 16 23 27 - - - 2 8 14 17 17 - - 1 2 6 8 8 9 - SUMMING POSITIONS TABLE ======================== 1 2 3 4 5 6 6 - - - - - - 5 3 - - - - - 4 3 3 - - - - 3 3 3 4 - - - 2 2 3 3 5 - - 1 1 2 3 4 5 - ====== PART C ====== >From the minimum cost table, the minimum cost of adding x_1 + x_2 + x_3 + x_4 + x_5 + x_6 is the value in MC[5,1] which is 35. >From the summing position table the summing order is (((x_1 + x_2) + x_3) + ((x_4 + x_5) + x_6)) However note the summing order is not unique as other summing orders will also give the same minimum cost of 35. The above is just one of several possible summing orders. ======================== SOLUTIONS FOR QUESTION 3 ======================== ====== PART A ====== Use array A[1..n], A[i] to store value of f_{i,m-n+i}. A[1] = 1; for i = 2 to n sum = 0; for k = 1 to i-1 sum = sum + A[k]; // or sum+A[i-k] A[i] = i + m-n+i + sum; return A[n]; ====== PART B ====== Function for f(n,m) if (n==1) return 1; sum = 0; for k = 1 to n-1 sum = sum + f(n-k,m-k); return n + m + sum; ======================== SOLUTIONS FOR QUESTION 4 ======================== ====== PART A ====== Here is the CP table. Each entry holds up to 4 ordered pairs (k,CP[i-1,j-k]*PF[i,k]) with a '#' beside the pair which give the min value. CP[1,j] just contains (j,PF[1,j]). CP[i,j] is stored in row i and column j. i\j| 1 | 2 | 3 | 4 | 5 | 6 | 7 ===+========+=========+==========+=========+==========+======== ==+=========== 1 |(1,.8)# |(2,.6)# |(3,.3)# |(4, .1)# | | | ---+--------+---------+----------+---------+----------+----------+----------- 2 | |(1,.68)# |(1,.51) |(1,.255) |(1,.085)# | | | | |(2,.4)# |(2,.3) |(2,.15) | | | | | |(3,.16)# |(3,.12) | | | | | | |(4,.12) | | ---+--------+---------+----------+---------+----------+----------+----------- 3 | | |(1,.408)# |(1,.24)# |(1,.096)# |(1,.051)# | | | | |(2,.374) |(2,.22) |(2,.088) | | | | | |(3,.34) |(3,.2) | | | | | | |(4,.272) | ---+--------+---------+----------+---------+----------+----------+----------- 4 | | | | | | |(1,.03825)# | | | | | | |(2,.0624) | | | | | | |(3,.132) | | | | | | |(4,.1836) Based on the table, the optimal solution is CP[4,7] = 0.03825, which is attained by allocating 4 blocks to Cosmetics and 1 to each of the others. ====== PART B ====== For i categories and j blocks, we have a choice of allocating k = 1, 2, 3 or 4 blocks to category i. If we allocate k blocks to category i, the minimum probability of failure becomes (the minimum probability of failure for the remaining i-1 categories and the remaining j-k blocks) times (the probability of failure for k blocks of category i), which is precisely CP[i-1,j-k]*PF[i,k]. Since we want to minimize the probability of failure, we take the minimum over all possible values for k. (The restriction of i-1 <= j-k <= 4(i-1) is explained below.) For CP[i,j], j must be at least i because you need at least one block per category, and j must be at most 4i because you can have at most 4 blocks per category.