# Data Structure Questions and Answers-Rod Cutting

## Click on any option to know the CORRECT ANSWERS

 Question 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 All of the mentioned

Question 1 Explanation:
All the methods mentioned above can be used to solve the rod cutting problem.

 Question 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

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

 Question 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)

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

 Question 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

Which of these pieces give the maximum price?

 A {1, 2, 7} B {10} C {2, 2, 6} D {1, 4, 5}

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

 Question 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)