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)
· Lecture 4: Online equivalence, Geometric Greedy and Greedy Future