Textbook Exercise:

Suppose youre consulting for a company that manufactures PC equipment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply s~ of equipment (measured in pounds), whi4h has to be shipped by an air freight carrier. Each weeks supply can be carried by one of two air freight companies, AorB. Company A charges a fixed rate r per pound (so it costs r- s~ to ship a weeks supply si). Company B makes contracts for a fixed amount c per week, independent of the weight. However, contracts with company B must be made In blocks of four consecutive weeks at a time. A schedule, for the PC company, is a choice of air freight Company (A or B) for each of the n weeks, with the restriction that company B, whenever it is chosen, must be chosen for blocks of four contiguous weeks at a 0me. The cost of the schedule is the total amount paid to company A and B, according to the description above. Give a polynomial-time algorithm that takes a sequence of supply Sn and returns a schedule of minimum cost. Example. Suppose r = 1, c = 10, and the sequence of values is 11, 9, 9, 12, 12, 12, 12, 9, 9, 11. Then the optimal schedule would be to choose company A for the first three weeks, then company B for a block of four consecutive weeks, and then company A for the final three weeks.

1. (25) [Algorithm design: shipping carrier schedulingl Textbook Exercise 11 in Chapter 6. Show the optimal substructure (with an explanation), give the memoized bottom-up dynamic programming algorithm, and state the resulting running-time complexity (with an explanation). 1. (25) [Algorithm design: shipping carrier schedulingl Textbook Exercise 11 in Chapter 6. Show the optimal substructure (with an explanation), give the memoized bottom-up dynamic programming algorithm, and state the resulting running-time complexity (with an explanation)