# 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)

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