5. [Duck Dance-off.] Two dancing duck troupes are having a dance-off. The rules are as follows. There is a dance floor,

[answerhappygod]

5 Duck Dance Off Two Dancing Duck Troupes Are Having A Dance Off The Rules Are As Follows There Is A Dance Floor 1 (51.51 KiB) Viewed 76 times

5. [Duck Dance-off.] Two dancing duck troupes are having a dance-off. The rules are as follows. There is a dance floor, which is laid out as a row of n squares, where n is an even number. Each square has a score (a positive number), which is given by an array D of length n. Each duck receives the score of the square it dances in, and the score for the whole team is the sum of the scores of each dancer in that team. The two dancing duck troupe take turns adding dancers to the dance floor; but the rules are that a new dancer can only join next to an existing dancer, or next to the edge of the dance floor. The two troupes are colored green and white, and green goes first. For example, the following would be a legal dance-off, with a dance-floor-array D (5,7, 3, 4, 4, 6]. -- 5 7 3 4 4 6 Round 1 5 7.3 4.4 6 Round 2 5 7.3 4.4 6 Round 3 5 7.3 4.46 Round 4 5 7 3 4 4 6 Round 5 5 7 3 4 4 6 Round 6 At the end of this dance-off, the green ducks have a score of 5+4 +6 = 15, while the white ducks have a score of 7+3+4 = 14, so the green ducks win. Notice that in the above example, the ducks may not have been using the optimal strategy. For the questions below, "green ducks” refers to the dance troupe that goes first in this dance-off. In this problem, you will design an algorithm to compute the best score that the green ducks can obtain, assuming that the white ducks are playing optimally. Your algorithm should run in time 0(n). (a) What sub-problems will you use in your dynamic programming algorithm? What is the recursive relationship which is satisfied between the sub-problems? [We are expecting: • A clear description of your sub-problems. • A recursive relationship that they satisfy, along with a base case. . An informal justification that the recursive relationship is correct. 1 (b) Write pseudocode for your algorithm. Your algorithm should take as input the array D, and return a single number which is the best score the green team can

achieve. Your algorithm does not need to output the optimal strategy. It should run in time 0(1. We are expecting: Pseudocode AND a clear English description. You do not need to justify that your algorithm is correct, but correctness should follow from your reasoning in part (a).]