« Lecture #Syllabus for all sect | Main | Schedule Syllabus for all sect »

March 29, 2006

Homework Syllabus for all sect

1. Perform BTest(a=4, n=15), where BTest() is the test employed in the Miller-Rabin algorithm for primality testing. 4 is a known false witness for 15. What does your result using BTest indicate? (For section 001, note that we saw this exact situation in class today).

2. If a Monte Carlo algorithm A for a problem with two possible outcomes is 0.51-correct and the negative (false) outcome can be accepted with certainty, how many times do you need to try A with only positive (true) outcomes in order to be certain with probability 1-10^-10 of a positive answer? (Hint: The following logarithmic identity may be useful for you: log_b(x) = log_k(x) / log_k(b) , where you read log_b(k) as "log base b of k")

Posted by ringger at March 29, 2006 02:39 PM

Comments

just a thought. The logarithmic identity is a little confusing (i.e. where'd the x come from?) should it read: log_b(x) = log_k(x)/log_k(b). That's an identity I'm more familiar with.

Posted by: mfarley5 [TypeKey Profile Page] at March 30, 2006 10:59 PM

Good catch. Your correction is the intended identity. I went ahead and updated the text of the assignment. Hopefully not too late for some students.

Posted by: ringger [TypeKey Profile Page] at March 31, 2006 07:19 AM

Post a comment

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


Remember me?