Question 1 (Gameshow Strategy, 75 points). Dirk is participating in a gameshow. In this show there are n different challenges. For the ith challenge, Dirk estimates a probability p, that he can pass the challenge (and this is independent of which other challenges he may have done up to this point or their results) and there is a reward R, that he will receive if he successfully completes it. Dirk may attempt the challenges in any order he chooses (though may not try any particular challenge more than once), but once he fails a challenge, he must stop and leave with any award money he has won thus far. (a) Give an On log(n)) time algorithm that given the p; and R, determines the best order for Dirk to attempt these challenges in. Hint: For any two challenges A and B, if Dirk is doing one of them right after the other, which would he rather do first? (b) After a rules change, Dirk is allowed to repeat challenges, but is not allowed to compete in more than k of them total, even if he completes all of them successfully. Give an algorithm that given k, ps and R,. runs in O(kn) time and determines which challenges Dirk should attempt in which order so that he maximize his expected payout. Hint: The answer is not always to do the same challenge k times. Try starting with the last challenge to attempt.

Question 1 (Gameshow Strategy. 75 points). Dirk is participating in a gameshow. In this show there are.n different challenges. For the ith challenge, Dirk estimates a probability p, that he can pass the challenge (and this is independent of which other challenges he may have done up to this point or their results) and there is a rewand Ri that he will recerve if he successfully completes it. Dirk may attempt the challenges in any order he chooses (though may not try any particular challenge more than once), but once he fails a challenge, he must stop and leave with any award money he has won thes far. (a) Give an O(nlog(n)) time algorithm that given the pi and R1 determines the best orier for Dirk to attempt these challenges in. Hint: For any two challenges A and B, if Dirk is doing one of them right after the other, which would he rather do first? [ 40 points] (b) After a rules change, Dirk is allowed to repeat challenges, but is not allowed to compete in more than k of them total, even if he completes all of them successfully. Give an algorithm that given k, pi and Ri, runs in O(kn) time and determines which challenges Dirk should attempt in which order so that he maximizes his expected payout. Hint: The answer is not always to do the same challenge k times. Try starting with the last challenge to attempt. [35 points]