Campus Event Calendar
Event Entry
What and Who
Proof of the Weighted Dynamic Finger Theorem by Iacono and Langerman.
Bhaskar Ray Chaudhury
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (others' work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 17 October 2017
13:00
60 Minutes
E1 4
024
Saarbrücken
Abstract
I will present the proof of the main theorem of the paper (by Iacono and Langerman) presented by Kurt Mehlhorn on 5th October. It states that GreedyASS performs asymptotically as well as any static binary search tree where each search begins from the last search (instead of the root). This is the strongest finger type bound to be proven for binary search trees.
Contact
Bhaskar Ray Chaudhury
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Data Structures, Dynamic Optimality Conjecture
The time taken will be 60 minutes!!
Bhaskar Ray Chaudhury, 10/16/2017 14:50
Bhaskar Ray Chaudhury, 10/06/2017 14:07
Bhaskar Ray Chaudhury, 10/05/2017 17:37 -- Created document.
Bhaskar Ray Chaudhury, 10/06/2017 14:07
Bhaskar Ray Chaudhury, 10/05/2017 17:37 -- Created document.