ANALYTIC INFORMATION THEORY

In this part of the course we shall concentrate on applications of analytic algorithmics to information theory. Most likely, we will cover two of the following three topics.

  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

    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.

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

    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.

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