Problem 8

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Problem 4 with variables

Due: January 25
Points: 3

In the "airplane bomber" scenario, assume that:

• There are $$q$$ passengers total.
• At least $$r$$ passengers must collude to make a bomb.
• With probability at least $$p$$, not a single passenger will have any bomb-making liquid.

So $$q,r$$ are integers with $$1 \le r \le q$$, and $$p$$ is a real number with $$0 \le p \le 1$$.

Now our randomized algorithm is, given some very carefully-chosen constant $$n$$:

1. Randomly choose $$n$$ passengers to screen.
2. If none of the $$n$$ has any bomb liquid, let the plane fly.
3. If any one of the $$n$$ has any bomb liquid, check all 200 passengers.

Determine a formula for $$n$$ based on $$q$$, $$r$$, and $$p$$, that is simple to compute AND which guarantees that the probability that the plane is successfully bombed is less than one in a million. Use your formula to come up with a big-O bound on $$n$$ in terms of $$q$$, $$r$$, and $$p$$. Choose your formula so that the big-O bound is as small as possible.