0368428101 - Advanced Topics in Data Structures, Spring 20/21

Haim Kaplan, Thursdays 16-19

We will go through some beautiful data structures and algorithms, starting from splay trees, online greedy, the geometric view of binary search trees, and the dynamic optimality problem. Then we will move to dynamic tree, flows, and interior point methods.

       Lecture 1: The binary search tree model, offline and online algorithms, greedy future

       Lecture 2: Approximate the optimal static tree, splay trees, geometric view of binary search trees

       Lecture 3: Satisfied supersets and BST algorithms (offline and online equivalences)

       Homework 1

       Lecture 4: Online equivalence, Geometric Greedy and Greedy Future

       Bib on BSTs