# 15.1 Rod cutting

## 15.1-1

Show that equation $\text{(15.4)}$ follows from equation $\text{(15.3)}$ and the initial condition $T(0) = 1$.

• For $n = 0$, this holds since $2^0 = 1$.
• For $n > 0$, substituting into the recurrence, we have

\begin{aligned} T(n) & = 1 + \sum_{j = 0}^{n - 1} 2^j \\ & = 1 + (2^n - 1) \\ & = 2^n. \end{aligned}

## 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 \le i \le n$, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n - i$.

The counterexample:

$$\begin{array}{c|cccc} \text{length i} & 1 & 2 & 3 & 4 \\ \hline \text{price p_i} & 1 & 20 & 33 & 36 \\ p_i / i & 1 & 10 & 11 & 9 \end{array}$$

## 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.

We can modify $\text{BOTTOM-UP-CUT-ROD}$ algorithm from section 15.1 as follows:

MODIFIED-CUT-ROD(p, n, c)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
q = p[j]
for i = 1 to j - 1
q = max(q, p[i] + r[j - i] - c)
r[j] = q
return r[n]


We need to account for cost $c$ on every iteration of the loop in lines 5-6 but the last one, when $i = j$ (no cuts).

We make the loop run to $j - 1$ instead of $j$, make sure $c$ is subtracted from the candidate revenue in line 6, then pick the greater of current best revenue $q$ and $p[j]$ (no cuts) in line 7.

## 15.1-4

Modify $\text{MEMOIZED-CUT-ROD}$ to return not only the value but the actual solution, too.

MEMOIZED-CUT-ROD(p, n)
let r[0..n] and s[0..n] be new arrays
for i = 0 to n
r[i] = -∞
(val, s) = MEMOIZED-CUT-ROD-AUX(p, n, r, s)
print "The optimal value is" val "and the cuts are at" s
j = n
while j > 0
print s[j]
j = j - s[j]

MEMOIZED-CUT-ROD-AUX(p, n, r, s)
if r[n] ≥ 0
return r[n]
if n == 0
q = 0
else q = -∞
for i = 1 to n
(val, s) = MEMOIZED-CUT-ROD-AUX(p, n - i, r, s)
if q < p[i] + val
q = p[i] + val
s[n] = i
r[n] = q
return (q, s)


## 15.1-5

The Fibonacci numbers are defined by recurrence $\text{(3.22)}$. Give an $O(n)$-time dynamic-programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?

FIBONACCI(n)
let fib[0..n] be a new array
fib[0] = 1
fib[1] = 1
for i = 2 to n
fib[i] = fib[i - 1] + fib[i - 2]
return fib[n]


There are $n + 1$ vertices in the subproblem graph, i.e., $v_0, v_1, \dots, v_n$.

• For $v_0, v_1$, each has $0$ leaving edge.
• For $v_2, v_3, \dots, v_n$, each has $2$ leaving edges.

Thus, there are $2n - 2$ edges in the subproblem graph.