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.

Bachelorarbeit.

Jan Laumeyer (2017)

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

Bei Interesse wenden Sie sich bitte an Florian Kurpicz.