View publication
Title | Fast Algorithms That Yield Small and Fast Data Structures |
Authors | Jérémy Barbay |
Publication date | 2013 |
Abstract |
In many cases, the relation between encoding space and execution time translates into combinatorial lower bounds on the computational complexity of algorithms in the comparison or external memory models. We describe a few cases which illustrate this relation in a distinct direction, where fast algorithms inspire compressed encodings or data structures. In particular, we describe the relation between searching in an ordered array and encoding integers; merging sets and encoding a sequence of symbols; and sorting and compressing permutations. |
Downloaded | 5 times |
Pages | 97-111 |