This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 7

Problem 2 with variables

Due: January 26
Points: 2

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 \(q\) 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.