- R-3.7
- R-3.20, R-3.21, R-3.22, R-3.23, R-3.24 Show how you computed big-Oh for each problem.
- C-3.1
- C-3.14
- C-3.20
- P-3.2 You can use an instance of the
StopWatch class to time the execution of each
loop. Be sure to time only the loop itself and not the entire
method. Copy the code from
~newhall/public/cs35/week3/to get an idea of how to use this class to time your Java code.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.
You should turn in tables and graph(s) showing the results of your experiments; for each method, plot its runtime for different values of n. On the Sun machines, you can use xgraph to draw the graph(s). Here is some information about using xgraph: xgraph. Here is a sample data file for xgraph: data_file. You can create a postscript version of the graph drawn by xgraph by selecting the "Hardcopy" menu option and specifying the "Postscript" and "To File" Hardcopy options.
Use ghostview to view a postscript file:
ghostview filename.ps
Use lpr to print a postscript file to the laser printer in the Sun lab:lpr filename.ps
or to print two pages per sheet of paper:mpage -2 -M-10 -dp filename.ps | lpr
Group the functions according to their order of growth. For example, all O(n) functions should appear together in a single graph.
