Themenliste

Allgemeine Literatur

• G. Manzini. The Burrows-Wheeler Transform: Theory and Practice, MFCS 1999.


• G. Manzini. An Analysis for the Burrows Wheeler Transform, Journal of the ACM 48, 2001.

Themen für Projekte

Folgende Themen bieten interessante Aspekte für ein Praktikum:

1. Efficient Suffix Array Construction

• P. Ko and A. Aluru. Space Efficient Linear Time Construction of Suffix Arrays, CPM 2003.


• J. Kärkkäinen, P. Sanders and S. Burkhardt. Linear work suffix array construction, Journal of the ACM, To appear.


• P. Ferragina and G. Manzini. Engineering a Lightweight Suffix Array Construction Algorithm, Algorithmica 40, 2004.


• S. Puglisi, W. Smyth and A. Turpin. The Performance of Linear Time Suffix Sorting Algorithms, DCC 2005.


• V. Heun. Algorithmen auf Sequenzen, Skriptum, LFE Bioinformatik, LMU München, 2005.

2. Compressed Suffix Arrays

• V. Mäkinen and G. Navarro. Compressed Compact Suffix Arrays, CPM 2004.


• R. Gonzez, S. Grabowski, V. Mäkinen and G. Navarro. Practical Implementation of Rank and Select Queries, WEA 2005.


• V. Mäkinen and G. Navarro. New search algorithms and time/space tradeoffs for succinct suffix arrays, TechRep C-2004, Univ. Helsinki, Dept. CS, 2004.