idk yet

Question 1

what is the rod cutting problem ?

Answer 1

The rod-cutting problem is the following. Given a rod of length n inches and a
table of prices pi for i , determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces

Question 2

Consider a modification of the rod-cutting problem in which, in addition to a
price pi 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

Answer 2

MODIFIED-CUT-ROD(p, n, c)
1. let r[0..n] be a new array
2. r[0] ← 0
3. for j = 1 to n
4. q ← p[j] // No cut: use whole rod
5. for i = 1 to j - 1
6. q ← max(q, p[i] + r[j - i] - c)
7. r[j] ← q
8. return r[n]

Question 3

What is the psdeocode for LCS-length?

Answer 3

LCS-LENGTH(X, Y)
1. m ← length(X)
2. n ← length(Y)
3. create tables b[1..m, 1..n] and c[0..m, 0..n]
4. for i = 1 to m
5. c[i, 0] ← 0
6. for j = 0 to n
7. c[0, j] ← 0
8. for i = 1 to m
9. for j = 1 to n
10. if X[i] == Y[j]
11. c[i, j] ← c[i-1, j-1] + 1
12. b[i, j] ← “↖”
13. else if c[i-1, j] ≥ c[i, j-1]
14. c[i, j] ← c[i-1, j]
15. b[i, j] ← “↑”
16. else
17. c[i, j] ← c[i, j-1]
18. b[i, j] ← “←”
19. return c and b

Question 4

What is the pseudocode for extended bottom-up ?

Answer 4

EXTENDED-BOTTOM-UP-CUT-ROD(p, n):
1. r[0..n] = 0 // Maximum revenue for rod length 0
2. s[0..n] = 0 // First cuts for each rod length
3. for j = 1 to n:
4. q = -∞
5. for i = 1 to j:
6. if q < p[i] + r[j - i]:
7. q = p[i] + r[j - i]
8. s[j] = i
9. r[j] = q
10. return r and s

Question 5

what’s the memonic for extened bottom up algorithm

Answer 5

Really Smart People Solve Every Rod”

This will help you remember the key parts of the algorithm:

Really: Remember to initialize r[0] = 0 (base case for zero-length rod).

Smart: Set up the s[0..n] array for storing the first cuts.

People: Process rod lengths from 1 to n (outer loop) — for each possible rod length.

Solve: Search for the best cut by iterating over possible cuts (1 to j).

Every: Evaluate if the current revenue from a cut is better than the previous maximum (q < p[i] + r[j-i]).

Rod: Record the best cut s[j] = i and the maximum revenue r[j] = q

Question 6

given a table of :
length: 1 2 3 4 5 6
price: 1 5 8 9 10 13

what is r?

Answer 6

r= 0 1 2 3 4 5 6
0 1 5 8 9 10 13