Due in class Thursday, 14 February 2008

For this assignment you may write your solutions by hand or type your solutions. There is no programming for this assignment. You may also work with one partner on this assignment. If you work with a partner, you may submit a single assignment with both of your names on the paper. The solution to each problem should be a collaborative effort. Do not simply divide the work into two parts.

Textbook Problems

Write up solutions to the following problems in the textbook.
- R-4.12. If two functions have the same
*asymptotic*growth, indicate this in your solution. - R-4.15, R-4.16, R-4.17, R-4.18, R-4.19. Give a brief explanation of how you arrived at your solution. Can you suggest a asymptotically faster solution to 4.19? If so, explain. Note that these problems refer to code fragment 4.5 on page 183.
- C-4.8, C-4.10, C-4.12
- Analyze the runtime of the
`main`method in the`BirthdayTest.java`in your`labs/w03-analysis`folder. You may assume that**n**is the maximum number of people in the outermost loop. Thus in the code example`for(int i=5; i<=100; i+=5){`, the value of**n**is 100. You can treat the number of experiments as a constant or as another parameter**m**if you want the added challenge of expressing your answer in terms of both**n**and**m**. - C-4.16
**or**C-4.18. For 4.18, how many taste testers do you expect to die?

Submitting

Hand in your nicely handwritten or typed solutions to me at the start of class on Thursday.