Topics covered by Wojtek (Wed, Th, F, June 9-11)

1. Analysis of Exact Pattern Matching (3h, Wednesday?)

Math techniques:
(a) Combinatorial Calculus (languages)
(b) Generating functions
(c) simple complex asymptotics -- poles)
(d) Moment analysis

Homework - Problems (for Mark to cover)
(a) Details of derivations
(b) Limiting distribution
(c) Extension to Markov
(d) Another example of combinatorial calculus (joint distribution)

References (all can be downloaded from http://www.cs.purdue.edu/people/spa)
M. Regnier and W. Szpankowski,
On pattern frequency occurrences in a Markovian sequence
Algorithmica, 22, 631-649, 1998.

W. Szpankowski, 
Average Case Analysis of Algorithms on Sequences,
John Wiley & Sons, New York, 2001.
(Chap. 7.1 and 8.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.


2. Worst Case Minimax Redundancy for memoryless Sources (3h, Thurs.)
   

Math techniques:
(a) Shtarkov bound
(b) Tree-like generating functions
(c) Singularity analysis

Homework - Problems
(a) Singularity expansion for T(z) and B(z)
(b) Extraction of coefficients for B^m(z) -- details

References:                                                                     
W. Szpankowski,                                                  
On asymptotics of certain recurrences arising in universal coding, 
Problems of Information Transmission,
34, No.2, 142-146, 1998.

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



3. Error Resilient LZ'77 and Tries/Suffix Trees Analysis (3h, Friday)

Math techniques
(a) Recurrences 
(b) Poissonization
(c) Mellin transform
(d) Depoissonization

Homework - Problems:
(a) Solve some other trie like recurrences (Chap. 7.6.1)
(b) Mellin transform exercises (Chap 9)
(c) Depoissonization examples (Chap 10)
(d) Limiting distribution of M_n.

References:
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.

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