You are working in a reputable investment firm. Having money from many investors all over the...

 

Transcribed Image Text:

You are working in a reputable investment firm. Having money from many investors all over the world, they would like to invest them in deals and assets that maximize their profit. They managed to collect a database of promising deals from all over the world, in which they can invest; then, their analysis team managed to accurately estimate the expected profit for each deal, so that each deal, D₁, has now the expected profit, Pi, and the required investment value to invest in such deal, Vi-that is if they paid Vi, it is expected to have a profit of P₁. Currently, they have decided to invest with a maximum budget B. Therefore, they want to make sure they gain the maximum possible profit. The problem is that database is quite huge with many deals, that no human can decide which deals to invest in to maximize the profit, and what that maximum profit is. Knowing you are studying Algorithms course, they needed your help. a) Design a recursive algorithm that takes as input list of tuples of (Vi, Pi) and maximum budget, B, and outputs the maximum possible profit [7 Points] Example, if we got the array of the below table, your algorithm should output 20; this happens by investing in deals 1&4 b) Empirically, show the performance curve of the algorithm using time measurements [3 Points] c) Adjust your algorithm to return a list of deal indices that achieve that maximum profit, while adjusting it to minimize the invested budget as well. Therefore, if there were many set of deals achieving the maximum profit, the algorithm favors the one with the least investment value. [2 Bonus Points] B = 10 Deal Number Investment Value (V₁) | Expected Profit (P₁) 0 1 2 3 4 5 6 2 5 3 8 5 2 2 Max Total Expected Profit: 20 1 10 7 13 10 1 1 You are working in a reputable investment firm. Having money from many investors all over the world, they would like to invest them in deals and assets that maximize their profit. They managed to collect a database of promising deals from all over the world, in which they can invest; then, their analysis team managed to accurately estimate the expected profit for each deal, so that each deal, D₁, has now the expected profit, Pi, and the required investment value to invest in such deal, Vi-that is if they paid Vi, it is expected to have a profit of P₁. Currently, they have decided to invest with a maximum budget B. Therefore, they want to make sure they gain the maximum possible profit. The problem is that database is quite huge with many deals, that no human can decide which deals to invest in to maximize the profit, and what that maximum profit is. Knowing you are studying Algorithms course, they needed your help. a) Design a recursive algorithm that takes as input list of tuples of (Vi, Pi) and maximum budget, B, and outputs the maximum possible profit [7 Points] Example, if we got the array of the below table, your algorithm should output 20; this happens by investing in deals 1&4 b) Empirically, show the performance curve of the algorithm using time measurements [3 Points] c) Adjust your algorithm to return a list of deal indices that achieve that maximum profit, while adjusting it to minimize the invested budget as well. Therefore, if there were many set of deals achieving the maximum profit, the algorithm favors the one with the least investment value. [2 Bonus Points] B = 10 Deal Number Investment Value (V₁) | Expected Profit (P₁) 0 1 2 3 4 5 6 2 5 3 8 5 2 2 Max Total Expected Profit: 20 1 10 7 13 10 1 1

Answer rating: 100% (QA)

a Design a recursive algorithm that takes as input list of tuples of Vi P and maximum budget B and outputs the maximum possible profit 7 Points Example if we got the array of the below table your algo... View the full answer