= (5) At a fair, there is a game with n balloons that are placed adjacent to each other in a line. In this game, you must shoot all the balloons. Each balloon i E 1, ..., n has an award v(i). If you shoot ith balloon you will get an award of v(i 1)v(i)v(i + 1) unless the left or right balloon is missing (which is the case for the balloons on the ends of the line). In the case that left (or right) neighbor is missing, let vi 1) = 0 (or vi + 1) 0). When balloon i is shot, the balloons to the right of balloon i decrease their position by 1 and their awards remain the same. You have to shoot all balloons in some order so that you score a maximum total number of points. (a) Does the strategy For the remaining balloons at each step, shoot the balloon with highest value work? (b) Does the strategy "For the remaining balloons at each step, shoot the balloon with highest award at that point in time work? (c) Devise a dynamic programming method to determine an optimal order in which to shoot the balloons. Make the algorithm as efficient as possible. = (5) At a fair, there is a game with n balloons that are placed adjacent to each other in a line. In this game, you must shoot all the balloons. Each balloon i E 1, ..., n has an award v(i). If you shoot ith balloon you will get an award of v(i 1)v(i)v(i + 1) unless the left or right balloon is missing (which is the case for the balloons on the ends of the line). In the case that left (or right) neighbor is missing, let vi 1) = 0 (or vi + 1) 0). When balloon i is shot, the balloons to the right of balloon i decrease their position by 1 and their awards remain the same. You have to shoot all balloons in some order so that you score a maximum total number of points. (a) Does the strategy For the remaining balloons at each step, shoot the balloon with highest value work? (b) Does the strategy "For the remaining balloons at each step, shoot the balloon with highest award at that point in time work? (c) Devise a dynamic programming method to determine an optimal order in which to shoot the balloons. Make the algorithm as efficient as possible