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.