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

- Develop recurrence relation
- Derive GF equation
- Extract coefficients
- Asymptotics:Develop approximation

# Context

## Mathematics need

- Recurrence
- Genretating Function
- Asymptotics
- Trees
- Permutations
- Strings and Tries
- 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