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

  1. 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

  2. Hypothsieze that the cost is ~ $aC_n$ where a is a constant

  3. 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
  4. 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:

  1. Model may not be realistic.
    • A challenge in any scientific discipline
    • Advantage in CS: we can randomize to make the model apply.
  2. Math may be too difficult
    • A challenge in any scientific (c.f statistical physics)
    • A “calculus” for AofA is the motivation for this course!
  3. 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

Archive

Dialogue & Discussion