## Analysis of Exact Pattern Matching

Math techniques:

1. Combinatorial Calculus (languages)
2. Generating functions
3. Simple complex asymptotics -- poles)
4. Moment analysis

Homework - Problems

1. Details of derivations
2. Limiting distribution
3. Extension to Markov
4. Another example of combinatorial calculus (joint distribution)

### References

1. M. Regnier and W. Szpankowski. On Pattern Frequency Occurrences in a Markovian Sequence, Algorithmica, 22, 631-649, 1998.

2. W. Szpankowski. Average Case Analysis of Algorithms on Sequences . John Wiley & Sons, New York, 2001. (Chap. 7.1 and 8.3).

3. P. Jacquet and W. Szpankowski. Analytic Approach to Pattern Matching. In Applied Combinatorics on Words (eds. Lothaire), Cambridge University Press (Encycl. of Mathematics and Its Applications), 2004.

## Worst Case Minimax Redundancy for memoryless Sources

Math techniques :

1. Shtarkov bound
2. Tree-like generating functions
3. Singularity analysis

Homework - Problems

1. Singularity expansion for T(z) and B(z)
2. Extraction of coefficients for B m (z) -- details

### References:

1. W. Szpankowski. On Asymptotics of Certain Recurrences Arising in Universal Coding. Problems of Information Transmission , 34, No.2, 142-146, 1998.
2. W. Szpankowski. Average Case Analysis of Algorithms on Sequences . John Wiley & Sons, New York, 2001. (Chap. 8.7).

## Error Resilient LZ'77 and Tries/Suffix Trees Analysis

Math techniques

1. Recurrences
2. Poissonization
3. Mellin transform
4. Depoissonization

Homework - Problems :

1. Solve some other trie like recurrences (Chap. 7.6.1)
2. Mellin transform exercises (Chap 9)
3. Depoissonization examples (Chap 10)
4. Limiting distribution of M n .

### References:

1. M. Ward and W. Szpankowski. Analysis of a Randomized Selection Algorithm Motivated by the LZ'77 Scheme. The First Workshop on Analytic Algorithmics and Combinatorics , (ANALCO04), New Orleans, January 10, 2004.

2. W. Szpankowski. Average Case Analysis of Algorithms on Sequences . John Wiley & Sons, New York, 2001. (Chap. 9 and 10).