An Analysis of Binary Search Trees using Forbidden Submatrices

16^th July 2024, 13:00 Ashton Lecture Theatre
Dr. Wanchote Po Jiamjitrak
Department of Computer Science, University of Helsinki

Abstract

Binary search trees (BSTs) are one the most fundamental data structures in computer science. The long-standing conjecture "dynamic optimality" states that there exists an online BST algorithm with an offline optimal cost for any access sequence.

In this talk, we will explore BSTs from a geometric perspective and explore the greedy algorithm, which is arguably considered to be the most promising candidate for the dynamic optimality conjecture. Then, we will analyze the cost of the greedy algorithm using the mathematical tool "forbidden submatrices".

Biography

Wanchote is currently a postdoc at he University of Helsinki. His research interests include online algorithms, graph theory, and data structures.

Additional Materials

• https://arxiv.org/abs/2211.04112