| 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. | ||||