PhD Defence by Hjalte Wedel Vildhøj, Monday 17 November 2014 at 13:00
Abstract
Algorithms are often evaluated solely on their running time. However, in practical situations, space can be a more precious resource than time. Prominent examples include embedded devices with small amounts of writable memory, and data structures with a space requirement that exceeds the capacity of the fast memory. Under such circumstances we are interested in algorithms that allow their space complexity to be reduced, possibly at the cost of increasing their running time. In this work we study several fundamental combinatorial pattern matching problems on strings and design new algorithmic time-space trade-offs. Our results improve upon previous work in the area and show that many of these string problems can be efficiently solved using little space.
Supervisors:
Associate professor Inge Li Gørtz, DTU Compute
Associate professor Philip Bille, DTU Compute
Examiners:
Associate professor Carsten Witt, DTU Compute (Chair)
Professor Martin Farach-Colton, Rutgers University, USA
Professor Moshe Lewenstein, Bar-Ilan University, Israel
Chairman of the defence:
Associate professor Jørgen Villadsen, DTU Compute
All are welcome
A copy of the PhD thesis is available at the department.