this is everything we have

2. Problem description - Your chance to win big! The College of Engineering invites students like you to participate in a game where you can use your expertise in algorithm design to win lots of money! The setting is as follows: There are n stages in the game in which you are given access ton blue doors and a red doors. During each stage you get to open either the red or the blue door. 1 2 Behind each door there is an amount which you can win if positive) or loose (if negative). Your goal is to choose the doors correctly so that you maximize your earnings. The following rules are imposed by the administration: The game proceeds in stages. So, doors must be opened in the order 1, 2, 3, -- and you can always select either the red or the blue door (but not both). In stage 1, you have to open one of the two doors. However, it is ok if you decide to not select any door in some later stage. - Once you make a selection, next time you must switch color. So, if you picked a red door in the current stage, then in the next one you must pick a blue door (and vice versa). Your goal is to come up with a Dynamic Programming algorithm to solve this problem, subject to the constraints mentioned above. For example, consider the door values shown below. 9 Stage 1 2 3 4 5 6 7 Red 1 -2 -1 4 2 9 -2 Blue 71 5 36 4 Then you can select the shaded doors for a total sum of 7-1+9+9=24 You should implement a Dynamic programming algorithm for this problem, test it for correctness using the test instances that can be found in the class web page and evaluate its performance. 3. Project Implementation You can work in teams of up to two. The teams are expected to accomplice the following goals. Implement your algorithms in JAVA or Python following the conventions below. ON is the number of doors Red, Blue are the arrays of maximum size 10000 holding the amounts behind each door The amounts are integers in the range -1000 to 1000 When your program is called, it should print the maximum sum attained as well as the doors that were selected at the various stages For the example above, your program should print Maximum sum: 24 Doors selected: B1, R3, B4, R6 o basis. So, even if you didn't work on a specific part of the project, you need to be able to answer when asked. Participation and contribution will be examined based on the following table: Worst Criteria Best 5 4 Weight 3 2 1 0 0.5 2 The design of the algorithm (input/output) The recursive formulation of solution (definition of OPT solution) Any special cases (i= 0, 1), etc How items are printed Running time and analysis Compilation without mistakes 0.5 1 1 1 Total /30 o Project report (70%) You must turn in your own work. The report should be well organized and should not contain grammatical mistakes. For full credit, your report should contain the following items: o Title page with course number, project title, team members' names and IDs, date of submission. Use the assignment cover page for that purpose. o Organization and sectioning of the report. Small introduction about the problem you are trying to solve. Detailed design steps including formulation of the DP recurrence, explanation on how you arrived to it. Proof of correctness and justifications for any choices made. o Analysis of the DP algorithm in terms of running time and space requirements. o Testing and screenshots along with a verbal description of the results. O Division of work between members. Each member should be able to explain the algorithm when asked. Conclusions. Academic honesty part (as in the homework problems) References Source code with proper comments. 0 0 0 0