Homework 6

Assigned November 8, due November 14

This homework covers the material in chapters 11, 12, and 13 of the textbook and includes a special problem on the run time of algorithms.

1. The instructions for this problem are in the following files:
   Instructions (postscript)
   Instructions (pdf)
   code
   (10 points)

2. Do exercise 11.1-2 on page 203. (10 points)

3. Do exercise 11.1-5 on page 203. (10 points)

4. Do exercise 11.1-6 on page 203. (10 points)

5. Do problem 11-1 on page 216. (10 points)

6. Do exercise 13.1-2 on page 246. (10 points)

7. Suppose that we are given 13 golf balls, one of which is heavier than the rest, and a balancing scale. Design a procedure that finds the heavy ball using an expected number of weighings that is less than 2.5. Explain why the expected number of weighings for your procedure is less than 2.5 and give an equation for the expected number of weighings. (10 points)

Gerry Brady
Thu Nov 8 12:02:10 CST 2001