CS35 Lab3: Analysis

Run update35 to get copies of some useful files added to your cs35/labs/03 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.

• C-3.1 on page 138
• C-3.14 on page 140
• C-3.15 on page 140 (tricky). Try the following examples first 1) two bottles, one tester. 2) four bottles, two testers. 3) eight bottles, three testers. Try to generalize your result. Testers need to test a mixture of multiple bottles.
• R-3.20 through R-3.24 on page 137

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/03 directory there are some starting point files to help you with this task.

• There is a Timer class that works like a stop watch. You can start one of these objects before some code for which you want to measure the running time. Then stop it after the code you are measuring, and print the elapsed time.
• There is a test.cpp file that contains a main program that demonstrates how to use the Timer class on a particular problem.
• Note: the examples in the book use integer types for i,j, and n. For some values of n, n*n is larger than the maximum value of an integer. Instead of int n use long long n for your function prototypes and local variables. Note long is repeated twice. The data type is long long
• There is a ex4results file that shows how you can create a text file that is readable by a unix program called xgraph to view your results graphically. Be sure to put your name (or names) in the title and to label the data with an appropriate name. To see the results do:

  xgraph -P ex4results

• To save the graph, choose "Hdcpy", then "Postscript" and "ToFile". By default this file will be called xgraph.ps (you can choose a different name). To print this file do:

  lpr xgraph.ps

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

Home Page