Problem 41

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.