This problem set covers contents of sections 15.1, and 15.2. To solve the proble

ID: 3604432 • Letter: T

Question

This problem set covers contents of sections 15.1, and 15.2. To solve the problems you will use dynamic programming method. Dynamic programming method avoids repeated computation for same input size by storing the results in the memory, which is know as space-time tradeoff or memory-time tradeoff. This can be done using top-down recursive algorithms or bottom-up iterative algorithms. Let us use a small rod-cutting problem to illustrate a bottom-up method. The Table below shows price of a rod for a given length. Unit does not matter as long as we have prices and revenues are for the same unit of length. ngth i1 2 345 Price 15 8 9 10 esi 15 8 10 13 Table 1: Price table for rods. The BOTTOM-UP-CUT-ROD(P, N) algorithm is used for creating the table shown below. Two rows ia and ib are for iteration i the outer-loop. Rows i show symbolic values and ib show the numerical values. Max revenue 2b 3b 4a 4b 9 10 9 10 5b 13 13 10 10 13 Table 2: Trace of the bottum-up algorithm. 1. For the rod prices shown in Table 3 create a computation table similar to Table 2. 6 789 10 2611 10 1224232533 40 Price pi Table 3: Price table for rods, and corresponding maximum revenue for a given length

Explanation / Answer

Since there are multiple questions answering only the first one.

Max revenue

p(1)+r(0)

p(1)+r(1)

p(2)+r(0)

p(1)+r(2)

p(2)+r(1)

p(3)+r(0)

p(1)+r(3)

p(2)+r(2)

p(3)+r(1)

p(4)+r(0)

p(1)+r(4)

p(2)+r(3)

p(3)+r(2)

p(4)+r(1)

p(5)+r(0)

p(1)+r(5)

p(2)+r(4)

p(3)+r(3)

p(4)+r(2)

p(5)+r(1)

p(6)+r(0)

p(1)+r(6)

p(2)+r(5)

p(3)+r(4)

p(4)+r(3)

p(5)+r(2)

p(6)+r(1)

p(7)+r(0)

p(1)+r(7)

p(2)+r(6)

p(3)+r(5)

p(4)+r(4)

p(5)+r(3)

p(6)+r(2)

p(7)+r(1)

p(8)+r(0)

p(1)+r(8)

p(2)+r(7)

p(3)+r(6)

p(4)+r(5)

p(5)+r(4)

p(6)+r(3)

p(7)+r(2)

p(8)+r(1)

p(9)+r(0)

p(1)+r(9)

p(2)+r(8)

p(3)+r(7)

p(4)+r(6)

p(5)+r(5)

p(6)+r(4)

p(7)+r(3)

p(8)+r(2)

p(9)+r(1)

p(10)+r(0)