Note1-AofA: From AofA to AC

This is an introduce lecture on Analysis of Algorithms. I will show the history and progress having made in the past, from Knuth’s scientific method, to Theory of Algorithm, and then to the current Analytic Combinatorial. We can get a general picture from this lecture.

#Introduction

Classic AofA Steps:

  1. Develop recurrence relation
  2. Derive GF equation
  3. Extract coefficients
  4. Asymptotics:Develop approximation

Context

Mathematics need

  1. Recurrence
  2. Genretating Function
  3. Asymptotics
  4. Trees
  5. Permutations
  6. Strings and Tries
  7. Words and Maps

Ultimate Goal: Automatic Analysis

Analysis of Algorithm(1995) -> INRIA tech reports -> Analytic Combinatorics In principle, classical methods can provide

* full detials.
* full and accurate asymptotic estimates

In practice, it is ofter possible to

* generalize specialized derivations
* skip details and move directly to accurate asymptotics

Knuth: The Art of Computer Programming

To analyze an algorithm:

* Develop a good implementation and a realistic input mode
* Determine the caose and execution frequency of each operation.
* Calculate the total running time
* Run experiments to validate model and analysis  Beni: 

* Scientific foundation for AofA.
* Can predict performance and compare algorithms

Drawbacks:

* Model may be unrealistic.
* Excessive detail likely in the analysis

Theory of Algorithms (AHU 1970,CLRS)

To address Knuth drawbacks:

* Analyze worst-case cost [takes model out of the picture]
* Use O-notation for upper bound [takes detail out of analysis]
* Classify algorithms by these costs

Beni:

* Enable a new Age of Algorithm Design

Drawbacks:

* Analysis is often unsuitable for scientific studies (often overlooked)

Analytic combinatorics

can provide a basis for scitenfic studies.

* A calculus for developing models.
* Universal laws that encompass the detail in the analysis

Quantitative study of large combinatorial structures. Generating fuctions are the central object of study

AC Basic process:

1. Defin a combinatorial construction that precisely sepcifies the structure.
2. Use a symbolic transfer theorem to derive a GF equation.
3. Use an analytic transfer theorem to extract coefficient asymptotics

Combinatorial constructions:

* Algeraic formular built from natural combinatorial operators
* Operands are atoms or other combinatorial constructsions
* Two cases: atoms are unlabelled or labelled (all different)i ### Generating functions:
* controverial for some time. no particular meaning
symbolic meyhods: OGFs,EGFs,MGFs

Extract coefficients asymptotics

analytic transfer theorems based on GF as complex function.
Complex Asympotics: Singularity Analysis, Saddle Pointi [Asmptotiv
Counting,Moments of paramenters]
=> Random Structures: Multivarite Asymptotics, Singularity
Perturbation.[limit laws,Large Deviations]

combinatorial structures:

unlabelled universe:
    trees,strings,languages, compostitions.partitions, intergers.
labelled universe:
    permutations,cycles,words,mappings,urns,cayley trees

Universal laws

of sweeping generarlity are on hallmark of analytic combinatorics
Example: Context-free constructions
Grobner basis eleminations
Drmota-Lalley-wood theorem

Analytic combinatorics at the next level

Combinatorial parameters are handled with MGFS, often leadning to limit
laws.
Complicated singualrity strucuture leads to oscillatory behavior (like RS/PF
        formula in common).
GFs with no singularties require saddle-points asymptotics.
"If you can specify it, you can generate a random structure".
Analytic transfer understanding transformations form one combinatrorial
struture to another.
New types of implicit GS functional equations are arise. very strong list and growing

Applications of analytic combinatorics

* patterns in random strings
* polynomials over finite fields
* hashing
* data compression
* geometric search
* combinatorial chemistry
* arithmetic alogrithms
* planr maps and graphs
...

ALGO

Archive

Dialogue & Discussion