Perform the Matrix-Chain-Order algorithm from Section 15.2 on an input giving the following sequence of dimensions: \(\langle 32, 12, 8, 76, 72, 28\rangle\). Fill in the tables, and then write out the optimal parenthesization.
Based on your superb algorithms and optimization skills, you have been hired by a medical research company to help optimize their operations. The first problem they ask you to solve is to devise an algorithm to minimize the cost of cutting a strand of DNA into pieces. For a length \(L\) strand, you are given \(n\) positions \(p_1, p_2, \ldots, p_n\) at which it needs be cut, where each \(p_i\) denotes the distance from the beginning of the original strand. Position 0 is the far left of the strand. You are given the positions in sorted order, so \[ 0 < p_1 < p_2 < \cdots < p_n < L . \] Only one cut can be made at a time, and the cost of cutting a strand is proportional to the length of the strand, so the order in which cuts are made affects the overall cost. For example, if you are given a strand with \(L=100\) that must be cut at positions \(p_1=25\) and \(p_2=50\), then your first cut always costs $100, but if you cut at \(p_1\) you are left with a strand of length 75 which will cost $75 to cut. On the other hand, if you cut at \(p_2\) first, then you cut a length \(50\) strand for the second cut, which costs only $50, saving you $25 over the other solution.
Consider a problem with \(L=100\), and three cuts to be made at \(26\), \(50\), and \(78\). Calculate the cost of each of the \(3!=6\) possible orders for making cuts, and find the lowest-cost order.
At first glance it seems reasonable that the following rule will give the optimal ordering: For any piece that requires cutting, make the cut that is as close to the middle as possible. Repeat this process until no more cuts need to be made. Come up with an example that shows that this does not always give the lowest cost sequence of cuts. Note: It is possible to do this with a problem with only 3 cuts.
Clearly state the recursive characterization of the optimal cost, and use this to design a dynamic programming solution for this problem. Give your dynamic programming solution using pseudocode. The running time must be polynomial in \(n\).
Prove that your algorithm always finds the optimal solution (remember to focus on the “optimal substructure” property).
Analyze the running time of your algorithm.
Illustrate how your algorithm works (filling in the dynamic programming table and giving the optimal ordering of cuts), using the example problem you gave in part (b).
Illustrate how your algorithms works on the following problem: \(L=200\) and cut positions at \(\langle 10, 16, 20, 98, 100, 105, 130\rangle\).