Note2-AofA: A scientfic Approach
A scientfic Approach
The scientfic method: O-notation, not at all useful for predicting performance
Scientific method calls for tilde-notion. Running time is ~aN^c, an effective path to predicting performance
Common error: Thinking that O-notaion is useful for predicting performance
Galactic algorithms:
R.J.Lipton: A galactic is one that will never be used. An effect would never be noticed in this galaxy. 75% SODA,95% STOC/FOCS are galctic
Steps
- Analyze the algorithm by
- idenfiying anabstractr operation in the inner loop
- Develop a realistic model for input to the program.
- Analyze the frequeny of execution $C_n$ of op for input size N
Hypothsieze that the cost is ~ $aC_n$ where a is a constant
- Validate the hypothesis by
- Developing generator for input according to model.
- Calculate a by running the program for large input.
- Run the program for larger input check the analysis
- Validate the model by testing in application contexts.
Refine and repeat as necessary.
Tilde Notation.
Empirical:
* Run algorithm to solve real algorithm
* Measure running time and/or count operations Challenge: need good implementation
Mathematical:
* Develop mathematical model.
* Analyze algorithm within model Challenge: need good model. need to the math
Scientific:
* Run algorithm to solve real problem
* Check for agreement with model. Challenge: need all of the above.
Drawbacks:
- Model may not be realistic.
- A challenge in any scientific discipline
- Advantage in CS: we can randomize to make the model apply.
- Math may be too difficult
- A challenge in any scientific (c.f statistical physics)
- A “calculus” for AofA is the motivation for this course!
- Experiments may be too difficult.
- Not compared to other scientific disciplines.
- Can’t implement? Why analyze?
symmetry:
$\sum_{1 \leq k\leq N} {C_{k-1}+C_{N-k}}$
both sums are $\sum_{1 \leq k \leq 2} C_{k-1}$
Quicksort compares: limiting distribution is not “normal” “Approximating the Limiting Quicksort Distributution”
Easy Method to Predict Hypothesis: Running time of Quicksort is ~aN in N.
Experiment.
* Run for input size N. Observe running time.
* Could solve for a.
* Predict time for 10N to increase by a factor ..
Validate-refine-analyze cycle
ALGO