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 consult anything, please write an e-mail to mares+ds@kam.mff.cuni.cz and we will discuss possibilities.
| datum | téma |
|---|---|
| 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. |