Abstract:
Classical data structures are designed to minimize the cost of each operation. In many situations this is too restrictive a goal: All we need is that the total cost of a sequence of operations is small. Using this more relaxed objective allows the design of simlper data structures that adapt to the way they are used. I'll give some examples and discuss a framework for the design and analysis of such structures.