# Data Structure Questions and Answers – Rod Cutting

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Rod Cutting”.

1. Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
a) Brute force
b) Dynamic programming
c) Recursion
d) Brute force, Dynamic programming and Recursion

Explanation: Brute force, Dynamic programming and Recursion can be used to solve the rod cutting problem.

2. You are given a rod of length 5 and the prices of each length are as follows:

```length     price
1		  2
2		  5
3		  6
4		  9
5		  9```

What is the maximum value that you can get after cutting the rod and selling the pieces?
a) 10
b) 11
c) 12
d) 13

Explanation: The pieces {1,2 2} give the maximum value of 12.

3. Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?
a) O(n2)
b) O(n3)
c) O(nlogn)
d) O(2n)

Explanation: The brute force implementation finds all the possible cuts. This takes O(2n) time.

4. You are given a rod of length 10 and the following prices.

```length     price
1		  2
2		  5
3		  6
4		  9
5		  9
6		  17
7 		  17
8		  18
9		  20
10		  22```
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Which of these pieces give the maximum price?
a) {1,2,7}
b) {10}
c) {2,2,6}
d) {1,4,5}

Explanation: The pieces {2,2,6} give the maximum value of 27.

5. Consider the following recursive implementation of the rod cutting problem:

```#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
max_price = max_of_two(_____________); // subtract 1 because index starts from 0
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

Complete the above code.
a) max_price, prices[i] + rod_cut(prices,len – i – 1)
b) max_price, prices[i – 1].
c) max_price, rod_cut(prices, len – i – 1)
d) max_price, prices[i – 1] + rod_cut(prices,len – i – 1)

Explanation: max_price, prices[i] + rod_cut(prices,len – i – 1) completes the above code.

6. What is the time complexity of the following recursive implementation?

```#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
// subtract 1 because index starts from 0
max_price = max_of_two(max_price, prices[i] + rod_cut(prices,len - i - 1));
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)

Explanation: The time complexity of the above recursive implementation is O(2n).

7. What is the space complexity of the following recursive implementation?

```#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
// subtract 1 because index starts from 0
max_price = max_of_two(max_price, prices[i] + rod_cut(prices,len - i - 1));
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) O(1)
b) O(logn)
c) O(nlogn)
d) O(n!)

Explanation: The space complexity of the above recursive implementation is O(1) because it uses a constant space.

8. What will be the value stored in max_value when the following code is executed?

```#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
// subtract 1 because index starts from 0
max_price = max_of_two(prices[i] + rod_cut(prices,len - i - 1), max_price);
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 3;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) 5
b) 6
c) 7
d) 8

Explanation: The value stored in max_value after the code is executed is equal to 7.

9. For every rod cutting problem there will be a unique set of pieces that give the maximum price.
a) True
b) False

Explanation: Consider a rod of length 3. The prices are {2,3,6} for lengths {1,2,3} respectively. The pieces {1,1,1} and {3} both give the maximum value of 6.

10.Consider the following dynamic programming implementation of the rod cutting problem:

```#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = _____________;
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

Which line will complete the ABOVE code?
a) prices[j-1] + max_val[tmp_idx]
b) prices[j] + max_val[tmp_idx]
c) prices[j-1] + max_val[tmp_idx – 1]
d) prices[j] + max_val[tmp_idx – 1]

Explanation: prices[j-1] + max_val[tmp_idx] completes the code.

11. What is the time complexity of the following dynamic programming implementation of the rod cutting problem?

```#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx];
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(2n)

Explanation: The time complexity of the above dynamic programming implementation of the rod cutting problem is O(n2).

12. What is the space complexity of the following dynamic programming implementation of the rod cutting problem?

```#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx];
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(2n)

Explanation: The space complexity of the above dynamic programming implementation of the rod cutting problem is O(n) because it uses a space equal to the length of the rod.

13. What is the output of the following program?

```#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx];
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) 9
b) 10
c) 11
d) 12

Explanation: The program prints the maximum price that can be achieved by cutting the rod into pieces, which is equal to 27.

14. What is the value stored in max_val[5] after the following program is executed?

```#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx];
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}```

a) 12
b) 27
c) 10
d) 17

Explanation: The value stored in max_val[5] after the program is executed is 12.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]