0368428101 - Advanced Topics in Data Structures, Fall 21/22

Haim Kaplan, Thursdays 16-19, room 7 Schrieber

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 some data structures to handle strings.

        Lecture 1: The binary search tree model, approx optimal static tree, greedy future, splay trees

        Lecture 2: Update operations on splay tree, The geometric view, offline and online equivalences

        How to implement split trees

        Lecture 3: Geometric Greedy, Wilberís first lower bound

        Lecture 4: Tango Trees, The Maximum Flow Problem, Dinicís algorithm

        Lecture 5: Dynamic Trees

        Lecture 6: Analysis of Dynamic Trees, Push/Relabel

        Lecture 7: Push/Relabel with Dynamic Trees, Minimum cost flows

        Lecture 8: Cost scaling

        Lecture 9: Strongly polynomial cost scaling algorithm, Suffix trees

        Lecture 10: Suffix Trees, LCAs, Suffix arrays

        Lecture 11: Linear time construction of a suffix array, Burrows-Wheeler compression

        Lecture 12: Burrows-Wheeler compression, Huffman and Arithmetic codes

        Lecture 13: The FM index