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.
date | topics | sources |
---|---|---|
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. |
Assignments
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.
Additional material (especially source code) is available as a Git repository. You can also browse it on the web.
Please submit your solutions to ReCodEx.
Lecture notes [Lxx]
chapter | version |
---|---|
01. Preliminaries | 2019-03-16 |
02. Splay trees | 2019-03-11 |
03. (a,b)-trees | 2019-04-01 |
04. Heaps | 2019-04-01 |
05. Caching | 2019-04-15 |
The notes are a work in progress. If you find any mistakes or hard-to-understand parts, please let me know.
Literature
- [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