Analysis of Data Structures
In the summer semester of 2018/2019, I will teach extended recitation sessions [NTIN105] for the course Data Structures I. Unlike the regular recitations, which are mostly practical, these will attempt to provide deeper insight into the design and analysis of the respective structures.
We will meet on every other Monday from 9:00 in S322, starting with March 4th.
Class credit will be given for active participation in the classes.
If you want to contact me and consult anything, you are welcome to visit me in room S322 or to write me an e-mail to email@example.com.
|4. 3.||Splay trees: different implementations of Insert and Delete, weighted analysis, weights 1/n, scale invariance, static optimality.|
|18. 3.||Splay trees: static finger bound, working set bound. Representation of tries using inter-linked Splay trees.|
|1. 4.||Binomial heaps: a sequence of N Inserts, caching of minimum, different variants of amortized costs.|
|15. 4.||Binomial and Fibonacci heaps.|
|29. 4.||Cache-aware and cache-oblivious techniques. Binary search, (a,b)-trees, van Emde-Boas layout of binary search trees.|
|20. 5.||Systems of hash functions.|