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.