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