Factional Cascading and Markov Couplings

31 maio 2017, 11:00 • Luís Manuel Silveira Russo

Fractional Cascading [Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica, 1 (1): 163–191, doi:10.1007/BF01840441.].

Using "dirty" arrays [Briggs, Preston, and Linda Torczon. "An efficient representation for sparse sets." ACM Letters on Programming Languages and Systems (LOPLAS) 2, no. 1-4 (1993): 59-69.].
Markov Chains and Couplings [11.2 Probability and Computing: Randomized Algorithms and Probabilistic Analysis: Michael Mitzenmacher and Eli Upfal 2005 Cambridge University Press]

Trees and BWT decoding.

30 maio 2017, 12:30 • Luís Manuel Silveira Russo

Exercises with Wavelet trees, decoding BWTs and Range trees

Wavelet Trees and Orthogonal Range Queries

30 maio 2017, 11:00 • Luís Manuel Silveira Russo

Computing rank and select for general alphabets, wavelet trees [Navarro, Gonzalo, and Veli Mäkinen. "Compressed full-text indexes." ACM Computing Surveys (CSUR) 39.1 (2007): 2].

The Burrows-Wheeler transform and backward search [Navarro, Gonzalo, and Veli Mäkinen. "Compressed full-text indexes." ACM Computing Surveys (CSUR) 39.1 (2007): 2.].

Orthogonal range queries, range trees [Bentley, J. L. (1979). "Decomposable searching problems". Information Processing Letters. 8 (5): 244–251] and layered range trees.

Succinct Data Structures

24 maio 2017, 11:00 • Luís Manuel Silveira Russo

The DFUDS and LOUDS tree representation.
[Rahman, Naila, and Rajeev Raman. "Engineering the LOUDS succinct tree representation." International Workshop on Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2006.]

Computing Rank and Select in constant time on bitmaps.
[Navarro, Gonzalo, and Veli Mäkinen. "Compressed full-text indexes." ACM Computing Surveys (CSUR) 39.1 (2007): 2.]

Exercises of chapters 9, 11 and 12.

23 maio 2017, 12:30 • Luís Manuel Silveira Russo

Computing edit distances, with and without Hirschberg's algorithm.
Computing Longest Increasing sub-sequences.
Computing maximal palindromes [Gusfield 9.2] and classifying tandems [Gusfield 9.6].
Simulating the SMAWK algorithm.