===== Wavelet-Tree-Konstruktion mit speziellen CPU-Instruktionen =====

==== Beschreibung ====
Wavelet-Trees (WT) sind eine platzeffiziente Datenstruktur mit einer Vielzahl von Anwendungen in der Text-Indexierung, algorithmischen Geometrie.
Ziel dieser Arbeit ist die Konstruktion von WTs unter Ausnutzung spezieller CPU-Instruktionen (z.B. Packed Shuffle Bytes oder Parallel Bits Extract).
In der Praxis sollte dieser Algorithmus der schnellste sequentielle WT-Konstruktionsalgorithmus sein, siehe Kaneta (2018).
Der zu implementierende Algorithmus wurde von Babenko et al. (2015) und Munro et al. (2016) vorgestellt.

==== Typ ====
Masterarbeit

==== Das sollten Sie mitbringen ====
  * Spaß an algorithmischen Problemstellungen
  * Gute Programmierkenntnisse in C++
  * Kenntnisse in String-Algorithmen und idealerweise parallelen Algorithmen oder die Bereitschaft, sich selbständig einzuarbeiten

==== Betreuer ====
Die Arbeit wird betreut von [[staff:fischer|Johannes Fischer]] und [[staff:kurpicz|Florian Kurpicz]].