4. A different Rod-Cutting Problem Suppose that after solving a rod-cutting problem of the type we studied in class, you know which cuts you need to make in the rod. But there still is a question of the order in which to make the cuts. This might be an issue if the cost to make a cut is proportional to the length of the sub-rod being cut. For example, if rods are very heavy and have to be lifted to a table to do the cut, then some energy (fuel, electricity) must be paid to do the lifting. After a cut, both sub-rods fall to the floor. So we want to figure out an order to do the cuts that minimizes the total cost of the cuts. For example, say in a rod of length 10, the desired cuts are at positions 2, 5, 9. If we do the cuts in left to right order, then we first lift a rod of length 10 (there is nothing we can do to avoid this), and create a rod of length 2 and another of length 8. Then we lift the rod of length 8, and cut so that two rods of length 3 and 5 are created. Then we lift the rod of length 5 and cut to create rods of lengths 4 and 1. So we lifted rods of length 10, 8, 5. But if instead we do the first cut at position 5, then the total lifts will be of length 10, 5 and 5, which is cheaper. You might think that the best policy is to first do the "middle" cut. But what is middle? Is it one that divides the rod into two roughly equal rods, or is it one that splits the number of cut-positions roughly evenly? So, it is not obvious that there is a simple strategy. Instead, we need an algorithnm to find the best order to do the cuts. Problem: Devise recursive logic, and a recursive algorithm to solve this problem. Describe and explain the logic and the recursive algorithm. Ex press and explain Memoized version of the recursive algorithm. Express and explain a DP version of the algorithm. Explain how to do the traceback to actually find the order of the cuts given by the DP solution. Analyze the worst-case number of operations done by the DP algorithm. (This is not the number of cuts, but the number of computational operations done by the DP algorithm.) 4. A different Rod-Cutting Problem Suppose that after solving a rod-cutting problem of the type we studied in class, you know which cuts you need to make in the rod. But there still is a question of the order in which to make the cuts. This might be an issue if the cost to make a cut is proportional to the length of the sub-rod being cut. For example, if rods are very heavy and have to be lifted to a table to do the cut, then some energy (fuel, electricity) must be paid to do the lifting. After a cut, both sub-rods fall to the floor. So we want to figure out an order to do the cuts that minimizes the total cost of the cuts. For example, say in a rod of length 10, the desired cuts are at positions 2, 5, 9. If we do the cuts in left to right order, then we first lift a rod of length 10 (there is nothing we can do to avoid this), and create a rod of length 2 and another of length 8. Then we lift the rod of length 8, and cut so that two rods of length 3 and 5 are created. Then we lift the rod of length 5 and cut to create rods of lengths 4 and 1. So we lifted rods of length 10, 8, 5. But if instead we do the first cut at position 5, then the total lifts will be of length 10, 5 and 5, which is cheaper. You might think that the best policy is to first do the "middle" cut. But what is middle? Is it one that divides the rod into two roughly equal rods, or is it one that splits the number of cut-positions roughly evenly? So, it is not obvious that there is a simple strategy. Instead, we need an algorithnm to find the best order to do the cuts. Problem: Devise recursive logic, and a recursive algorithm to solve this problem. Describe and explain the logic and the recursive algorithm. Ex press and explain Memoized version of the recursive algorithm. Express and explain a DP version of the algorithm. Explain how to do the traceback to actually find the order of the cuts given by the DP solution. Analyze the worst-case number of operations done by the DP algorithm. (This is not the number of cuts, but the number of computational operations done by the DP algorithm.)