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