Data Structures I
I am teaching English version of the course Data Structures 1 [NTIN066] in the summer semester of 2020/2021.
Lectures are held every Wednesday from 9:00 [in room S5 if possible, otherwise online]. Sign up for recitations in SIS.
We will meet on Zoom, you should have received a Zoom link by e-mail. If you have not, check your spam folder and let me know. All lectures will be recorded and the videos posted here.
Please read the complete rules of the game.
|3. 3.||Introduction: what is a data structure – interface vs. implementation, static vs. dynamic, model of computation. Examples of interfaces: queue, set, ordered set, dictionary. Flexible arrays (with both stretching and shrinking).||[L01]||video board|
|10. 3.||Different approaches to amortized analysis: aggregation, accounting, coins, potentials. Examples: binary counters, deletion using tombstones, lazily balanced BB[α] trees.||[L01]||video board|
|17. 3.||Splay trees: amortized analysis of the Splay operation. Incorporating splaying in Find, Insert, and Delete.||[L02] [ST]||video board|
|24. 3.||Splay trees: Complexity of BST operations; remarks on static and dynamic optimality, sequential traversal, and working set bound. (a,b)-trees: definition, logarithmic height, Find, Insert, Delete, choice of parameters.||[L02] [L03]||video board|
|31. 3.||(a,b)-trees: Amortized bounds for (a,2a-1) and (a,2a)-trees. Top-down splitting and joining. Memory hierarchy: theoretical models – I/O, cache-aware, cache-oblivious. Examples: cache effects on a real machine, sequential scanning of arrays.||[L03] [L05] [CO]||video board|
|7. 4.||Cache-oblivious algorithms. Sorting: MergeSort, multi-way MergeSort, a remark on FunnelSort and lower bounds. Matrix transposition: cache-aware tiling, cache-oblivious divide & conquer algorithm.||[L05] [CO]||video board|
|14. 4.||Cache-oblivious model versus reality: Sleator-Tarjan theorem on competitivity of LRU. Hashing: buckets with lists (chaining). Choice of hash functions: c-universal systems of functions, expected bucket size, time complexity of hashing with chains.||[L05] [CO] [STb] [L06]||video board|
|21. 4.||Hash function families: k-independence, constructions of universal/independent systems from linear functions. Generic bounds for composition of families, k-independent hashing from polynomials, tabulation hashing. Cuckoo hash tables.||[L06] [Tb] [E10]||video board|
|28. 4.||Hash tables: open addressing, analysis of linear probing.||[L06] [T]||video board|
|5. 5.||Hashing: lemmata on composition of hash function families. Hashing of vectors using scalar products. Bloom filters: 1-band, k-band.||[L06] [Tb]||video board|
|6. 5.||Material covered at exercise classes: Hashing of vectors and strings using polynomials, rolling hashes.||[L06]||video board|
|12. 5.||No lecture today – it's the rector's sporting day.|
|13. 5.||Material covered at exercise classes: Plan: Optimization of Bloom filters, counting filters.||[L06]|
|19. 5.||Plan: Multi-dimensional data structures. Range queries on binary search trees. K-d trees: basic principle, lower bound. Range trees: construction, queries, dynamization by partial rebuilds, speedup by fractional cascading.||[L07] [M7]|
Description of assignments can be found in ReCodEx. You need to create an account there and sign up to a group for the recitations you chose.
Please submit your solutions to ReCodEx.
- [CO] Erik Demaine: Cache-Oblivious Algorithms and Data Structures
- [E] Erik Demaine: přednáška Advanced Data Structures z MIT
- [H] Handbook of Data Structures and Applications (available online from MFF network)
- [Lxx] Martin Mareš: Lecture notes on data structures
- [M] Kurt Mehlhorn: Data Structures and Algorithms (digitální verze knihy)
- [ST] Sleator, Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985
- [STb] Sleator, Tarjan: Amortized Efficiency of List Update and Paging Rules, Communicatons of the ACM, 1985
- [T] Mikkel Thorup: Lecture Notes on Linear Probing with 5-Independent Hashing
- [Tb] Mikkel Thorup: High Speed Hashing for Integers and Strings