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

       Homework 2

       Lecture 5: Access Lemma for Greedy, Wilber first lower bound

       Lecture 6: Tango trees. Maximum flow and Dinicís algorithm

       Lecture 7: Dinicís algorithm with dynamic trees, dynamic MST, interval stabbing

       Lecture 8: Dynamic trees

       Homework 3

       Lecture 9: Dynamic trees + Push/relabel flow algorithm

       Lecture 10: The Push/relabel maximum flow algorithm with dynamic trees

       Bib on flow and dynamic trees

       Homework 4

       Lecture 11: Suffix trees

       Bib on data structures for strings

       Lecture 12: LCA, suffix array, LCP array

       Final Exam Ė moed A