There are two parallel lines of apples, Line 0 and Line 1, each of length T...

  

Transcribed Image Text:

There are two parallel lines of apples, Line 0 and Line 1, each of length T meters. In each line, every 1 meter there is either: a good apple or a bad apple For example, if N = 11, the lines might look like the figure below: Meter: 1 2 3 4 5 67 8 9 10 11 Line 0: Line 1: You are designing an apple collecting robot. Your robot starts at meter 1 of Line 0, and then slowly moves to the right, collecting apples along the way. The robot can switch between the lines, but at each meter, it can collect only one apple. More precisely, if the robot switches from Line 0 to Line 1 at meter 4, then it collects the apple at Line 1 (and not the apple at Line 0). Your goal is for the robot to collect as many good apples as possible. However, switching between Lines 0 and 1 costs a lot of energy for your robot, and so your robot can only switch from one line to the other at most s times. For a concrete example, suppose in the example above that the robot starts in Line 0 and can switch at most two times (s=2). It might decide to switch at meter 4 (from Line 0 to Line 1) and again at meter 9 (from Line 1 to Line 0). In total, it collects 9 good apples. It is happy. Now, suppose that the two lines of apples are visible to the robot and that s is known. The "data" (the lines of apples) are given as a 2D array X, where, for meters m = 1,2,..., N and lines j = 0, 1, we have X[j, m] = if Line j has a good apple at meter m; 0 if Line j has a bad apple at meter m. In this problem, we will use dynamic programming to devise an algorithm for collect- ing the optimal number of good apples; here, "optimal" means maximum. To get you started, consider the following subproblem: The optimal number of good apples that can be collected when starting in Line j at meter m and going till the end (meter N) when k more switches are possible. (a) Using the subproblem suggested above, write a recurrence to express the optimal reward (number of collected good apples) of a larger problem in terms of the optimal reward of subproblems. (b) Using your recurrence, write a dynamic programming algorithm for finding the optimal reward when starting at meter 1 of Line 0 with a budget of s 20 switches. It is ok if your algorithm does not have an efficient runtime. In dynamic programming, there is a clever trick called "memoization" (we will learn about it later in the course) which ensures that a given algorithm never makes the same recursive call twice (i.e., once it has obtained the optimal reward for a subproblem, it stores it and neve recomputes it again). (c) Once you have filled the table of optimal rewards for subproblems, describe a way to figure out in exactly which meters the robot should switch. That is, construct an optimal solution. There are two parallel lines of apples, Line 0 and Line 1, each of length T meters. In each line, every 1 meter there is either: a good apple or a bad apple For example, if N = 11, the lines might look like the figure below: Meter: 1 2 3 4 5 67 8 9 10 11 Line 0: Line 1: You are designing an apple collecting robot. Your robot starts at meter 1 of Line 0, and then slowly moves to the right, collecting apples along the way. The robot can switch between the lines, but at each meter, it can collect only one apple. More precisely, if the robot switches from Line 0 to Line 1 at meter 4, then it collects the apple at Line 1 (and not the apple at Line 0). Your goal is for the robot to collect as many good apples as possible. However, switching between Lines 0 and 1 costs a lot of energy for your robot, and so your robot can only switch from one line to the other at most s times. For a concrete example, suppose in the example above that the robot starts in Line 0 and can switch at most two times (s=2). It might decide to switch at meter 4 (from Line 0 to Line 1) and again at meter 9 (from Line 1 to Line 0). In total, it collects 9 good apples. It is happy. There are two parallel lines of apples, Line 0 and Line 1, each of length T meters. In each line, every 1 meter there is either: a good apple or a bad apple For example, if N = 11, the lines might look like the figure below: Meter: 1 2 3 4 5 67 8 9 10 11 Line 0: Line 1: You are designing an apple collecting robot. Your robot starts at meter 1 of Line 0, and then slowly moves to the right, collecting apples along the way. The robot can switch between the lines, but at each meter, it can collect only one apple. More precisely, if the robot switches from Line 0 to Line 1 at meter 4, then it collects the apple at Line 1 (and not the apple at Line 0). Your goal is for the robot to collect as many good apples as possible. However, switching between Lines 0 and 1 costs a lot of energy for your robot, and so your robot can only switch from one line to the other at most s times. For a concrete example, suppose in the example above that the robot starts in Line 0 and can switch at most two times (s=2). It might decide to switch at meter 4 (from Line 0 to Line 1) and again at meter 9 (from Line 1 to Line 0). In total, it collects 9 good apples. It is happy. Now, suppose that the two lines of apples are visible to the robot and that s is known. The "data" (the lines of apples) are given as a 2D array X, where, for meters m = 1,2,..., N and lines j = 0, 1, we have X[j, m] = if Line j has a good apple at meter m; 0 if Line j has a bad apple at meter m. In this problem, we will use dynamic programming to devise an algorithm for collect- ing the optimal number of good apples; here, "optimal" means maximum. To get you started, consider the following subproblem: The optimal number of good apples that can be collected when starting in Line j at meter m and going till the end (meter N) when k more switches are possible. (a) Using the subproblem suggested above, write a recurrence to express the optimal reward (number of collected good apples) of a larger problem in terms of the optimal reward of subproblems. (b) Using your recurrence, write a dynamic programming algorithm for finding the optimal reward when starting at meter 1 of Line 0 with a budget of s 20 switches. It is ok if your algorithm does not have an efficient runtime. In dynamic programming, there is a clever trick called "memoization" (we will learn about it later in the course) which ensures that a given algorithm never makes the same recursive call twice (i.e., Now, suppose that the two lines of apples are visible to the robot and that s is known. The "data" (the lines of apples) are given as a 2D array X, where, for meters m = 1,2,..., N and lines j = 0, 1, we have X[j, m] = if Line j has a good apple at meter m; 0 if Line j has a bad apple at meter m. In this problem, we will use dynamic programming to devise an algorithm for collect- ing the optimal number of good apples; here, "optimal" means maximum. To get you started, consider the following subproblem: The optimal number of good apples that can be collected when starting in Line j at meter m and going till the end (meter N) when k more switches are possible. (a) Using the subproblem suggested above, write a recurrence to express the optimal reward (number of collected good apples) of a larger problem in terms of the optimal reward of subproblems. (b) Using your recurrence, write a dynamic programming algorithm for finding the optimal reward when starting at meter 1 of Line 0 with a budget of s 20 switches. It is ok if your algorithm does not have an efficient runtime. In dynamic programming, there is a clever trick called "memoization" (we will learn about it later in the course) which ensures that a given algorithm never makes the same recursive call twice (i.e., once it has obtained the optimal reward for a subproblem, it stores it and neve recomputes it again). (c) Once you have filled the table of optimal rewards for subproblems, describe a way to figure out in exactly which meters the robot should switch. That is, construct an optimal solution. once it has obtained the optimal reward for a subproblem, it stores it and neve recomputes it again). (c) Once you have filled the table of optimal rewards for subproblems, describe a way to figure out in exactly which meters the robot should switch. That is, construct an optimal solution.

Answer rating: 100% (QA)

Understanding the Problem The robot moves on two parallel lines Line 0 and Line 1 of apple trees each T meters long Every meter on a line has either a ... View the full answer