This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
In the "airplane bomber" scenario, we are assuming that:
With this in mind, we came up with the following randomized algorithm:
- Randomly choose n passengers to screen.
- If none of the n has any bomb liquid, let the plane fly.
- If any one of the n has any bomb liquid, check all 200 passengers.
Determine the number of passengers n that must be screened in order to ensure that the probability that the plane is successfully bombed is less than one in a million. Try to make n as small as possible. Show your work!