In this seminar we will investigate succinct, compact and compressed data structures which have lately become increasingly
more important in Bioinformatics. The best example is the very popular and widely used Compressed Suffix Array (also called FM-index). It uses constant time rank queries on bitvectors, as a replacement for table lookups.

In the seminar we will read original papers and parts of the new book "Compact data structures" by Gonzalo Navarro. The first part of the seminar will consist of chapters of the book reviewing basic techniques. The second part will deal with recent bioinformatics data structures.

During the first part, all participants will read the reading assignments each week and one will be randomly chosen to lead the discussion on the blackboard. During the second part of the seminar, selected research papers will be presented by the participants.

Literatur

Gonzalo Navarro: Compact data structures, Cambridge University Press