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 | 9 times |
| Pages | 97-111 |
|