Su in t Data Stru tures, Adaptive (analysis of) Algorithms: Overview, Combination, and Perspe tive

Abstra t. Su in t data stru tures repla e stati instan es of pointer based data stru tures, improving performan e in both time and spa e in the word RAM model (a restri tion of the RAM model where the size of ea h ma hine-word is bounded). The adaptive analysis of algorithms onsiders the omplexity in a ner way than merely grouping the instan es by size, yielding more pre ise lower and upper bounds on the omplexity of a problem. We give a qui k overview of those two te hniques, some brief examples of how they an be ombined on various sear h problems to obtain near optimal solutions, and some general perspe tive on the development and appli ation of those te hniques to other problems and in under dierent models. The slides orresponding to this abstra t are available at the following address