Basser Seminar Series

Putting Your Data Structure on a Diet

Prof. Jyrki Katajainen
University of Copenhagen, Denmark

Wednesday 14 February 2007, 4-5 pm

School of IT Building, Lecture Theatre 123, Level 1

Abstract

Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several data-structural transformations are described that can be used to transform D into another data structure D' that supports the same operations as D, has considerably smaller memory overhead than D, and performs the supported operations by a small constant factor or a small additive term slower than D, depending on the data structure and operation in question. The compaction technique has been successfully applied for linked lists, dictionaries and priority queues.

Speaker's biography

Jyrki Katajainen is Associate Professor at the Department of Computing, University of Copenhagen, Denmark. He received his master and PhD degrees from the Department of Computer Science, University of Turku, Finland. His scientific work falls into several fields: algorithmic graph theory, computational complexity, computational geometry, data compression, parallel computing, performance programming, software tools, and sorting and searching. Currently, his active areas of research are experimental algorithmics, theoretical algorithmics, and software tools.