1. Analysis of Exact Pattern Matching

    2. 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
    (all can be downloaded from http://www.cs.purdue.edu/people/spa)
    1. M. Regnier and W. Szpankowski. On Pattern Frequency Occurrences in a Markovian Sequence Algorithmica, 22, 631-649, 1998. http://www.cs.purdue.edu

    2. W. Szpankowski. Average Case Analysis of Algorithms on Sequences . John Wiley & Sons, New York, 2001. (Chap. 7.1 and 8.3). http://www.cs.purdue.edu>
    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. http://www.cs.purdue.edu

  2. Worst Case Minimax Redundancy for memoryless Sources

    3. 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. http://www.cs.purdue.edu

    2. W. Szpankowski. Average Case Analysis of Algorithms on Sequences . John Wiley & Sons, New York, 2001. (Chap. 8.7). http://www.cs.purdue.edu

  3. Error Resilient LZ'77 and Tries/Suffix Trees Analysis

    4. 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. http://www.cs.purdue.edu

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