Data Structures I
I am teaching English version of the course Data Structures I [NTIN066] in the summer semester of 2018/2019.
Lectures are held every Thursday from 9:00 in room S4. Sign up for recitations in SIS. The course is accompanied by optional practicals on Analysis of data structures.
Please read the complete rules of the game.
|21. 2.||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]|
|28. 2.||Different approaches to amortized analysis: aggregation, accounting, coins, potentials. Examples: flexible arrays, binary counters, lazily balanced BB[α] trees. Splay trees: description of the Splay operation, incorporating splaying to Find, Insert, and Delete.||[L01] [L02] [ST]|
|7. 3.||Splay trees: amortized analysis. Remarks on static and dynamic optimality, sequential traversal, and working set bound.||[L02] [ST]|
|14. 3.||(a,b)-trees: definition, logarithmic height, Find, Insert, Delete, choice of parameters. Amortized bounds for (a,2a-1) and (a,2a)-trees. Top-down splitting and joining, parallel (a,b)-trees. At the practicals: Equivalence between (2,4)-trees and left-leaning red-black trees.||[L03]|
|21. 3.||Heaps: binary and d-regular heaps, strict and lazy binomial heaps, Fibonacci heaps. Use in Dijkstra's algorithm.||[L04]|
|28. 3.||There is be no lecture.|
|4. 4.||Memory hierarchy: a sketch of hardware caches (see examples of memory access timings), full/set associativity and aliasing, multiple cache levels. Theoretical models: I/O, cache-aware, cache-oblivious. Example: sequential scanning of arrays. Sorting: MergeSort, multi-way MergeSort, a remark on FunnelSort and lower bounds.||[CO]|
|11. 4.||Cache-oblivious algorithms: matrix transposition. Model versus reality: Sleator-Tarjan theorem on competitivity of LRU.||[CO] [ST2]|
|18. 4.||Hashing: buckets with lists. Choice of hash functions: c-universal and k-independent systems of functions. Expected bucket size for c-universal systems. Constructions of universal/independent systems from linear functions.|
|25. 4.||Plan: Hashing: More systems of hash functions. Cuckoo hashing.|
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.
Lecture notes [Lxx]
|02. Splay trees||2019-03-11|
The notes are a work in progress. If you find any mistakes or hard-to-understand parts, please let me know.
- [CO] Erik Demaine: Cache-Oblivious Algorithms and Data Structures
- [FKS] Fredman, Komlós, Szemerédi: Storing a Sparse Table with O(1) Worst Case Access Time, Journal of ACM, 1984
- [H] Handbook of Data Structures and Applications (available online from MFF network)
- [KS] Keith Schwarz: Slides on Linear Probing (lecture at Stanford University)
- [Lxx] The lecture notes above
- [ST] Sleator, Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985
- [T] Mikkel Thorup: Lecture Notes on Linear Probing with 5-Independent Hashing
- [T2] Mikkel Thorup: High Speed Hashing for Integers and Strings