Message posted by Tyronne in the newsgroup of the course
========================================================

Hello,
I have noticed that a lot of students are having confusion about
Question 2 of this Assignment. Thus I shall give below a short
example to demonstrate the main idea.

Let 
    x_1 contain 2 digits
    x_2 contain 2 digits
    x_3 contain 4 digits

and supposing we wish to compute 

    x_1 + x_2 + x_3

using the inefficient program described in Question 2.

Thus let C[r,c] = mimimum total cost of adding x_c + x_{c+1} .... x_{c+r}
and let SP[r,c] = index of element in subsequence x_c + x_{c+1} .... x_{c+r}
                         after which the last addition takes place

The answer is as follows:

VALUES IN COLUMN=1, ROW=1
The cost of computing x_1 + x_{1+1} = max(2,2) + 1 = 3  
Therefore C[1,1] = 3
The last addition takes place after the element x_1
Therefore SP[1,1] = 1

VALUES IN COLUMN=2, ROW=1
The cost of computing x_2 + x_{2+1} = max(2,4) + 1 = 5  
Therefore C[1,2] = 5
The last addition takes place after the element x_2
Therefore SP[1,2] = 2

VALUES IN COLUMN=1, ROW=2
To find the cost of computing x_1 + x_{1+1} + x_{1+2} 
we note that there are two ways of doing this computation

FIRST WAY => (( x_1 + x_{1+1}) + x_{1+2})
There are two additions in the above statement
and thus we calculate the cost of each addition separately
and then sum the two costs to get the total cost.

The cost of computing (x_1 + x_{1+1}) = C[1,1] = 3
Let y = (x_1 + x_{1+1}). Then y will have at most 3 digits. 
Then the cost of computing y+x_{1+2} = max(3,4) + 1 = 5
Thus the cost of the first addition is 3 and the cost of the
second addition is 5. Thus the total cost of the two additions is 8.

IMPORTANT: THE TOTAL COST OF THE TWO ADDITIONS IS NOT
     max(3,5)+1 = 6

THE ABOVE IS EXTREMELY IMPORTANT AS LOT OF STUDENTS WERE
MAKING THIS MISTAKE.

Anyway back to the question ...  So if we decide to compute 
x_1 + x_{1+1} + x_{1+2} the first way, the total cost is 8.

SECOND WAY => (x_1 + (x_{1+1} + x_{1+2}))
Again there are two additions in the above statement
and thus we calculate the cost of each addition separately
and then sum the two costs to get the total cost.

The cost of computing (x_{1+1} + x_{1+2}) = C[1,2] = 5 
Let y = (x_{1+1} + x_{1+2}). Then y will have at most 5 digits. 
Then the cost of computing x_1 + y = max(2,5) + 1 = 6
Thus the cost of the first addition is 5 and the cost of the
second addition is 6. Thus the total cost of the two additions is 11.

IMPORTANT: AGAIN THE TOTAL COST OF THE TWO ADDITIONS IS NOT
     max(5,6)+1 = 7

So if we decide to compute x_1 + x_{1+1} + x_{1+2} the 
second way, the total cost is 11.

Thus when comparing the two costs, we see that it is cheaper to
compute x_1 + x_{1+1} + x_{1+2} the first way ie as
((x_1 + x_{1+1}) + x_{1+2}). This way the cost will be 8.

Therefore C[2,1] = 8.
Now in the above, the last addition is after x_{1+1}.
Therefore SP[2,1] = 2

VALUES IN COLUMN=2, ROW=2.
Here we wish to compute x_{2+1} + x_{2+2}.
However x_{2+2} = x_4 does not exist.
Therefore C[2,2] and SP[2,2] is not defined.

Thus is summary the COST and SUMMING POSITION tables are

COST
====

     |  1    2
----------------
  1  |  3    5      
  2  |  8    -

The minimum cost of computing x_1 + x_2 + x_3 = C[2,1] = 8

SUMMING POSITION
================ 

     |  1    2
----------------
  1  |  1    2      
  2  |  2    -


I hope this example clarifies some of the confusion people
are having. If it doesn't feel free to ask questions until
you understand the idea completely.

Best wishes
Tyronne