PSV-Queries

Beschreibung

Gegeben sei ein Array A der Länge n. Eine Anfrage nach dem previous smaller value (PSV) für eine Position i < n soll mit der Position j < i beantwortet werden, so dass A[j] ≤ A[i] und für alle j < k < i gilt A[k] > A[i]. PSV-Queries können mithilfe zusätzlicher Datenstrukturen in konstanter Zeit beantwortet werden und spielen eine wichtige Rolle in verschiedenen Anwendungen, z.B. Compressed Suffix Trees (CST). In dieser Arbeit sollen unterschiedliche Ansätze für die Beantwortung von PSV-Queries implementiert und evaluiert werden.

Typ

Bachelorarbeit.

Bearbeiter

Jan Laumeyer (2017)

Das sollten Sie mitbringen

  • Spaß an algorithmischen Problemstellungen
  • gute Programmierkenntnisse in C oder C++

Betreuer

Bei Interesse wenden Sie sich bitte an Florian Kurpicz.

 
Last modified: 2017-06-19 09:55 by Johannes Fischer
DokuWikiRSS-Feed