Note that this is a “half-assignment” in order to fit it in before Spring Break, and it will only count for 50 points. Note that problems 2 and 3 are programming challenges – there is information in Canvas about how to submit solutions for these problems. Also note that the first two problems together are worth 88% of your grade. That means you can get a high B without solving the final programming challenge, but to get an A you’ll need to solve both challenges!

Assignment 3 - Due Thurs, March 3, 2022

  1. (35 points) Consider multiplying six matrices together, with the following sizes:

    \(A_1\): \(8\times 14\)
    \(A_2\): \(14\times 4\)
    \(A_3\): \(4\times 12\)
    \(A_4\): \(12\times 4\)
    \(A_5\): \(4\times 10\)
    \(A_6\): \(10\times 16\)

    1. If you just did the multiplications from left-to-right, as \((((((A_1 A_2) A_3) A_4) A_5) A_6)\), how many scalar multiplications are performed?

    2. Work through the Matrix-Chain-Order algorithm for these matrix sizes, producing the \(m\) and \(s\) arrays, and then showing the optimal parenthesization for the product.

    3. How many scalar multiplications are required in this ordering?

  2. (Programming Challenge – 9 points) You have decided to put your computer science skills to good use while working in the lumber section of Home Depot. Decorative molding comes from the distributor in \(n\) foot long pieces, but you can sell it in pieces of any integer length. Different pieces have different values, and you are given a handy-dandy table that gives the value for each possible length. Your task is to figure out how to cut up an \(n\)-foot long piece to sell it for the maximum possible amount.

    Consider this example: A trending BricBrak video shows how to make a totally adorable craft project that uses 5-foot lengths of molding, so your store has been inundated with BricBrakers willing to pay a premium for pieces cut to 5 feet long. Unfortunately, boards come in 8-foot lengths, so cutting a 5-foot piece would leave you with a 3-foot left-over that isn’t worth much. Given the following table of prices, is it better to cut the molding to produce 5-foot pieces (and do you cut the 3-foot piece up further), or is there a better strategy?

       Length (feet):    1  2  3  4  5  6  7  8
   Value (dollars):  2  5  6  7 14 15 16 18

    It turns out that the best strategy in this situation is to cut the 8-foot board into three pieces with lengths 1, 2, and 5, for a total value of 2+5+14 = 21 dollars.

    Program Input: The input to this problem will have the integer \(n\) on the first line, followed by \(n\) lines giving the value of lengths 1 through \(n\). The input for our example problem would look like this:

    8
2
5
6
7
14
15
16
18

    Program Output: The output should consist of the lengths of pieces, from smallest to largest, with each length on its own line. Note that if you have multiple pieces of the same length, that appears in the output as multiple lines with the same length printed. There may be multiple solutions with the same optimal cost, and in that case any such solution will be accepted in the output. Here is what the output for the example should look like:

    1
2
5

    Program Constraints: Your program must be able to process inputs with values of \(n\) between 1 and 6000 in under 10 seconds.

  3. (Programming challenge – 6 points) Given your great work in the last problem, maximizing profit for your employer, they give you a promotion to working with plywood sheets. The sheets come in \(n\)-foot by \(n\)-foot square sheets, and when you cut a piece you must cut all the way across it. However, you can cut in either dimension. Now each \(x\)-by-\(y\) size has a value, and these are given in the input. For the prices given in the sample input below, here is a picture of an optimal cutting (numbers are the value of each piece), giving pieces with a total value of 374.

    The first cut takes the 5-by-5 sheet and cuts it into two pieces, one being 2-by-5 and the other being 3-by-5. There is no sequence of cuts that gives higher total value than this.

    Program Input: The input to this problem consists of a number \(n\) on a line, followed by \(n\) lines with \(n\) values on each line. This is a matrix of costs, with the [1,1] position given first. The following is a sample input, which results in the optimal cuts shown in the picture above:

    5
10 22 36 44 50
22 50 70 90 110
36 70 180 190 200
44 90 190 200 230
50 110 200 220 250

    Program Output: The output should consist of just one number on a line by itself, giving the maximum possible value for any sequence of cuts. The output for this example would look like this:

    374

    Program Constraints: Your program must be able to process inputs with values of \(n\) between 1 and 250 in under 10 seconds.