Advanced Data Structures (Fall 2016)

Shay Mozes

Lectures (including video)

L01 Nov. 10

[+] Introduction and Amortized Analysis

[Slides] [Video]
Overview of the class. A quick review of material students should be very comfortable with. The second half of the lecture is devoted to explaining Amortized analysis, a technique that will be used throughout the class.
L02 Nov. 17

[+] Binomial and Fibonacci heaps

[Slides] [Video]
In this lecture we study Binomial and Fibonacci heaps.
L03 Nov. 24

[+] Fibonacci heaps wra-up and Hashing

[Slides] [Video]
We wrap up the discussion of Fibonacci heaps, and start discussing universal and perfect static hashing (FKS).
L04 Dec. 1

[+] Cuckoo Hashing

[Slides] [Video]
We present and analyze a dynamic hashing scheme called Cuckoo hashing. We then begin a new topic - datat structures supporting predecessor and successor queries on integer keys.
L05 Dec. 8

[+] Predecessor/Successor search. Move-to-Front

[Slides] [Video]
We present two data structures for maintaining a dynamic set of integers under predecessor and successor queries - van Emde Boas trees, and y-fast tries. Towards the end of the lecture we begin a discussion of self balancing linked lists and competitive analysis.
L06 Dec. 15

[+] Move to front and self-adjusting binary search trees.

[Slides] [Video]
We analyze the Move-to-Front heuristic for self-adjusting linked lists and show that it is 2-competitive both in the static and in the dynamic settings. We then begin discussing binary search trees. We show an algorithm for constructing an optimal search tree in the stochastic settings and begin discussion of rotations towards describing splay trees.
L07 Dec. 22

[+] Splay trees

[Slides] [Video]
We discuss and analyze Splay trees. We prove or mention the access theorem, static and dynamic finger theorem, working set theorem, sequential access theorem, and conclude by discussing the dynamic optimality conjecture.
L08 Dec. 29

[+] Wilber's lower bound and Tango trees

[Slides] [Video]
We present a lower bound on self-adjusting binary search trees, and then show how Tango trees utilize this lower bound to be O(loglog n) competitive againt the dynamic optimium.
L09 Jan. 5

[+] Link-Cut trees

[Slides] [Video]
We present a data structure, due to Sleator and Tarjan, for maintaining rooted unorderd trees under link and cut operations.
L10 Jan. 12

[+] Link-Cut trees and Euler Tour trees

[Slides] [Video]
We show that the amortized cost per operation of Link-Cut trees is logarithmic. We also discuss how to implement decorations that allow updates and queries along a root-to-node path in logarithmic time. On the last part of the lesson we present Euler Tour trees.
L11 Jan. 26

[+] Dynamic connectivity and RMQ/LCA

[Slides] [Video]
We disucss a data structure for maitaining a graph under edge insertions, deletions and connectivity queries in polylogarithmic time. We then begin discussing the range minimum query problem and its relationship to the lowest common ancestor problem.
L12 Feb. 2

[+] RMW wrap-up and Suffix trees

[Slides] [Video]
We conclude the discussion of RMQ data structures, and discuss tries, suffix trees and suffix arrays.

Infrastructure for this site and for making the videos available was generously provided by Erik Demaine.
For more information about the process and setup see this guide by Erik Demaine and Martin Demaine.