BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Binary search trees (BSTs) and heaps are perhaps the simplest
implementations of the dictionary and the priority queue data types. They a
re among the most extensively studied structures in computer science\, yet\
, many basic questions about them remain open. What is the best strategy fo
r updating a BST in response to queries? Is there a single strategy that is
optimal for every possible scenario? Are self-adjusting trees ("splay tree
s"\, Sleator\, Tarjan\, 1983) optimal? In which cases can we improve upon t
he logarithmic worst-case cost per operation? Our understanding of heaps
is even more limited. Fibonacci heaps (and their relatives) are theoretica
lly optimal in a worst-case sense\, but they perform operations outside the
"pure" comparison-based heap model (in addition to being complicated in pr
actice). Is there a simple\, "self-adjusting" alternative to Fibonacci heap
s? Is there\, by analogy to BSTs\, a heap that can adapt to regularities in
the input? Are the two problems related? In my talk I will present some
old and new results pertaining to this family of questions.
DTSTAMP:20181120T171000
DTSTART:20181203T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:László Kozma (Freie Universität Berlin): Self-adjusting data struct
ures: trees and heaps
UID:94649660@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181203-L-Kozma.html
END:VEVENT
END:VCALENDAR