This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
The State of Delaware sports 3 representatives in the U.S. Congress, out of a total of 541 voting and non-voting members. Based on this, we might expect, on average 3 in every 541 Midshipment to be from Delaware.
(*The number is probably even higher than this, based on the vice president and the general quality of people who grew up in Delaware. If this ratio of approximately 0.55% seems small, compare it to the total population of the state compared to the entire country, which is 917092/315487000, or about 0.29%. Take that, Texas!)
Consider the following algorithm to find a Delawarean midshipman:
def findBlueHen(): M = chooseRandomMidshipman() if M is from Delaware: return M else: return findBlueHen()
Part 1: Write a recurrence to describe the running time of the recursive algorithm. There should be 2 cases, and a probability for each case.
Part 2: Solve your recurrence to determine the expected running time of the algorithm.
Part 3: Part 2 should give you the expected number of recursive calls that the algorithm will make. Call this number of recursive calls n. Use techniques similar to Problem 4 to determine the probability that we have still not found a Delawarean after n recursive calls.