CS35 Lab #3: Algorithmic Analysis

Due in class Wednesday, 11 February 2008

For this assignment you may write your solutions by hand or type your solutions. There is only one small programming component for this assignment and you do NOT need to submit this code. You may dicuss the problems with your classmates, but you should write up the solutions on your own. It will be important that you understand this material as we move foward in the course.

Textbook Problems

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
  4. C-4.18. How many taste testers do you expect to die?
  5. Prove that the product of two odd integers is odd.

Programming Experiment

In the homework/03 folder, there are two java programs, Factorial.java and StopWatch.java, both of which we have explored in class. Factorial.java calculates n! using either iteration (e.g., a loop) or recursion. Both of these algorithms have the same asymptotic runtime. What is it?

Since they have the same aysmptotic runtime, should they also have the same empirical runtime? Yes or no? Test you hypothesis by using a StopWatch object in the main() method of Factorial.java. You should try a couple values of n (e.g., n = 1000, 2000, ..., 5000). For this experiment, plot your results on a graph where the x-axis is n and the y-axis is empirical runtime.

For each of the two algorithms, does the empirical runtime match the asymptotic runtime? (e.g., refer to the Big-Oh Definition, what are c and n_0?) Is one of these two algorithms faster? If so, which one? Why do you think it is faster?

(For this problem, you need not submit your code.)

Submitting

Hand in your nicely handwritten or typed solutions to me at the start of class on Wednesday. Illegible solutions will be marked down despite correctness.