CS 237, Fall 2007

Date Due: Tuesday, September 25

Reading: None

Problems:

1. Page 17, #1.16

2. Page 18, #1.21

3. Suppose you have a bin with 9 white and 3 black balls. You randomly draw 3 balls from the bin, one after the other.

(i). What is the probability that all three are white ?

(ii). What is the probability that 2 are white and one is black ?

4. In a particular school of 25% of the students got an A in math, 15% had an A in CS, and 10% had an A in both.

(i). If a student got an A in CS, what is the probability she also had an A in math ?

(ii). If a student got an A in math, what is the probability she also had an A in CS ?

(iii). What is the probability that the student had an A in either math or CS ?

(iv). What is the probability that a student got an A in neither math nor CS ?

5. Let A and B be events with pr(A) = 0.4 and pr(A union B) = 0.7

Find pr(B) if, (i). A and B are independent

(ii). A and B are disjoint

(iii). A is a subset of B

6. Assume we are solving the database contention problem discussed in class. So we have n processes, each trying to access a database with some fixed probability p at each round of our algorithm.

Let S(i,t) be the event that process i succeeds during round t of the algorithm.

(i). Explain why pr(S(i,t)) = p (1-p) ^n-1.

(ii). We would like to find which value of p, p between 0 and 1, makes pr(S(i,t)) maximal.

For p between 0 and 1, sketch the graph of the the function f(p) = pr(S(i,t)). What is the max value of f(p)?

(Hint: Find f's max value by taking the derivative of f(p) and finding the max value of f(p) by determining that value at the p where the derivative is 0.)