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.

Write up solutions to the following problems in the textbook.

1. R-4.12. If two functions have the same asymptotic growth, indicate this in your solution.
2. 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.
3. C-4.8, C-4.10, C-4.12
4. 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.
5. C-4.16 or C-4.18. For 4.18, how many taste testers do you expect to die?

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

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:42 AM