[talks] Daniel Larkin will present his FPO, "Compressing Trees with a Sledgehammer" on Wednesday, 11/11/2015 at 10am in CS 402
ngotsis at CS.Princeton.EDU
Wed Nov 4 11:00:26 EST 2015
Daniel Larkin will present his FPO on Wednesday, 11/11/2015 at 10:00AM, 402 Computer Science.
The members of his committee are: Readers: Robert Sedgewick and Jeff Erickson (University of Illinois at Urbana-Champaign); Examiners: Sanjeev Arora, Zeev Dvir and Robert Tarjan (adviser).
A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk title and abstract follow below:
"Compressing Trees with a Sledgehammer"
A variety of problems can be solved more efficiently with the use of compressed trees.
The compressed tree method is flexible and can be applied in different ways to solutions
for many problems including disjoint set union, nested set union, and path
The central contribution of this thesis is a unified framework for the analysis of the
compressed tree method and a meta-theorem that proves an inverse-Ackermann-type
bound for a class of algorithms. The meta-theorem requires only that the compaction
method be well-structured and that the other operations maintain a forest structure
that admits a well-behaved rank function. These are the weakest known conditions
of any analysis to-date that proves such a bound.
We use the framework to give a clean, compact alternative analysis of all but one
of the known efficient algorithms for disjoint set union; we provide an explicit proof
of optimality for the remaining known optimal method, splicing by rank, which was
left as an exercise by Tarjan and van Leeuwen ; we prove that a new algorithm
for disjoint set union called randomized linking is optimal, giving theoretical backing
for some recent experimental results; and finally we proceed to explore the nested set
union problem, giving an optimal algorithm for any constant number of partitions as
well as a few alternatives for the restricted case of two partitions.
More information about the talks