[talks] Daniel Larkin will present his FPO, "Compressing Trees with a Sledgehammer" on Wednesday, 11/11/2015 at 10am in CS 402

[Nicki Gotsis]

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: 

Title: 
"Compressing Trees with a Sledgehammer" 

Abstract: 
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 
evaluation. 
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 [24]; 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.