Due at the beginning of class Thursday, February 11

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.

Solve the following problems from the book

- 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

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/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

Induction proof

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