0:06

We start by implementing a procedure that computes the minimum and

Â maximum value of the subexpression (i,j) through optimal values for

Â smaller sub subexpressions.

Â So the procedure is called MinAndMax(i,j).

Â So we first declared two intervals, max and min.

Â Initially min is equal to plus infinity, max is equal to minus infinity, or

Â to a very large number, or to very small number.

Â Then we go through all possible values of k between i and j- 1.

Â I mean between,

Â we just go through all possibilities of splitting our subexpression (i,

Â j) into two sub subexpressions from i to k and from k plus 1 to j.

Â 0:51

When such a splitting is fixed, we compute four possible values, applying

Â opk to either two maximum values of this subexpression or two minimum values or

Â two maximum and minimum value or two minimum and maximum value.

Â 1:07

When such two values are computed,

Â we just check whether one of them can improve our minimum or maximum values.

Â If it improves we update the min or max variable.

Â Finally we return the minimum value and the maximum value for our subexpression.

Â 1:27

Our current relation expresses the solution for an expression (i,j) for

Â a solution for smaller sub subexpressions.

Â What do we mean by saying smaller?

Â Well, we mean just that they are shorter, right?

Â So once again when we compute the value for a subexpression (i,j) we rely on

Â the fact that those are values for shorter subexpressions are already computed.

Â This means that our algorithm needs to compute the solutions for

Â all subproblems in order of increasing length.

Â Namely, in order of increasing value of j minus i, right?

Â So for this problem we have roughly quadratic number of subproblems.

Â Namely our subproblem, i, i, j, is parameterized by the value of i and

Â j which in turn range from 1 to n.

Â Right, so it makes sense in this case to store the values for

Â all subproblems in a two dimensional table of size n by n.

Â Recall also that we need to recall our subproblems

Â in the order of increasing value of j- 1.

Â We can do this just by going through all subproblems in an order

Â shown on the slide.

Â So, why this order?

Â Well this is simply because it goes through all possible values of i,

Â j in order of increasing j minus y as required.

Â So lets take a look.

Â On this diagonal we have

Â all the cells where I, where j- i is equal to 0, right?

Â 3:07

So the first cell here is 1, 1.

Â The second cell is 2, 2.

Â The third cell is 3, 3 and so on.

Â We then proceed to this cell here i is equal to 1,

Â j is equal to 2, so the difference is 1.

Â We then proceed to this cell.

Â 3:25

This is the cell 2, 3 with the difference 1 again.

Â We then proceed to this cell which is 3, 4 and so on.

Â So on this cell we have on this diagonal we have all the cells i,

Â j where i- j = 0.

Â On this diagonal we have all cells i, j where j- i = 1.

Â For this diagonal, this difference is equal to two.

Â For this diagonal, this difference is equal to three and so on.

Â The resulting value for

Â our initial subproblem will be computed as the value of the last cell.

Â 4:06

Right, because of this cell responds to the initial subexpression from one to n.

Â Now everything is ready to write down an algorithm.

Â In the algorithm we will maintain two tables, m and capital M.

Â The first one for storing the minimum values for all subexpressions, and

Â the second one for storing the maximum values for all subexpressions.

Â We start by initializing these tables as follows.

Â So when subexpression contains just one digit,

Â which means that when j = i, then there is nothing,

Â actually to minimize or maximize because there are no operations.

Â So there is no order on operations.

Â So, because of that we just initialize

Â the main diagonals of this table with the most current point in digits.

Â This is with the following loop.

Â So m(i,i) and M(i,i) = di.

Â Then we go through all possible subproblems in order of increasing size.

Â And this is done as follows.

Â We gradually increase the parameter s from 1 to n- 1.

Â This is done in the following loop.

Â When s is fixed, i goes from 1 to n- s.

Â And j is computed as i + s.

Â This is done to go through all possible payers (i,j)

Â such that j- i = s.

Â Right when i and j are fixed we call the procedure min and

Â max to compute the minimum and maximum value of the subexpression (i,j).

Â All right.

Â So finally we return the value of capital M of 1,n as the result for

Â our initial problem because this subexpression,

Â 1 n corresponds to our initial problem.

Â Containing all digits from 1 to n.

Â 6:14

Namely, big O of nq.

Â And these can be seen by noting that we have two nested loops.

Â The first one with n-1 iterations, the inner one is

Â with n-s iterations, which is at most n.

Â Also, inside these two loops we have a call to min and max procedure.

Â The running time of min and

Â max procedure is proportional to j-i which is also at most n.

Â So the right end time however algorithm is it must O and

Â n times n time n, which is n cubed.

Â This slide shows an example on how a table's m and

Â capital M look like if we ran a well reason on our toy example,

Â namely expression 5- 8 + 7 x 4- 8 + 9.

Â Let's just go through this example step by step.

Â So we start by filling in the values on the main diagonal in both matrices.

Â So this is 5, this is 8, this is 7, this is 4, 8, 9.

Â So this response to subexpression consisted of just one digit.

Â So there is nothing to maximize or minimize.

Â 7:43

Well with -3 here and this corresponds to this subexpression

Â again in this case there is just one operation.

Â So there is nothing to minimize or maximize here,

Â because there will just be one other when we have Just one sign.

Â So we put -3 here this corresponds to the problem, to the subproblem one, two.

Â Let me put all the indices here by the way.

Â 8:20

Then we proceed through the cell to 3, which corresponds to this subproblem.

Â Again, there is nothing to maximize or minimize so we continue in the same way.

Â In this case it is not so interesting and

Â then we proceed to the third day namely to this cell.

Â 8:43

So this can respond to the subexpression 1,3 which

Â consists of three digits and two operations, minus and plus.

Â So we know that one of them is the last operation in the optimal order

Â when computing minimal value for example.

Â So as soon as this is minus.

Â This will split the subexpression into two sub subexpression, 5 and 8 + 7.

Â So for both the subexpressions we already know their maximum and minimum values.

Â So once again, this subexpression corresponds to (1, 1),

Â this subexpression corresponds to (2, 3).

Â Sort of from second to third digits, and third digit from first to first digit.

Â So we know that for the first subexpression we know already it's minimum

Â value it is here, and it's maximum value, it is here.

Â So for the second subexpression, we already know it's minimum value,

Â it is here.

Â It is 15, and then its maximum value.

Â It is also 15.

Â So by going through all possible pairs of obviously maximum and

Â minimum values, in this case, they're all the same.

Â We compute the minimum value, which is just 5- 15.

Â It is minus ten.

Â However, this was only the first case of splitting this

Â 10:09

sub expression into two sub expressions.

Â And as a possibility would be the following so

Â we can split it into the following two subexpressions.

Â So this corresponds to 1, 2 and this corresponds to 3,3.

Â 10:28

Right?

Â So, for one two we know its minimum value, it is minus three,

Â and its maximum value, it is also minus three.

Â For 3, 3 we know its maximum value.

Â It is here, seven.

Â Its minimum value and its maximum value.

Â So then we can compute- 3 + 7,

Â which gives us just 4.

Â So for the maximum value of the subexpression (1,3) we select 4.

Â For the minimum value we select -10.

Â So we proceed filling in this table in a similar fashion.

Â So we then put 36 here in this cell, then -20 in this cell,

Â 11:22

and then parallel we put 60 here, 20 here, and so on.

Â So, in the end we see the value 200 here.

Â And this is the maximum value of our initial expression.

Â This still doesn't give us the optimal load rate itself, but

Â we will be able to reconstruct it from these two tables.

Â Now we are sure that the maximum value of our initial expression is 200,

Â and we will find out the optimal ordering, or the optimal sizing in a minute.

Â