18.310 Exam #2: Take Home Part
Due Wednesday, Nov. 28, 2007, on Stellar
Problem 1. 25 points
Write a spreadsheet that, for an input number N of up to 2,000,000, will find a prime (if one exists) in the numbers between N and N + 100. As usual, inputs and outputs should be clearly marked. It should
(1) apply a sieve to eliminate numbers with small prime factors,
(2) apply the probabilistic primality test that uses Fermat's theorem to the remaining numbers to eliminate all but a few candidates.
You should then
(3) also build a spreadsheet which will let you input one of these candidates, and which applies a probabilistic test that screens out Carmichael numbers. (If you want, you can have the spreadsheet input it automatically.)
Problem 2. 25 points
(1) Set up a spreadsheet that calculates the exact probability of finding the best candidate, given that there are N candidates, you see candidates one at a time, and you must accept or reject each one before seeing the next. The spreadsheet should work for N up to 50.
(2) Set up a spreadsheet that calculates the expected value of the optimal strategy in the following situation: you see candidates one at a time, and you must accept or reject each one before seeing the next. You win money only if you choose the best candidate, and if you have looked at k candidates, your reward is k dollars. Again, the spreadsheet should work for N up to 50.
(3) Suppose now that you are rewarded only if you find one of the top two candidates. You are awarded $2000 for finding the best, and $1000 for finding the second best. Set up a spreadsheet which finds the strategy maximizing your expected reward.