Cut Rod Problem — Dynamic Programming

A complete implementation of the classic Rod Cutting Problem from Introduction to Algorithms (CLRS), with three algorithmic approaches and an interactive browser-based visualizer.

---

The Problem

You have a rod of length n inches and a price table that tells you how much each cut length sells for. You want to cut the rod into pieces (or keep it whole) to maximize total revenue.

Length:  1   2   3   4   5   6   7   8   9  10
Price:   1   5   8   9  10  17  17  20  24  30

For a rod of length 4, the best strategy is two pieces of length 2 (5 + 5 = $10), not selling it whole for $9.

This is a classic optimal substructure problem: the best way to cut a rod of length n depends on the best ways to cut shorter rods — making it a perfect fit for dynamic programming.

---

Algorithms

1. Naive Recursion — simple_cut_rod(p, n)

Tries every possible first cut at position i and recurses on the remainder.

def simple_cut_rod(p, n):
    if n == 0:
        return 0
    q = float('-inf')
    for i in range(1, n + 1):
        q = max(q, p[i] + simple_cut_rod(p, n - i))
    return q

Time complexity: O(2ⁿ) — exponential. Each subproblem is recomputed from scratch.

---

2. Top-Down DP with Memoization — memoized_cut_rod(p, n)

Same recursion as above, but caches results in an array r. If r[n] has already been computed, return it immediately.

def memoized_cut_rod(p, n):
    r = [float('-inf')] * (n + 1)
    return _memoized_cut_rod_aux(p, n, r)

Time complexity: O(n²) — each of the n subproblems is solved exactly once.

---

3. Bottom-Up DP — bottom_up_cut_rod(p, n)

Fills a table r[0..n] iteratively from the smallest subproblem up. For each rod length j, tries every first cut i from 1 to j and stores the best result.

def bottom_up_cut_rod(p, n):
    r = [0] * (n + 1)
    for j in range(1, n + 1):
        q = float('-inf')
        for i in range(1, j + 1):
            q = max(q, p[i] + r[j - i])
        r[j] = q
    return r[n]

Time complexity: O(n²) | Space complexity: O(n)

This is the approach animated in the visualizer.

---

Complexity Comparison

Approach	Time	Space	Notes
Naive recursion	O(2ⁿ)	O(n) call stack	Impractical for n > 30
Top-down (memoized)	O(n²)	O(n)	Natural recursive structure
Bottom-up	O(n²)	O(n)	No recursion overhead, cache-friendly

---

Project Files

.
├── cut_rod.py              # Python implementation (all 3 algorithms)
├── visualization.html      # Interactive browser visualizer
└── Cut Rod Problem/
    └── Cut Rod Problem/
        ├── Program.cs      # Original C# implementation
        └── Data.txt        # Price table (33 prices, space-separated)

Data.txt — Price Table

1 5 8 9 10 17 17 20 24 30 33 31 31 31 40 39 20 45 42 46 70 76 77 80 85 90 95 100 110 120 111 200 678

Prices for lengths 1 through 33 inches.

---

Running the Python Version

python3 cut_rod.py

You will be prompted for a rod length. Switch between algorithms by uncommenting the desired line in main():

best_price = memoized_cut_rod(prices, n)   # default
# best_price = bottom_up_cut_rod(prices, n)
# best_price = simple_cut_rod(prices, n)   # slow for n > 25

Example output for n = 10:

Enter number of Inches: 10
Best Revenue is upto : 30
Time Elapsed : 0.000021875s

---

Running the Visualizer

Open visualization.html directly in any modern browser — no server or dependencies needed.

open visualization.html       # macOS
start visualization.html      # Windows
xdg-open visualization.html   # Linux

Controls

Control	Action
Rod Length	Set the rod length (1–25). Resets the animation.
Speed	Adjust playback speed (1× slow → 10× fast).
▶ Play	Run the animation automatically.
⏸ Pause	Pause at the current step.
⏭ Step	Advance one step forward.
⏮ Back	Go one step backward.
↺ Reset	Restart from the beginning.

---

Example: Rod of Length 10

The algorithm finds that the maximum revenue is $30, achieved by keeping the rod uncut (selling the full 10-inch piece at $30).

For a rod of length 7, the optimal is 3 + 4 = $17 (8 + 9 = $17, compared to selling whole for $17 — same either way, but the s-table reveals the first cut chosen).

---

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Section 15.1 — Rod cutting.