代做CSC 317 Data Structures And Algorithm Analysis Homework set #8代做Statistics统计

Homework set #8

CSC 317 Data Structures And Algorithm Analysis

To solve these problems you will use dynamic programming method. Dynamic programming  method avoids repeated computation of an optimal solution for the same subset of inputs by storing in memory an optimal solution obtained for it for the first time; this is known 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 1 below shows the 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.

Table 1: Price table for rods.

The BOTTOM-UP-CUT-ROD(P, N) algorithm is used for creating Table 2 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.

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.

Table 3: Price table for rods and corresponding maximum revenue for a given length.

2.  Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is < 6, 7, 8, 3, 10, 6 >. Show both m and s tables.