Speaker: Maverick Woo
Title: A Tale of Two Simple Data Structures
Abstract:
Among the numerous designs for meldable heaps, Fat Heaps by Kaplan and
Tarjan (1998) stand out to be almost perfect. Fat Heaps retain the
simplicity of Fibonacci Heaps, but the time bounds are worst-case instead
of amortized (although they don't match Fibonacci Heaps in the Meld
operation.) The key ingredient in this design is an abstraction known as
redundant counters, introduced by Clancy and Knuth back in 1977. I will
show how Fat Heaps work, and more importantly, how we can understand its
design from a deamortization point of view. This part of the talk will be
self-contained.
In the Dynamic Connectivity problem, we are given a set of $n$ fixed vertices
on which we have to maintain a dynamic graph supporting an intermixed sequence
of edge insertions, edge deletions and connectivity queries ("Are $u$ and $v$
connected?"). A long line of papers have been written on this problem, but I
will focus on the conceptually simple design by Holm, de Lichtenberg and Thorup
(1998) that supports each operation in deterministic amortized $O(log^2 n)$
time. This part of the talk will depend on an abstraction known as Dynamic
Trees. I will explain the abstraction but will not go into the details of its
implementation and analysis.
Notes from Maverick:
Coincidentally, Danny Sleator is teaching how to implement Dynamic Trees with
Splay Trees in his Advanced Data Structure course right after this talk. The
class starts at 1:30pm in Wean 4623.