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
View Answer

Answer: d
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
View Answer

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

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)
View Answer

Answer: d
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}
View Answer

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

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

advertisement
#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)
View Answer

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

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)
View Answer

Answer: d
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!)
View Answer

Answer: a
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
View Answer

Answer: c
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
View Answer

Answer: b
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]
View Answer

Answer: a
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)
View Answer

Answer: c
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)
View Answer

Answer: b
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
View Answer

Answer: d
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
View Answer

Answer: a
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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.