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.