2
$\begingroup$

I'm not quite sure how to approach the second part of this problem. Any help is appreciated. Thanks.

You wrote a computer program.

The input to your program is any 400-bit string. You want to make sure that your program is good, that is, that it does not crash on any input.

1.How many possible inputs are there to your program?

Ans: I think the possible outputs is 2^400

You use the following randomized algorithm to test your program:

(a) Choose a 400-bit string r uniformly at random (i.e., each possible string is equally likely to be chosen).
(b) Run your program on input r.
(c) If your program crashes, conclude your program is bad. Otherwise, conclude your program is good.

Suppose your program is bad; for some strange reason, it crashes whenever the input bit-string contains exactly 42 `ones'. What is the probability that the test correctly concludes that your program is bad?

Answer: I'm not quite sure how to approach this. I think that the amount of strings with 42 ones is (400 choose 42). Would I then divide that amount by the total number of bit strings possible, 400? Thanks.

$\endgroup$
  • 1
    $\begingroup$ Yes, since each bit string is equally likely. This is the same as $\frac{\mbox{Num bad cases}}{\mbox{Total num cases}}$. It is also something that can be obtained from a "Binomial random variable" if you know what that is, since $$\frac{400 \choose 42}{2^{400}} = {400 \choose 42} (1/2)^{42} (1/2)^{400-42}$$ $\endgroup$ – Michael Mar 2 '17 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.