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