CS35 Lab3: Analysis

Due at the beginning of class Thursday, September 24

Run update35 to get copies of some useful files added to your cs35/lab/3 directory. You will not need to turn in any code this week. Instead you will turn in written solutions to the problems below as well as some graphs showing the results of various running time experiments.

You may work with a partner this week. However, you should work together on each problem rather than each working on only half of the problems. Make sure that both names are on the pages that you hand in.

Solve the following problems from the book
Running time experiments

Perform an experimental analysis that compares the relative running times of the functions you considered in problems R-3.20 through R-3.24.

In running these experiments, you may need to use very different sizes of n, depending on the example being tested. Fast algorithms may not start showing any distinctions until n gets to be greater than 100,000. Slower algorithms may begin showing differences when n is nearer to 100.

In your cs35/lab/3 directory there are some starting point files to help you with this task.

Induction proof

Prove the following relation by induction. Clearly enumerate each step in the proof.