Analysis of Algorithms

1.  Scientific method of analyzing algorithm:
  a)  Observe some feature of the natural world.
  b)  Hypothesize a model that is consistent with the observations.
  c)  Predict events using the hypothesis.
  d)  Verify the predictions by making further observations.
  e)  Validate by repeating until the hypothesis and observations agree.

 

2. Knuth prooves that in principle, accurate mathematical models of algorithm analysis are available. Total running time is the sum of cost × frequency for all operations.

 

3. Turing mentioned that we can use some basic operation (most common operation in the algorithm) as a proxy for running time.

 

4.  Tilde notation : Estimate running time (or memory) as a function of input size N. Ignore lower order terms:
  – when N is large, terms are negligible
  – when N is small, we don't care

 

  Technical definition. f(N) ~ g(N) means lim N→ ∞ f (N)/g(N) = 1

 

5.  the small set of functions:
1, log N, N, N log N, N^2, N^3, and 2^N
suffices to describe order-of-growth of typical algorithms.

 

 

6.  An N^2 log N algorithm for 3-SUM problem ( given a list of numbers , try to tell how many triples' sum equals to 0. )

    Sorting-based algorithm.
    a)  Sort the N (distinct) numbers.
    b)  For each pair of numbers a[i] and a[j], binary search for -(a[i] + a[j]).

 

    Analysis. Order of growth is N^2 log N.
    a)  Step 1: N^2 with insertion sort.
    b)  Step 2: N^2 log N with binary search.

 

7.  Commonly-used notations in the theory of algorithms:

 

8.  Algorithm design approach:

  Start:
  a)  Develop an algorithm.
  b)  Prove a lower bound.
  Gap?
  a)  Lower the upper bound (discover a new algorithm).
  b)  Raise the lower bound (more difficult).

 

9. Tilde-notation provide an approximate model of algorithm analysis.

 

10.  Typical memory usage for objects in Java:

    Object overhead: 16 bytes.
    Reference: 8 bytes.
    Padding: Each object uses a multiple of 8 bytes.

 

11.  A String of length N typically uses 40 bytes (for the String object) plus 24 + 2N bytes (for the array that contains the characters) for a total of 64 + 2N bytes.

 

12.  Total memory usage for a data type value:
    a)  Primitive type: 4 bytes for int, 8 bytes for double, …
    b)  Object reference: 8 bytes.
    c)  Array: 24 bytes ( 16 bytes of object overhead, 4 bytes for the length, and 4 bytes of padding) + memory for each array entry.
    d)  Object: 16 bytes + memory for each instance variable + 8 bytes if inner class (for pointer to enclosing class).
    e)  Padding: round up to multiple of 8 bytes.