Homework 4

1. Exercises 15.1-1
   Show that follows from and the initial condition .

   • 第十二組

2. Exercises 15.1-2
   Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p_i / i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n - i.

   • 第一組

3. Exercises 15.1-3
   Consider a modification of the rod-cutting problem in which, in addition to a price p_i for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.

   • 第十五組

4. Exercises 15.1-4, unit05-演算法.pdf p12
   Modify M_Cut-Rod to return not only the value but the actual solution, too.

   • 第七組

5. Exercises 15.2-1
   Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is《5, 10, 3, 12, 5, 50, 6》.

   • 第四組