[FrontPage] [TitleIndex] [WordIndex] 

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. From RosenBook

Do Exercises 4.4.20, 5.2.10, 6.4.20, and 6.4.34.

2. Not from RosenBook

Homer Simpson obtains a box of n donuts and eats k of them, chosen uniformly at random. Little did he know that r of the donuts were poisoned.

  1. What is the probability that Homer ate at least one poisoned donut, as a function of n, k, and r?
  2. The police pick one of the n-k remaining donuts uniformly at random and test it for poison. What is the probability that this donut is poisoned, as a function of n, k, and r?

  3. Suppose that the tested donut was poisoned. What is the probability that Homer ate at least one poisoned donut, conditioned on this fact?

2014-06-17 11:57