MADALGO seminar

MADALGO theory seminar: Tsvi Kopelowitz, University of Michigan

2014.06.24 | Trine Ji Holmgaard Jensen

Dates Wed 31 Dec
Date 22:00
Location

Theory Seminar

 

Order/File-maintenance revisited again

 

Tsvi Kopelowitz, University of Michigan

 

Time: Wednesday, June 11 at 14:15 to 15:00

Location: Nygaard 298 NOTICE! DIFFERENT LOCATION!

 

Abstract

The order-maintenance data structure  is one of the most used black-boxes for many dynamic problems. The data structure allows to maintain a dynamic ordered list in constant time per update (assuming a pointer is given to the location) while supporting constant time order queries in which one wishes to determine the order of two elements in the list. All of these time bounds are in a worst case sense. Unfortunately , the correctness of the known solutions is considered by many to be questionable, due to a black-box usage of another unclear/complex data structure for another problem known as the file-maintenance problem.

We will survey the interesting history of the order maintenance problem and describe a new simple solution that has some additional properties which are useful for applications such as online suffix tree construction and fully persistent arrays. Finally, if time permits we will discuss a new understandable  solution for the file-maintenance problem.

Host: Gerth Stølting Brodal