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
· 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
· 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
· Lecture
11: Suffix trees
· Bib
on data structures for strings
· Lecture
12: LCA, suffix array, LCP array