Data Structures, Amortization, and Competitiveness
This talk will present a novel approach to the design and analysis of data structures based on amortized or time - averaged efficiency. This leads to especially simple and robust data structures that have "self- adjusting" behavior. Some examples of such data structures and the tools needed to analyze them will be discussed.