Thursday, 29 July 2010, 14h00 M 111 (Seminar Room)
Abstract
This is a survey on randomized data structures. I discuss
here how randomization helps the design of efficient data structures,
with guarantees for expected performance. I will describe the skip lists
by W. Pugh and the randomized BSTs by S. Roura and myself,
their algorithms and their analysis - which, indeed,
must be probabilistic.
© 2010 Vasco Brattka