CSC152 2005S, Class 31: Algorithm Analysis Lab
Admin
* No work for Friday
* Don't forget the work for break!
Overview:
* Review
* Lab
* Reflection
* Other notes
About the lab:
* Read the algorithms and analyze them "theoretically"
* Read code to understand how I analyze them experimentally
* Run some experiments and "graph" the results
* Design your own experiments
Review:
* O(f(n)): Intented to model the running time of a method
* Gives the shape of a curve that bounds the running time
* Ignores constant multipliers (c*f(n) is the same as f(n))
* Our goal: Figure out a good curve for each function
* To support that analysis: Experiments
What if our experimental results don't match our predicted running time?
* Our analysis is wrong
* The language does not work the way we expect
* Something we expect to be "constant time" isn't
* Other factors are involved (e.g., some game is running, too)
* Our implementation might not match the actual algorithm
* Our analysis is worst case, most experiments are average case
Do the lab with a partner!
* East meets West
Why is it a constant multiplier?
* We say that it's "constant" if it doesn't depend on n (or x)
* Because "wall clock" time (System.currentTimeMillis()) may
vary from computer to computer, particularly as individual
operations vary in time, we really care only about the shape
of the curve (at least at this point in the analysis)
Why do I get the stupid error message?
* Because Sam has not yet adapted to the new version of Java
WARNING! Before you test sequentialSearch, reload the lab
and make a copy of NewComputer.java. You should probably
build an array of Integer objects.