Question

This homework is due on gradescope Friday March 3rd at 11:59pm on gradescope. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in LTE​Xis recommend though not required.

Question 1 (Gameshow Again). Dirk's gameshow from Homework 4 decides to change their rules again. Now Dirk can attempt at most k challenges but cannot attempt the same challenge more than once. Give an O(nlog(n)+kn) algorithm to find the strategy that optimizes Dirk's expected winnings. Hint: Based on the solution to part (a) from the previous problem you can note that whatever challenges Dirk attempts to try, he should always attempt them in decreasing order of pi​Ri​/(1−pi​) (with the order not mattering if there are ties). You can assume this without proof.

Answer 1

To optimize Dirk's expected winnings, use an O(nlog(n)+kn) algorithm that sorts challenges and attempts them based on their ratio of potential winnings to potential losses.

Step-by-step explanation:

To find the strategy that optimizes Dirk's expected winnings, you can use an O(nlog(n)+kn) algorithm. Here are the steps:

1. Calculate the value of pi​Ri​/(1−pi​) for each challenge, which represents the ratio of potential winnings to potential losses for each challenge.
2. Sort the challenges in decreasing order based on the calculated ratio.
3. Starting with the challenge with the highest ratio, attempt each challenge in order as long as Dirk has not reached the maximum number of attempts for the overall game and has not attempted the same challenge before.
4. Continue attempting challenges until Dirk has reached the maximum number of attempts or has attempted all available challenges.

This algorithm ensures that Dirk prioritizes challenges with higher potential winnings compared to potential losses. By attempting challenges in decreasing order of the ratio, Dirk can optimize his expected winnings.